Structural conjecture for maximal independent sets in generalized Kneser graphs

From papers

Let d2d\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 d2d\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+d2\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.