The Burr-Erd\H{o}s-Graham-S\'os conjecture for the seven-cycle
En palabras de los autores
For a graph , let be the least number of colors in an edge-coloring of some -vertex graph with at least edges in which every copy of is rainbow. Burr, Erd\H{o}s, Graham, and S\'os conjectured that for every fixed , and Buci\'c, Chen, and Ma recently proved this for all . We prove the remaining case : \[ f\left(n,\left\lfloor n^2/4\right\rfloor+1,C_7\right) =\left(\frac18+o(1)\right)n^2. \] The lower bound rests on a weighted palette inequality, which we prove with an exact rational certificate on five sampled vertices. Its main ingredients are a fractional matching of compatible triangular edges and private resources attached to nontriangular edges. A stable form of the inequality, combined with regularity, triangle removal, and a direct argument for graphs close to bipartite, transfers the bound to arbitrary edge-colorings. We also describe a Lean 4 formalization of the conjecture for every fixed , which combines the new seven-cycle proof with a formalization of the Buci\'c-Chen-Ma argument for .
Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 20 pages. Lean 4 formalization and certificate verifier: https://github.com/Asad-Shahab/erdos-809-lean