The maximum-independent-set structure conjecture for qualitative independence graphs

Let QI(k2,k)QI(k^2,k) be the qualitative independence graph, and for distinct a,b{1,,k2}a,b\in\{1,\dots,k^2\} let S{a,b}S_{\{a,b\}} denote the independent set defined in the paper.

Maximum-independent-set structure conjecture. For all positive integers kk, every maximum independent set in QI(k2,k)QI(k^2,k) is of the form S{a,b}S_{\{a,b\}} for distinct a,b{1,,k2}a,b\in\{1,\dots,k^2\}.

This extends the corresponding result known for QI(9,3)QI(9,3). If true, the structural description would support proving that QI(k2,k)QI(k^2,k) is a core for every kk.

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.