Lexicode conjecture for clique covering numbers of Johnson graphs
Lexicode conjecture for clique covering numbers of Johnson graphs
Let be the Johnson graph whose vertices are the -subsets of a -element set, and let be the graph used in the construction above. Order the vertices of 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 lexicodehas cardinality
and its elements are pairwise overlapping. In particular, the code defines an independent set of cardinality in , so that
The construction is known computationally for . The conjecture would establish the stated clique-covering value for every that is a power of .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.