Sharp linear Tur\'an remainders for cycle and edge extremality
In the authors' words
For a graph , let denote the number of edges of , and let be the number of distinct cycles in . Morrison, Roberts and Scott asked whether, for every fixed graph and all large , some -vertex -free graph maximizes both and . In this paper, we show that the answer is no for every possible chromatic number. Let be the complete -partite Tur\'an graph on vertices. We find a constant such that if is sufficiently large and is a finite family with satisfying \[ ex(n,\mathcal{H})<e(T_{n,r})+\gamma_r n, \] then every cycle-maximal -free graph is edge-extremal, and is best possible.
Main resultLimitation the authors admit
Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 26pages