Linear-size Borel independent complete sections conjecture

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 2250log02^{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.

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

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.