On The Random Turán number of linear cycles

2023/04/28 by Mubayi, Dhruv, Yepremyan, Liana · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2304.15003

Abstract

Given two r-uniform hypergraphs G and H the Turán number \rmex(G, H) is the maximum number of edges in an H-free subgraph of G. We study the typical value of \rmex(G, H) when G=G_n,p^(r), the Erdős-Rényi random r-uniform hypergraph, and H=C_2ℓ^(r), the r-uniform linear cycle of length 2ℓ. The case of graphs (r=2) is a longstanding open problem that has been investigated by many researchers. We determine the order of magnitude of \rmex(G_n,p^(r), C_2ℓ^(r)) for all r≥ 4 and all ℓ≥ 2 up to polylogarithmic factors for all values of p=p(n). Our proof is based on the container method and uses a balanced supersaturation result for linear even cycles which improves upon previous such results by Ferber-Mckinley-Samotij and Balogh-Narayanan-Skokan.

Cited by

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

Related

• Random Turán theorem for hypergraph cycles
• Turán theorems for even cycles in random hypergraph
• Hypergraph Turán numbers of vertex disjoint cycles
• Linear Turan numbers of r-uniform linear cycles and related Ramsey numbers
• Random Turán theorem for expansions of spanning subgraphs of tight trees