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

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

On non-degenerate Turán problems for expansions

Dániel Gerbner
4 citations
European Journal of Combinatorics
Limits and Structures in Graph Theory
5.29
article

On non-degenerate Turán problems for expansions

Dániel Gerbner
article en
4 citations

Abstract

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 .

European Journal of CombinatoricsVol. 124
Nemzeti Kutatási és Technológiai Hivatal, Nemzeti Kutatási Fejlesztési és Innovációs Hivatal
Openalex Percentile: Top 3%
Limits and Structures in Graph Theory
5.29
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.