Linear-size Borel independent complete sections conjecture
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.