2023/09/04 by Dániel Gerbner, Gerbner, Dániel · 1 citation
Mathematics · #Limits and Structures in Graph Theory #Graph theory and applications #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2309.01857
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 exr(n,F(r)+) of r-edges in F(r)+-free r-graphs are Ω(nr-1) (in the case F is not a star) and ex(n,Kr,F), which is the largest number of r-cliques in n-vertex F-free graphs. We prove that exr(n,F(r)+)=ex(n,Kr,F)+O(nr-1). The proof comes with a structure theorem that we use to determine \exr(n,F(r)+) exactly for some graphs F, every rχ(F) and sufficiently large n.