Asymptotics of the hypergraph bipartite Turán problem

DOI10.1007/S00493-023-00019-6MaRDI QIDQ6081375zbMATH OpenFDO

Authors Domagoj Bradač, Lior Gishboliner, Oliver Janzer, Benny Sudakov

Publication date 4 October 2023

Published in Combinatorica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

bipartite graphshypergraphsTurán problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Abstract: For positive integers $s,t,r$, let $K_{s,t}^{(r)}$ denote the $r$-uniform hypergraph whose vertex set is the union of pairwise disjoint sets $X,Y_1,dots,Y_t$, where $|X|=s$ and $|Y_1|=dots=|Y_t|=r-1$, and whose edge set is $xcup{Y}_i:xinX,1leqileqt$. The study of the Tur'an function of $K_{s,t}^{(r)}$ received considerable interest in recent years. Our main results are as follows. First, we show that �egin{equation} mathrm{ex}(n,K_{s,t}^{(r)}) = O_{s,r}(t^{frac{1}{s-1}}n^{r - frac{1}{s-1}}) end{equation} for all $s,tgeq2$ and $rgeq3$, improving the power of $n$ in the previously best bound and resolving a question of Mubayi and Verstra"ete about the dependence of $mathrmex(n,K_{2,t}^{(3)})$ on $t$. Second, we show that this upper bound is tight when $r$ is even and $tggs$. This disproves a conjecture of Xu, Zhang and Ge. Third, we show that the above upper bound is not tight for $r=3$, namely that $mathrmex(n,K_{s,t}^{(3)})=O_{s,t}(n^{3-frac1s-1-varepsilo{n}_s})$ (for all $sgeq3$). This indicates that the behaviour of $mathrmex(n,K_{s,t}^{(r)})$ might depend on the parity of $r$. Lastly, we prove a conjecture of Ergemlidze, Jiang and Methuku on the hypergraph analogue of the bipartite Tur'an problem for graphs with bounded degrees on one side. Our tools include a novel twist on the dependent random choice method as well as a variant of the celebrated norm graphs constructed by Koll'ar, R'onyai and Szab'o.

Recommendations

• Some extremal results on hypergraph Turán problems
• New bounds for a hypergraph bipartite Turán problem
• Some tight lower bounds for Turán problems via constructions of multi-hypergraphs
• Some Exact Results and New Asymptotics for Hypergraph Turán Numbers
• A hypergraph extension of the bipartite Turán problem

Cited in

(2)

• Extremal Problems for Hypergraph Blowups of Trees
• A hypergraph bipartite Turán problem with odd uniformity

This page was built for publication: Asymptotics of the hypergraph bipartite Turán problem

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