Polynomial Erdős–Hajnal bound for graphs of bounded VC-dimension
Statement
Let . A graph has VC-dimension at most when its VC-dimension is bounded by . Bounded-VC-dimension Erdős–Hajnal conjecture. There exists a constant such that every graph on vertices with VC-dimension at most contains a clique or an independent set of size .
This is a bounded-VC-dimension analogue of the Erdős–Hajnal conjecture. The paper records weaker lower bounds, including , and states that the polynomial bound remains open.
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.