Random Turán Problems for Hypergraph Expansions

2024/08/06 by Jiaxi Nie, Nie, Jiaxi, Sam Spiro +1
Computer Science · Mathematics · #05C35 #05C65 #05C80 #05D40 #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.2408.03406

openalex publication_date 2024/08/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

Given an r₀-uniform hypergraph F, we define its r-uniform expansion F^(r) to be the hypergraph obtained from F by inserting r-r₀ distinct vertices into each edge of F, and we define ex(G_n,p^r,F^(r)) to be the largest F^(r)-free subgraph of the random hypergraph G_n,p^r. We initiate the first systematic study of ex(G_n,p^r,F^(r)) for general hypergraphs F. Our main result essentially resolves this problem for large r by showing that ex(G_n,p^r,F^(r)) goes through three predictable phases whenever F is Sidorenko and r is sufficiently large, with the behavior of ex(G_n,p^r,F^(r)) being provably more complex whenever F has no Sidorenko expansion. Moreover, our methods unify and generalize almost all previously known results for the random Turán problem for degenerate hypergraphs of uniformity at least 3.

Related

• Sidorenko Hypergraphs and Random Turán Numbers
• Random Turán Problems for K_s,t Expansions
• Random Turán theorem for hypergraph cycles
• Random Turán theorem for expansions of spanning subgraphs of tight trees
• Turan Problems on Non-uniform Hypergraphs