Pikhurko–Sousa conjecture on asymptotic extremal decompositions
Statement
Let be a graph with chromatic number at least . For an -vertex graph , let be the minimum number of parts in an edge partition into copies of and single edges, and define . Let denote the maximum number of edges in an -vertex graph containing no copy of .
Pikhurko–Sousa conjecture. There is an integer such that
for every .
Pikhurko and Sousa had previously established the asymptotic relation for each fixed graph with chromatic number at least ; the conjecture asks for eventual exact equality.
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.