Turán number of special four cycles in triple systems

DOI10.1016/J.DISC.2021.112667MaRDI QIDQ2237241zbMATH OpenOpenAlexFDO

Authors Attila Sali, Zoltán Füredi, András Gyárfás

Publication date 27 October 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2103.09774

zbMATH Keywords

extremal combinatoricstriple systemTurán number

Mathematics Subject Classification ID

Triple systems (05B07) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35)

Abstract: A {em special four-cycle } $F$ in a triple system consists of four triples {em inducing } a $C_4$. This means that $F$ has four special vertices $v_1,v_2,v_3,v_4$ and four triples in the form $w_i{v}_i{v}_{i+1}$ (indices are understood $pmod4$) where the $w_j$s are not necessarily distinct but disjoint from $v_1,v_2,v_3,v_4$. There are seven non-isomorphic special four-cycles, their family is denoted by $calF$. Our main result implies that the Tur'an number $extex(n,calF)=Theta(n^{3/2})$. In fact, we prove more, $extex(n,F_1,F_2,F_3)=Theta(n^{3/2})$, where the $F_i$-s are specific members of $calF$. This extends previous bounds for the Tur'an number of triple systems containing no Berge four cycles. We also study $extex(n,calA)$ for all $calAsubseteqcalF$. For 16 choices of $calA$ we show that $extex(n,calA)=Theta(n^{3/2})$, for 92 choices of $calA$ we find that $extex(n,calA)=Theta(n^2)$ and the other 18 cases remain unsolved.

Review text

A Berge four-cycle in a triple system has four distinct vertices \(v_1\), \(v_2\), \(v_3\), \(v_4\) and four distinct triples \(\{ \{w_1, v_1, v_2\}\), \(\{w_2, v_2, v_3\}\), \(\{w_3, v_3, v_4\}\), \(\{w_4, v_4, v_1\}\}\); the \(w_j\)s may coincide with the \(v_j\)s or with each other. A special four-cycle is a Berge four-cycle for which \(\{v_1, v_2, v_3, v_4\} \cap \{w_1, w_2, w_3, w_4\} = \emptyset\), but the \(w_j\)s need not be distinct. The special four-cycle \(F_1\) has all \(w_j\)s distinct; \(F_2\) has all \(w_j\)s equal; \(F_3\) has \(w_1 = w_2 \neq w_3 = w_4\); and \(F_4\) is the Pasch configuration (\(w_1 = w_3 \neq w_2 = w_4\)). The family of all seven non-isomorphic special four-cycles is denoted by \(\mathcal F\). In this paper, it is shown that \(\operatorname{ex}(n, \{F_1, F_2, F_3\}) = \Theta(n^{3/2})\) and that the Turán number \(\operatorname{ex}(n, {\mathcal F}) = \Theta(n^{3/2})\). The paper undertakes the classification of \(\operatorname{ex}(n, {\mathcal A})\) for all \({\mathcal A} \subseteq {\mathcal F}\). In addition to the known results that \(\operatorname{ex}(n, \emptyset) = \Theta(n^3)\) and \(\operatorname{ex}(n, F_2) = \Theta(n^{5/2})\), it is shown that \(\operatorname{ex}(n, {\mathcal A}) = \Theta(n^{3/2})\) for 16 choices of \({\mathcal A}\) and \(\operatorname{ex}(n, {\mathcal A}) = \Theta(n^2)\) for 92 choices of \({\mathcal A}\). The remaining 18 cases are not resolved.

Recommendations

• The Turán Number of Berge K₄ in Triple Systems
• Linear Turán numbers of acyclic triple systems
• On Turán densities of small triple graphs
• On hypergraphs with every four points spanning at most two triples
• Extremal problems for triple systems

Cites work

• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Extremal problems for triple systems
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• Hypergraphs in which all disjoint pairs have distinct unions
• On 3-uniform hypergraphs without a cycle of a given length
• On coloring graphs to maximize the proportion of multicolored k-edges
• On extremal problems of graphs and generalized graphs
• Some Exact Results and New Asymptotics for Hypergraph Turán Numbers

Cited in

(2)

• Linear Turán numbers of acyclic triple systems
• The Turán Number of Berge K₄ in Triple Systems

This page was built for publication: Turán number of special four cycles in triple systems

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