Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Claims
1995_03_01_krivelevich: Krivelevich's Theorem 3 (J. Combin. Theory Ser. B 1995): every regular triangle-free graph of degree at least 2n/5 has n/2 vertices spanning at most n²/50 edges, the blown-up C_5 alone meeting the bound; refereed.
2006_01_05_keevash_sudakov: Keevash and Sudakov (J. Combin. Theory Ser. B 2006) prove that a triangle-free graph with at most n²/12 edges, or with at least n²/5 edges, has n/2 vertices spanning at most n²/50 edges; refereed.
2013_11_22_norin_yepremyan: Norin and Yepremyan (J. Combin. Theory Ser. B 2015) prove the sparse-halves conjecture for triangle-free graphs of minimum degree at least 5n/14, with at least (1/5 - γ)n² edges, or close to the Petersen graph; refereed.
2021_04_19_razborov: Razborov (Mat. Sb. 2022) proves the sparse-halves conjecture for triangle-free graphs with no induced 2K_2, girth at least 5, independence number at least 2n/5, low density or strong regularity, and the bound 27n²/1024; refereed.