The smallest-eigenspace dimension conjecture for qualitative independence graphs

For a positive integer kk, let QI(k2,k)QI(k^2,k) be the qualitative independence graph, and let (k!)k1k\frac{-(k!)^{k-1}}{k} be its smallest eigenvalue.

Smallest-eigenspace dimension conjecture. For all positive integers kk, the eigenspace corresponding to this smallest eigenvalue has dimension

(k22)(k21).\binom{k^2}{2}-\binom{k^2}{1}.

The dimension is known for k=3k=3, and the paper reports confirmation for k=4k=4. The conjecture is motivated by the structure of maximum independent sets and possible proofs that these graphs are cores.

Sources & referencesView supporting material

Primary source

Karen Meagher, “Covering arrays on graphs: qualitative independence graphs and extremal set partition theory”, arXiv:math/0701553 (2007).

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.