On non-degenerate Turán problems for expansions
The r -uniform expansion F ( r ) + of a graph F is obtained by enlarging each edge with r − 2 new vertices such that altogether we use ( r − 2 ) | E ( F ) | new vertices. Two simple lower bounds on the largest number ex r ( n , F ( r ) + ) of r -edges in F ( r ) + -free r -graphs are Ω ( n r − 1 ) (in the case F is not a star) and ex ( n , K r , F ) , which is the largest number of r -cliques in n -vertex F -free graphs. We prove that ex r ( n , F ( r ) + ) = ex ( n , K r , F ) + O ( n r − 1 ) . The proof comes with a structure theorem that we use to determine ex r ( n , F ( r ) + ) exactly for some graphs F , every r < χ ( F ) and sufficiently large n .
Authors
- Dániel Gerbner (ORCID: https://orcid.org/0000-0001-7080-2883)
Publication Details
- Journal
- European Journal of Combinatorics
- Published
- 2024-09-23
- DOI
- https://doi.org/10.1016/j.ejc.2024.104071
- Citations
- 4
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 5.29
Funders
- Nemzeti Kutatási és Technológiai Hivatal
- Nemzeti Kutatási Fejlesztési és Innovációs Hivatal