Lexicode conjecture for clique covering numbers of Johnson graphs

Let J(2k,k1)J(2k,k-1) be the Johnson graph whose vertices are the (k1)(k-1)-subsets of a 2k2k-element set, and let JK(2k,k1)JK(2k,k-1) be the graph used in the construction above. Order the vertices of J(2k,k1)J(2k,k-1) lexicographically and apply the greedy algorithm to obtain a lexicode

in $J(2k,k-1)$. Let $C_k$ denote the corresponding benchmark cardinality. **Lexicode conjecture.** Assume that $k>1$ is a power of $2$. The lexicode

has cardinality

=12Ck,||=\tfrac{1}{2}C_k,

and its elements are pairwise overlapping. In particular, the code defines an independent set of cardinality CkC_k in JK(2k,k1)JK(2k,k-1), so that

θ(J(2k,k))=Ck.\theta(J(2k,k))=C_k.

The construction is known computationally for k=2,4,8,16k=2,4,8,16. The conjecture would establish the stated clique-covering value for every k>1k>1 that is a power of 22.

Sources & referencesView supporting material

Primary source

Søren Fuglede Jørgensen, “On the clique covering numbers of Johnson graphs”, arXiv:2502.15019 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.