Linear-size Borel independent complete sections conjecture
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.