Open access
Date
2023-06Type
- Journal Article
Abstract
For positive integers s, t, r, let K(r)s,t denote the r-uniform hypergraph whose vertex set is the union of pairwise disjoint sets X,Y1,…,Yt, where |X|=s and |Y1|=⋯=|Yt|=r−1, and whose edge set is {{x}∪Yi:x∈X,1≤i≤t}. The study of the Turán function of K(r)s,t received considerable interest in recent years. Our main results are as follows. First, we show that ex(n,K(r)s,t)=Os,r(t1s−1nr−1s−1)(1) for all s,t≥2 and r≥3, improving the power of n in the previously best bound and resolving a question of Mubayi and Verstraëte about the dependence of ex(n,K(3)2,t) on t. Second, we show that (1) is tight when r is even and t≫s. This disproves a conjecture of Xu, Zhang and Ge. Third, we show that (1) is not tight for r=3, namely that ex(n,K(3)s,t)=Os,t(n3−1s−1−εs) (for all s≥3). This indicates that the behaviour of ex(n,K(r)s,t) 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án 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ár, Rónyai and Szabó. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000621885Publication status
publishedExternal links
Journal / series
CombinatoricaVolume
Pages / Article No.
Publisher
SpringerSubject
hypergraphs; bipartite graphs; Turan problemOrganisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)
20-1 FEL-35 - Problems in Extremal Combinatorics (ETHZ)
More
Show all metadata