Structural conjecture for maximal independent sets in generalized Kneser graphs

About 4 years old · traced to

Let d≥2d\ge 2 be an integer, and let qΓ2d+1,{d,d+1}q\Gamma_{2d+1,\{d,d+1\}} be the Kneser graph whose vertices are the relevant subspaces and whose adjacency is determined by dimensions dd and d+1d+1. A point-pencil and a dual point-pencil are the standard maximal independent sets of these two types. Structural conjecture. For every integer d≥2d\ge 2 there is an integer ρ(d)\rho(d) such that every maximal independent set of qΓ2d+1,{d,d+1}q\Gamma_{2d+1,\{d,d+1\}} contains a point-pencil, a dual point-pencil, or has at most

ρ(d)⋅qd2+d−2\rho(d)\cdot q^{d^2+d-2}

elements.

This conjecture supplies the structural information on large maximal independent sets needed to extend the paper's chromatic-number argument from d=3d=3 to every dd for which the corresponding result is available. Its resolution is not specified in the source.

References

Primary source

Jozefien D'haeseleer, Klaus Metsch and Daniel Werner, “On the Chromatic Number of some generalized Kneser Graphs”, arXiv:2205.02632 (2022).

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.