Černý–Kynčl–Tóth dense stability conjecture
Statement
Let be a family of graphs. It is stable if there exist positive constants , , and such that, for every graph with at least vertices and edges, a positive fraction of all subgraphs of with edges has crossing number at least . Equivalently, if is obtained from by deleting each edge independently with probability , then with high probability .
Černý–Kynčl–Tóth dense stability conjecture. There exists an such that, for each , the family of graphs with edges is stable.
The original all- stability conjecture was disproved for . This restricted conjecture remains open for denser graph families, and concerns the robustness of crossing numbers under random edge deletion.
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.