Some tight lower bounds for Turán problems via constructions of multi-hypergraphs

DOI10.1016/J.EJC.2020.103161zbMath1447.05150arXiv1907.11909OpenAlexW2966441497MaRDI QIDQ2198988

Gennian Ge, Zixiang Xu, Tao Zhang

Publication date: 15 September 2020

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Recently, several hypergraph Tur'{a}n problems were solved by the powerful random algebraic method. However, the random algebraic method usually requires some parameters to be very large, hence we are concerned about how these Tur'{a}n numbers depend on such large parameters of the forbidden hypergraphs. In this paper, we determine the dependence on such specified large constant for several hypergraph Tur'{a}n problems. More specifically, for complete $r$-partite $r$-uniform hypergraphs, we show that if $s_r$ is sufficiently larger than $s_1,s_2,ldots,s_{r-1},$ then ${\displaystyle }$ extup{ex}_{r}(n,K_{s_{1},s_{2},ldots,s_{r}}^{(r)})=Theta(s_{r}^{frac{1}{s_{1}s_{2}cdots s_{r-1}}}n^{r-frac{1}{s_{1}s_{2}cdots s_{r-1}}}).${\displaystyle }$ For complete bipartite $r$-uniform hypergraphs, we prove that if $s$ is sufficiently larger than $t,$ we have ${\displaystyle }$ extup{ex}_{r}(n,K_{s,t}^{(r)})=Theta(s^{frac{1}{t}}n^{r-frac{1}{t}}).${\displaystyle }$ In particular, our results imply that the famous KH{o}v'{a}ri--S'{o}s--Tur'{a}n's upper bound $extupex(n,K_{s,t})=O(t^{frac1s}{n}^{2-frac1s})$ has the correct dependence on large $t$. The main approach is to construct random multi-hypergraph via a variant of random algebraic method.

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

zbMATH Keywords

hypergraph Turán problemsrandom multi-hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65)

Cites Work

• Unnamed Item
• Turán numbers for \(K_{s,t}\)-free graphs: topological obstructions and algebraic constructions
• Pentagons vs. triangles
• On a class of degenerate extremal graph problems
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Norm-graphs: Variations and applications
• Graphs without theta subgraphs
• Rational exponents in extremal graph theory
• Some extremal results on complete degenerate hypergraphs
• Cycles of given lengths in hypergraphs
• A hypergraph extension of the bipartite Turán problem
• Cycles of even length in graphs
• General lemmas for Berge-Turán hypergraph problems
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Norm-graphs and bipartite Turán numbers
• Hypergraphs with No Cycle of a Given Length
• Extremal problems for cycles in graphs
• Some Exact Results and New Asymptotics for Hypergraph Turán Numbers
• Triangle-Free Hypergraphs
• Random algebraic construction of extremal graphs
• A new series of dense graphs of high girth
• Graphs from Generalized Kac--Moody Algebras
• Graphs with few paths of prescribed length between any two vertices
• Hypergraphs with Few Berge Paths of Fixed Length between Vertices
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• Extremal Results for Berge Hypergraphs
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• On the structure of linear graphs
• Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs

Related Items (3)

Extremal graphs without exponentially small bicliques ⋮ A polynomial resultant approach to algebraic constructions of extremal graphs ⋮ Turán numbers of theta graphs

This page was built for publication: Some tight lower bounds for Turán problems via constructions of multi-hypergraphs