Random Tur\'an theorem for hypergraph cycles

arXiv2007.10320MaRDI QIDQ6345491FDOQ6345491

Authors: Dhruv Mubayi, L. Yepremyan 

Publication date: 20 July 2020

Abstract: Given $r$-uniform hypergraphs $G$ and $H$ the Tur'an number $mex(G,H)$ is the maximum number of edges in an $H$-free subgraph of $G$. We study the typical value of $mex(G,H)$ when $G=G_{n,p}^{(r)}$, the ErdH{o}s-R'enyi random $r$-uniform hypergraph, and $H=C_{2ell}^{(r)}$, the $r$-uniform linear cycle of length $2ell$. The case of graphs ($r=2$) is a longstanding open problem that has been investigated by many researchers. We determine $mex(G_{n,p}^{(r)},C_{2ell}^{(r)})$ up to polylogarithmic factors for all but a small interval of values of $p=p(n)$ whose length decreases as $ell$ grows. Our main technical contribution is a balanced supersaturation result for linear even cycles which improves upon previous such results by Ferber-Mckinley-Samotij and Balogh-Narayanan-Skokan. The novelty is that the supersaturation result depends on the codegree of some pairs of vertices in the underlying hypergraph. This approach could be used to prove similar results for other hypergraphs $H$.

This page was built for publication: Random Tur\'an theorem for hypergraph cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345491)