KPPY 100

Given an $r$-uniform hypergraph $G$ and a colouring $p : E(G) \to [k]$ of the hyperedges with up to $k$-colours, an adapted $k$-coloring of $(G,p)$ is a vertex map $\phi:V(G) \to [k]$ such that for every hyperedge $e$, there is some vertex in $e$ such that $\phi(v) \neq p(e)$. We show that for $k,r \geq 2$, the problem of deciding if an instance edge coloured graph $(G,p)$ has an adapted $k$-colouring is $NP$-complete unless $(k,r) = (2,2)$. In this last case, we show that the problem is polynomial time solvable. This is joint work with Mark Siggers.

Toric varieties are classical testing grounds in algebraic geometry, as the fundamental theorem of toric geometry tells us that a fan completely determines the associated toric variety. While complex toric varieties have been extensively studied, the geometric and topological properties of their real loci remain far less understood. To address this gap, we investigate real toric varieties from nested fans, with a focus on their topological invariants. In particular, we show that when the nested fan is chordal or graphical, the associated real toric variety exhibits rich combinatorial structures and interesting topological phenomena.

In 1979, Neumaier gave a bound on $\lambda$ in terms of $m$ and $\mu$, where $-m$ is the smallest eigenvalue of a primitive strongly regular graph, unless the graph in question belongs to one of the two infinite families of strongly regular graphs. We improve this result. We also indicate how our methods can be used to give an alternate derivation of Bruck's Completion Theorem for orthogonal arrays.

In 1973, Hoffman showed that for any fixed real number $\lambda$, there exists a positive integer $t=t(\lambda)$, such that if a graph $G$ has no induced subgraphs isomorphic to $K_{1,t}$ or $\widetilde{K_{2t}}$, then $G$ has smallest eigenvalue at least $\lambda$. In 2016, Kim, Koolen and Yang showed that if a graph $G$ has smallest eigenvalue at least $\lambda$, then there exist some dense induced subgraphs $\{Q_i\}$ of $G$, such that each vertex lies in at most $\lambda$ $Q_i$'s, and almost all edges of $G$ lies in at least one of the $Q_i$'s. In this talk, we will extend these results to signed graphs. In particular, for any fixed $\lambda$, there exists $t=t(\lambda)$, such that if a signed graph $G$ has no induced subgraphs switching equivalent to $K_{1,t}$, $\widetilde{K_{2t}}$, $\widehat{K_{2t}}$ or $K_t^-$, then $G$ has smallest eigenvalue at least $\lambda$. If a signed graph $G$ has smallest eigenvalue at least $\lambda$, then there exists some induced subgraphs $\{Q_i\}$ of $G$ with similar properties as the unsigned case. Finally, I will talk about our work on signed graphs with smallest eigenvalue at least $-1-\sqrt{2}$. This is joint work with Cao Mengyue under the supervision of Professor Jack Koolen.

For two integers $k$ and $\ell$, an $(\ell \text{ mod }k)$-cycle means a cycle of length $m$ such that $m\equiv \ell\pmod{k}$. In 1977, Bollobás proved a conjecture of Burr and Erdős by showing that if $\ell$ is even or $k$ is odd, then every $n$-vertex graph containing no $(\ell \text{ mod }k)$-cycles has at most a linear number of edges in terms of $n$. Since then, determining the exact extremal bounds for graphs without $(\ell \text{ mod }k)$-cycles has emerged as an interesting question in extremal graph theory, though the exact values are known only for a few integers $\ell$ and $k$. Recently, Győri, Li, Salia, Tompkins, Varga and Zhu proved that every $n$-vertex graph containing no $(0 \text{ mod }4)$-cycles has at most $\left\lfloor \frac{19}{12}(n -1) \right\rfloor$ edges, and they provided extremal examples that reach the bound, all of which are not $2$-connected. In this paper, we show that a $2$-connected graph without $(0 \text{ mod }4)$-cycles has at most $\left\lfloor \frac{3n-1}{2} \right\rfloor$ edges, and this bound is tight by presenting a method to construct infinitely many extremal examples.

A (symmetric) association scheme is called amorphic if any two relations fuse. It is known that in a amorphic scheme all the relations are SRG of Latin square type of negative Latin square type.

In this talk I will give new sufficient conditions for a scheme to be amorphic. Also I will discuss schemes that are close to be amorphic.

This is based on joint work with Edwin van Dam and Yan Zhen Xiong.

A shortest self-orthogonal embedding of a binary linear code has become of great interest because many such codes produced optimal self-orthogonal codes. However, it was less known exactly how many columns should be added to get a shortest self-orthogonal embedding of a given binary linear code. In this talk, we answer this question by giving an exact number of columns to be added. We have constructed a self-dual [22, 11, 6] code, called the shortened Golay code, from a binary [15, 11, 3] Hamming code and a self-dual [52, 26, 8] code from a binary [31, 26, 3] Hamming code. We begin with the introduction to coding theory f or the general audience.

In 1981, Furedi and Komlos established an upper bound for the spectral norm of random weighted graphs whose edge weights are independent (though not necessarily identically distributed) real-valued bounded random variables. In 2005, Vu further sharpened this result.

In this work, we obtain analogous upper bounds in the case where the weights are not necessarily bounded, but their $s$-moments are uniformly bounded for some $s > 4$. As an application, we show that Brouwer’s conjecture holds for such random weighted graphs.

This is joint work with S. Moon.

Let $\Gamma$ be a $Q$-polynomial distance-regular graph with vertex set $X$ and diameter $D \geq 3$. Fix a vertex $x \in X$. The Terwilliger algebra $T = T(x)$ of $\Gamma$ is the subalgebra of $\operatorname{Mat}_X(\mathbb{R})$ generated by the adjacency matrix $A$ of $\Gamma$ and the dual adjacency matrix $A^* = A^*(x)$ with respect to $x$. Consider the $\mathbb{R}$-vector space $V = \mathbb{R}^X$ consisting of column vectors indexed by $X$. Then $V$ becomes a $T$-module. Let $W$ be an irreducible $T$-submodule of $V$ with diameter $d$. It is known that $A$ and $A^*$ act on $W$ as a tridiagonal pair; that is, both are diagonalizable on $W$, and each acts on the eigenspaces of the other in a block-tridiagonal fashion. Let $\{\rho_i\}_{i=0}^d$ denote the sequence of dimensions of the eigenspaces of $A$ on $W$, taken in the ordering with respect to which $A^*$ acts in block-tridiagonal fashion. We say that $W$ is sharp if $\rho_0 = 1$. In this talk, we show that every irreducible $T$-submodule of $V$ is sharp. Moreover, we discuss the subalgebras $E_1^* T E_1^*$, $E_1 T E_1$, $E_D^* T E_D^*$, and $E_D T E_D$, and show that each is commutative and consists entirely of symmetric matrices. This is joint work with Blas Fernandez and Jongyook Park.

The classic Grid Theorem due to Robertson and Seymour tells us that a graph with high treewidth contains a large grid as a minor. Initial bounds for what is considered ‘high’ were not explicitly given, but have over time been brought down to roughly lie in $O(k^10)$, where k is the number of columns of the grid we want to find. We further know that the bound lies above $k^2 {\rm log} k$. If one only considers $H$-minor-free graphs it is however possible to push this down to a function that is linear in $k$, but heavily dependent on the size of $H$. The first such result gave no explicit bounds for the contribution of H and a recent improvement improved this to single exponential. We show that the total function can be lowered substantially to roughly $kt^2 + {\rm poly}(t)$. We give an introduction to all terms mentioned above, provide a sketch of the proof, as well as an idea of how the Graph Minor Structure Theorem contributes to this result.

This is joint work with Giannos Stamoulis, Dimitrios Thilikos, and Sebastian Wiederrecht.

We will discuss lower and upper bounds of the burning number of Hamming graphs, Johnson graphs, and halved cube graphs. To find the lower bounds, we use the fact that $1$-skelton of the eigenpolytopes of these graphs are isomorphic to the original graphs. In this case we can construct a dynamic search algorithm that runs on the eigenpolytope to find an unburned vertex. This idea was first used by Alon to determine the burning number of the hypercube graphs.

This talk is based on joint work with Hajime Tanaka. (arXiv:2508.17559)