15 problems

Delsarte's conjecture. There are no nontrivial perfect codes in Johnson graphs.

Karloff's eigenvalue-range conjecture. The condition $0\leq b\leq m/12$ in the theorem on the smallest eigenvalue of $J(m,m/2,b)$ could be relaxed to

For $0\leq k<n$, let ${{F\!\!J}}(n,k)$ be the full-flag Johnson graph whose vertices are the full flags of $[n]$, with adjacency when exactly $k$ flag components differ. Let $Q$ be…

The Johnson graph $J(n,i)$ has as its vertices the $i$-element subsets of $\{1,\ldots,n\}$, with two vertices adjacent when their intersection has cardinality $i-1$. Write…

Cornet–Dravec–Torres monotonicity conjecture. For every $r\ge 3$ and every $n\ge 2r$,

Cornet–Dravec–Torres conjecture. For every odd integer $n\ge 7$,

Let ${{F\!\!J}}(n,2)$ be the full-flag Johnson graph on the full flags of $[n]$, where two flags are adjacent exactly when two flag components differ. Its Aldous property means tha…

Chromatic number conjecture for Johnson graphs. This is the remaining case in the known classification of $\chi(J(n,3))$ for $n>7$: the values $n-2$ and $n-1$ are known in the othe…

Lexicode conjecture. Assume that $k>1$ is a power of $2$. The lexicode $$ has cardinality

Let $F_k(K_n)$ be the $k$-token graph of the complete graph $K_n$, and let $\operatorname{pw}$ and $\operatorname{tw}$ denote pathwidth and treewidth. Optimal path-decomposition co…

For integers $n$ and $k$ with $1\le k\le n-1$, let $F_k(K_n)$ be the $k$-token graph of the complete graph $K_n$, also known as the Johnson graph. The tree decomposition of this gr…

Boundary-ratio comparison conjecture. This inequality is valid for all natural numbers $n\geq 3$.

For integers $k\geq 1$, $0\leq s<k$, and $n\geq 2k-s+\mathbf{1}_{s=0}$, let $J_{n,k,s}$ be the graph whose vertices are the $k$-element subsets of $[n]$, with an edge between two s…

Let $G_n=K(n,2)$ be the Johnson graph whose vertices are the $2$-subsets of an $n$-element set, with two vertices adjacent when the corresponding subsets intersect in one element.…

Second-largest eigenvalue conjecture. The subset of eigenvalues of $\textit{FJ}(n,1)$ arising as eigenvalues of $M$ also includes the second-largest eigenvalue of…