Turán theorems for even cycles in random hypergraph

2023/04/28 by Nie, Jiaxi · 1 citation
#05Dxx #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2304.14588

Abstract

Let F be a family of r-uniform hypergraphs. The random Turán number ex(G^r_n,p,F) is the maximum number of edges in an F-free subgraph of G^r_n,p, where G^r_n,p is the Erdös-Rényi random r-graph with parameter p. Let C^r_ℓ denote the r-uniform linear cycle of length ℓ. For p≥ n^-r+2+o(1), Mubayi and Yepremyan showed that ex(G^r_n,p,C^r_2ℓ)≤max\p^(1)/(2ℓ-1)n^{1+(r-1)/(2ℓ-1)+o(1)},pn^r-1+o(1)\. This upper bound is not tight when p≤ n^{-r+2+(1)/(2ℓ-2)+o(1)}. In this paper, we close the gap for r≥ 4. More precisely, we show that ex(G^r_n,p,C^r_2ℓ)=Θ(pn^r-1) when p≥ n^{-r+2+(1)/(2ℓ-1)+o(1)}. Similar results have recently been obtained independently in a different way by Mubayi and Yepremyan. For r=3, we significantly improve Mubayi and Yepremyan's upper bound. Moreover, we give reasonably good upper bounds for the random Turán numbers of Berge even cycles, which improve previous results of Spiro and Verstraëte.

Cited by

• Maximum in-general-position set in a random subset of \mathbbF^d_q

Related

• Random Turán theorem for hypergraph cycles
• On The Random Turán number of linear cycles
• Random Turán theorem for expansions of spanning subgraphs of tight trees
• Sidorenko Hypergraphs and Random Turán Numbers
• Random Turán Problems for Hypergraph Expansions