2023/05/07 by Jiaxi Nie, Nie, Jiaxi · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2305.04193
openalex publication_date 2023/05/07 · openalex created_date 2023/05/10 · openalex updated_date 2026/07/28
The r-expansion of a k-uniform hypergraph H, denoted by H(+r), is an r-uniform hypergraph obtained by enlarging each k-edge of H with a set of r-k vertices of degree one. The random Turán number ex(Grn,p,H) is the maximum number of edges in an H-free subgraph of Grn,p, where Grn,p is the Erdős-Rényi random r-graph with parameter p. In this paper, we prove an upper bound for ex(Grn,p,H) when H belongs to a large family of r-partite r-graphs: the r-expansion of spanning subgraphs of tight trees. This upper bound is essentially tight for at least the following two families of hypergraphs. 1. Our upper bounds are essentially tight for expansions of Kk-1k, the complete (k-1)-graph on k vertices. The proof of the lower bound makes use of a recent construction of Gowers and Janzer generalizing the famous Ruzsa-Szemerëdi construction. In particular, when k=3, this answers a question of the current author, Spiro and Verstraëte concerning the random Turán number of linear triangle. 2. Let T be a tight tree such that the intersection of all edges of T is empty. Simple construction shows that the upper bounds we have for expansions of T are essentially tight. The main technical contribution of this paper is a new way to obtain balanced supersaturation results for expansions of hypergraphs: we combine two ideas, one of Mubayi-Yepremyan and another of Balogh-Narayanan-Skokan, via codegree dichotomy. We note that neither of these two ideas alone would be enough to recover results in this paper.