Asymptotics for the Turán number of Berge-\(K_{2,t}\)
From MaRDI portal
Publication:2312610
DOI10.1016/J.JCTB.2019.01.001zbMath1415.05126arXiv1705.04134OpenAlexW2908866483MaRDI QIDQ2312610
Dániel Gerbner, Máté Vizer, Abhishek Methuku
Publication date: 17 July 2019
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: Let $F$ be a graph. A hypergraph is called Berge-$F$ if it can be obtained by replacing each edge of $F$ by a hyperedge containing it. Let $mathcal{F}$ be a family of graphs. The Tur'an number of Berge-$mathcal{F}$ is the maximum possible number of edges in an $r$-uniform hypergraph on $n$ vertices containing no Berge-$F$ as a subhypergraph (for every $F in mathcal{F}$) and is denoted by $ex_r(n,mathcal{F})$. We determine the asymptotics for the Tur'an number of Berge-$K_{2,t}$ by showing $$ex_3(n,K_{2,t})=frac{1}{6}(t-1)^{3/2} cdot n^{3/2}(1+o(1))$$ for any given $t ge 7$. We study the analogous question for linear hypergraphs and show that $$ex_3(n,{C_2, K_{2,t}}) = frac{1}{6}sqrt{t-1} cdot n^{3/2}(1+o_{t}(1)).$$ We also prove general upper and lower bounds on the Tur'an numbers of a class of graphs including $ex_r(n, K_{2,t})$, $ex_r(n,{C_2, K_{2,t}})$, and $ex_r(n, C_{2k})$ for $r ge 3$. Our bounds improve results of Gerbner and Palmer, F"uredi and "Ozkahya, Timmons, and provide a new proof of a result of Jiang and Ma.
Full work available at URL: https://arxiv.org/abs/1705.04134
Cites Work
- Unnamed Item
- Unnamed Item
- Turán problems and shadows. II: Trees
- Hypergraphs with no cycle of length 4
- 3-uniform hypergraphs avoiding a given odd cycle
- Turán problems and shadows. I: Paths and cycles
- On 3-uniform hypergraphs without a cycle of a given length
- Forbidden Berge hypergraphs
- On the maximum size of connected hypergraphs without a path of given length
- Hypergraph extensions of the Erdős-Gallai theorem
- Pentagons vs. triangles
- Norm-graphs: Variations and applications
- Nearly perfect matchings in regular simple hypergraphs
- On hypergraphs of girth five
- The maximum number of cliques in graphs without long cycles
- On \(r\)-uniform linear hypergraphs with no Berge-\(K_{2,t}\)
- An Erdős-Gallai type theorem for uniform hypergraphs
- 3-uniform hypergraphs and linear cycles
- Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs
- Cycles of given lengths in hypergraphs
- Cycles of even length in graphs
- New asymptotics for bipartite Turán numbers
- A survey of forbidden configuration results
- General lemmas for Berge-Turán hypergraph problems
- Forbidden families of minimal quadratic and cubic configurations
- Norm-graphs and bipartite Turán numbers
- Hypergraphs with No Cycle of a Given Length
- A survey of Turán problems for expansions
- Turán Problems and Shadows III: Expansions of Graphs
- Extremal Results for Berge Hypergraphs
- The History of Degenerate (Bipartite) Extremal Graph Problems
- On a problem of K. Zarankiewicz
- Many \(T\) copies in \(H\)-free graphs
Related Items (36)
The exact linear Turán number of the sail ⋮ Turán numbers for hypergraph star forests ⋮ Nearly-Regular Hypergraphs and Saturation of Berge Stars ⋮ The Turán number of Berge-matching in hypergraphs ⋮ Multicolor Turán numbers ⋮ A note on the uniformity threshold for Berge hypergraphs ⋮ Spectral Radius on Linear $r$-Graphs without Expanded $K_{r+1}$ ⋮ A note on the Tur\'an number of a Berge odd cycle ⋮ Forbidding \(K_{2,t}\) traces in triple systems ⋮ 3-uniform hypergraphs without a cycle of length five ⋮ On Berge-Ramsey problems ⋮ On the maximum number of copies of H in graphs with given size and order ⋮ Linearity of saturation for Berge hypergraphs ⋮ Some tight lower bounds for Turán problems via constructions of multi-hypergraphs ⋮ On Ramsey numbers of 3-uniform Berge cycles ⋮ $t$-Wise Berge and $t$-Heavy Hypergraphs ⋮ The Turán Number of Berge K_4 in Triple Systems ⋮ A linear hypergraph extension of the bipartite Turán problem ⋮ Turán number of special four cycles in triple systems ⋮ General lemmas for Berge-Turán hypergraph problems ⋮ Turán numbers for Berge-hypergraphs and related extremal problems ⋮ Saturation of Berge hypergraphs ⋮ A stability result for Berge-\( K_{3 , t}r\)-graphs and its applications ⋮ The Turán number of Berge book hypergraphs ⋮ Anti-Ramsey Numbers of Paths and Cycles in Hypergraphs ⋮ A note on stability results for Berge-\( K_{s , t}\) hypergraphs ⋮ Ramsey Problems for Berge Hypergraphs ⋮ Spectral extremal results for hypergraphs ⋮ Hypergraph based Berge hypergraphs ⋮ Hypergraphs with Few Berge Paths of Fixed Length between Vertices ⋮ Counting copies of a fixed subgraph in \(F\)-free graphs ⋮ Avoiding long Berge cycles: the missing cases k = r + 1 and k = r + 2 ⋮ Partitioning the power set of \([n\) into \(C_k\)-free parts] ⋮ On the weight of Berge-\(F\)-free hypergraphs ⋮ Generalized Turán problems for complete bipartite graphs ⋮ A linear hypergraph extension of Turán's theorem
This page was built for publication: Asymptotics for the Turán number of Berge-\(K_{2,t}\)
