Linear-size Borel independent complete sections conjecture
Let be a Borel graph with finite asymptotic separation index, and let and be spanning Borel subgraphs of . A set is a complete section for a graph if it meets every connected component, and a section is -independent if it contains no edge of .
Linear-size Borel independent complete sections conjecture. There exist constants with the following property: if the maximum degree of is at most and every component of contains at least vertices, then there is a Borel -independent complete section for .
The preceding theorem proves the analogous conclusion with a superlinear lower bound on the sizes of the components of . The conjecture asks whether a linear bound in suffices; the finite asymptotic separation index assumption is necessary in general.
References
Primary source
Anton Bernshteyn and Felix Weilacher, “Borel versions of the Local Lemma and LOCAL algorithms for graphs of finite asymptotic separation index”, arXiv:2308.14941 (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
No solutions have been posted yet.