Linear-size Borel independent complete sections conjecture

About 3 years old · traced to

Let HH be a Borel graph with finite asymptotic separation index, and let G1G_1 and G2G_2 be spanning Borel subgraphs of HH. A set is a complete section for a graph if it meets every connected component, and a section is G1G_1-independent if it contains no edge of G1G_1.

Linear-size Borel independent complete sections conjecture. There exist constants C,0>0C,0>0 with the following property: if the maximum degree of G1G_1 is at most 00 and every component of G2G_2 contains at least C0C0 vertices, then there is a Borel G1G_1-independent complete section for G2G_2.

The preceding theorem proves the analogous conclusion with a superlinear lower bound 2250log⁡02^{25}0\log0 on the sizes of the components of G2G_2. The conjecture asks whether a linear bound in 00 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

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.