2020/04/23 by Jiaxi Nie, Nie, Jiaxi, Sam Spiro +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2004.10992
openalex publication_date 2020/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we consider an analog of the well-studied extremal problem for triangle-free subgraphs of graphs for uniform hypergraphs. A loose triangle is a hypergraph T consisting of three edges e,f and g such that |e ∩ f| = |f ∩ g| = |g ∩ e| = 1 and e ∩ f ∩ g = ∅. We prove that if H is an n-vertex r-uniform hypergraph with maximum degree \triangle, then as \triangle → ∞, the number of edges in a densest T-free subhypergraph of H is at least \frace(H)\triangle(r-2)/(r-1) + o(1). For r = 3, this is tight up to the o(1) term in the exponent. We also show that if H is a random n-vertex triple system with edge-probability p such that pn3→∞ as n→∞, then with high probability as n → ∞, the number of edges in a densest T-free subhypergraph is min\(1-o(1))pn\choose3,p(1)/(3)n2-o(1)\. We use the method of containers together with probabilistic methods and a connection to the extremal problem for arithmetic progressions of length three due to Ruzsa and Szemerédi.