Turán density of tight cycles minus one edge in the ℓ 2 \ell_{2} -norm

Levente Bodnár, Jinghua Deng, Jianfeng Hou, Xizhi Liu, Hongbin Zhao · 2025

Read Turán density of tight cycles minus one edge in the ℓ 2 \ell_{2} -norm by Levente Bodnár, Jinghua Deng, Jianfeng Hou, Xizhi Liu, Hongbin Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00812.txt.

Introduction

Levente Bodnar and co-authors prove a density result for hypergraphs in a 2025 paper. The objects are tight cycles with one edge removed. The measure used weights codegrees squared, a stronger norm than plain edge counts.

For cycle lengths from five up, with a remainder condition, extremal structures are pinned down. Any near-maximal example must sit close to an iterated blowup of one triple. That confirms a conjecture from a 2022 survey in stronger form. Readers see how a sharper norm forces a clean global structure out of a local forbidding rule.

Catalog record

CREATORLevente Bodnár, Jinghua Deng, Jianfeng Hou, Xizhi Liu, Hongbin Zhao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-00812

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Turán density of tight cycles minus one edge in the ℓ 2 \ell_{2} -norm Levente Bodnár, Jinghua Deng, Jianfeng Hou, Xizhi Liu, Hongbin Zhao Abstract The 3 3 -uniform tight ℓ \ell -cycle minus one edge C ℓ 3 − C_{\ell}^{3-} is the 3 3 -graph on ℓ \ell vertices consisting of ℓ − 1 \ell-1 consecutive triples in the cyclic order. We show that for every integer ℓ ≥ 5 \ell\geq 5 satisfying ℓ ≢ 0 ( mod 3 ) \ell\not\equiv 0\pmod{3} , every C ℓ 3 − C_{\ell}^{3-} -free 3 3 -graph whose ℓ 2 \ell_{2} -norm, that is, the sum of codegree squares, is close to the maximum must be structurally close to the iterative blowup of a single triple. This confirms a conjecture of Balogh–Clemen–Lidický [ BCL22a , Conjecture 3.5] in a stronger form. 1 Introduction Given an integer r\geq 2 , an r -uniform hypergraph (henceforth an r -graph ) \mathcal{H} is a collection of r -subsets of some set V . We call V the vertex set of \mathcal{H} and denote it by V(\mathcal{H}) . The size of V(\mathcal{H}) is denoted by v(\mathcal{H}) . We identify a hypergraph \mathcal{H} with its set of edges, and hence, |\mathcal{H}| represents the number of edges in \mathcal{H} . Given an r -graph \mathcal{H} , the shadow of \mathcal{H} is defined as \displaystyle\partial\mathcal{H}\coloneqq\left\{e\in\binom{V(\mathcal{H})}{r-1}\colon\text{there exists an edge $E\in\mathcal{H}$ containing $e$}\right\}. For an (r-1) -set T\subseteq V(\mathcal{H}) , the neighborhood of T in \mathcal{H} is defined as \displaystyle N_{\mathcal{H}}(T)\coloneqq\left\{v\in V(\mathcal{H})\colon T\cup\{v\}\in\mathcal{H}\right\}, and the codegree of T is d_{\mathcal{H}}(T)\coloneqq|N_{\mathcal{H}}(T)| . Following the definitions in [ BCL22b , CIL+24 ] , for every real number p\geq 1 , the \ell_{p} -norm of an r -graph \mathcal{H} is defined as \displaystyle\left\lVert\mathcal{H}\right\rVert_{p}\coloneqq\sum_{e\in\partial\mathcal{H}}d^{p}_{\mathcal{H}}(e), where d^{p}_{\mathcal{H}}(e) is an abbreviation for \left(d_{\mathcal{H}}(e)\right)^{p} . Note that for p=1 , we have \left\lVert\mathcal{H}\right\rVert_{1}=r\cdot|\mathcal{H}| . Given a family \mathcal{F} of r -graphs, an r -graph \mathcal{H} is \mathcal{F} -free if it does not contain any member of \mathcal{F} as a subgraph. The \ell_{p} -norm Turán number \mathrm{ex}_{\ell_{p}}(n,\mathcal{F}) of \mathcal{F} is the maximum \ell_{p} -norm of an \mathcal{F} -free r -graph \mathcal{H} on n vertices. The \ell_{p} -norm Turán density of \mathcal{F} is defined as \displaystyle\pi_{\ell_{p}}(\mathcal{F})\coloneqq\lim_{n\to\infty}\frac{\mathrm{ex}_{\ell_{p}}(n,\mathcal{F})}{n^{r-1+p}}. The existence of this limit follows from a simple averaging argument which can be found in such as [ KNS64 ] , [ BCL22b , Proposition 1.8] , and [ CIL+24 , Proposition 2.2] . Recall that the ordinary Turán number \mathrm{ex}(n,\mathcal{F}) of \mathcal{F} is the maximum number of edges in an n -vertex \mathcal{F} -free r -graph. The corresponding Turán density is defined as \pi(\mathcal{F})\coloneqq\lim_{n\to\infty}\mathrm{ex}(n,\mathcal{F})/\binom{n}{r} . Note that the \ell_{1} -norm Turán number of \mathcal{F} is simply r times its ordinary Turán number, and \pi(\mathcal{F})=(r-1)!\cdot\pi_{\ell_{1}}(\mathcal{F}) . For r=2 (i.e., graphs), the value of \pi(\mathcal{F}) is well understood thanks to the celebrated general theorem of Erdős–Stone [ ES46 ] (see also [ ES66 ] ), which extends Turán’s seminal theorem on complete graphs [ Tur41 ] to arbitrary graph families. The study of \pi_{\ell_{p}}(\mathcal{F}) for p>1 was initiated by Caro–Yuster [ CY00 , CY04 ] , and Erdős–Stone-type results in this setting were later obtained by Bollobás–Nikiforov [ BN12 ] . For r\geq 3 , determining \pi(\mathcal{F}) is already notoriously difficult in general, despite significant effort devoted to this area. For results up to 2011, we refer the reader to the excellent survey by Keevash [ Kee11 ] . Very recently, Balogh–Clemen–Lidický [ BCL22a , BCL22b ] initiated the study of \pi_{\ell_{p}}(\mathcal{F}) for hypergraph families. Among their many results, they determined the values of \pi_{\ell_{2}}(K_{4}^{3}) and \pi_{\ell_{2}}(K_{5}^{3}) , utilizing computer-assisted flag algebra computations, a powerful tool first introduced by [ Raz07 ] . These results are particularly interesting given the notorious difficulty of determining \pi(K_{\ell}^{3}) for any \ell\geq 4 , a problem originally posed by Turán [ Tur41 ] . The \ell_{p} -norm Turán problems for hypergraph have since been explored more systematically in recent works such as [ CL24 , CIL+24 , GLMP24 ] . In this paper, we focus on the following classical object in hypergraph Turán theory. For an integer \ell\geq 4 , the tight \ell -cycle C_{\ell}^{3} is the 3 -graph on [\ell] with edge set \displaystyle\big\{\{1,2,3\},~\cdots,~\{\ell-2,\ell-1,\ell\},~\{\ell-1,\ell,1\},~\{\ell,1,2\}\big\}, that is, we take all consecutive triples in the cyclic order on [\ell] . The tight \ell -cycle minus one edge C_{\ell}^{3-} is the 3 -graph on [\ell] with edge set \displaystyle\big\{\{1,2,3\},~\cdots,~\{\ell-2,\ell-1,\ell\},~\{\ell-1,\ell,1\}\big\}, that is, C_{\ell}^{3-} is obtained from C_{\ell}^{3} by removing one edge. If \ell\equiv 0\pmod{3} (i.e. \ell is divisible by 3 ), then both C_{\ell}^{3} and C_{\ell}^{3-} are 3 -partite and thus it holds that \pi(C_{\ell}^{3})=\pi(C_{\ell}^{3-})=0 by the classical general result of Erdős [ Erd64 ] . Partially inspired by the method used by Kamčev–Letzter–Pokrovskiy [ KLP24 ] for the Turán problem of C_{\ell}^{3} , Balogh–Luo [ BL24 ] proved that \pi(C_{\ell}^{3-})=1/4 for all sufficiently large \ell satisfying \ell\not\equiv 0\pmod{3} . Very recently, Lidický–Mattes–Pfender [ LMP24 ] , and independently Bodnár–León–Liu–Pikhurko [ BLLP24 ] proved that \pi(C_{\ell}^{3-})=1/4 for every \ell\geq 5 satisfying \ell\not\equiv 0\pmod{3} . Recall the following C_{\ell}^{3-} -free construction from [ MPS11 ] . For n\in\{0,1,2\} , the n -vertex T_{\mathrm{rec}} -construction is the empty 3 -graph on n vertices. For n\geq 3 , an n -vertex 3 -graph \mathcal{H} is a T_{\mathrm{rec}} -construction if there exists a partition V_{1}\cup V_{2}\cup V_{3}=V(\mathcal{H}) into non-empty parts such that \mathcal{H} is obtained from \mathcal{K}[V_{1},V_{2},V_{3}] , the complete 3 -partite 3 -graph with parts V_{1},V_{2},V_{3} , by adding a copy of T_{\mathrm{rec}} -construction into each V_{i} for i\in[3] . A 3 -graph is a T_{\mathrm{rec}} -subconstruction if it a subgraph of some T_{\mathrm{rec}} -construction. It is easy to see that every T_{\mathrm{rec}} -subconstruction is C_{\ell}^{3-} -free for every integer \ell\not\equiv 0\pmod{3} . Let t^{rec}_{2}(n) denote the maximum \ell_{2} -norm of an n -vertex T_{\mathrm{rec}} -construction. According to the definition, for every n\geq 3 , we have: \displaystyle t^{rec}_{2}(n)=\max\left\{n_{1}n_{2}n_{3}n+\sum_{i\in[3]}t^{rec}_{2}(n_{i})\colon\text{$n_{1}+n_{2}+n_{3}=n$ and $n_{i}\geq 1$ for $i\in[3]$}\right\}. Simple calculations show that t^{rec}_{2}(n)=(1/26+o(1))n^{4} . In [ BCL22a , Conjecture 3.5] , Balogh–Clemen–Lidický conjectured that the lower bound 1/26 , given by the 3 -partite recursive constructions described above, is also the upper bound for \pi_{\ell_{2}}(C_{5}^{3-}) , that is, \pi_{\ell_{2}}(C_{5}^{3-})=1/26 . The main result of this work is a confirmation of their conjecture, along with the establishment of an Erdős–Simonovits–type stability theorem [ Erd67 , Sim68 ] for C_{\ell}^{3-} -free 3 -graphs in the \ell_{2} -norm. Theorem 1.1 . Let \ell\geq 5 be an integer satisfying \ell\not\equiv 0\pmod{3} . Then \pi_{\ell_{2}}(C_{\ell}^{3-})=1/26 . Moreover, for every \varepsilon>0 there exist \delta and n_{0} such that the following holds for every n\geq n_{0} . Suppose that \mathcal{H} is an n -vertex C_{\ell}^{3-} -free 3 -graph with \left\lVert\mathcal{H}\right\rVert_{2}\geq(1/26-\delta)n^{4} . Then \mathcal{H} is a T_{\mathrm{rec}} -subconstruction after removing at most \varepsilon n^{3} edges. Our proofs crucially use the flag algebra machinery developed by Razborov [ Raz07 ] and are computer-assisted. More specifically, we adopt the strategy used in the previous work [ BLLP24 ] for determining the Turán density of C_{5}^{3-} , which is inspired by the strategy of Balogh–Hu–Lidický–Pfender used in [ BHLP16 ] for determining the inducibility of the 5 -cycle C_{5} (where asymptotically extremal graphs are also obtained via a recursive construction). Some standard reductions (see the discussion in Section 2 )

Read the complete text