Abstract
Let t be an integer such that t≥2. Let K2,t(3) denote the triple system consisting of the 2t triples {a,xi,yi}, {b,xi,yi} for 1≤i≤t, where the elements a,b,x1,x2,…,xt, y1,y2,…,yt are all distinct. Let ex(n,K2,t(3)) denote the maximum size of a triple system on n elements that does not contain K2,t(3). This function was studied by Mubayi and Verstraëte [9], where the special case t=2 was a problem of Erdős [1] that was studied by various authors [3,9,10]. Mubayi and Verstraëte proved that ex(n,K2,t(3))<t4(n2) and that for infinitely many n, ex(n,K2,t(3))≥[Formula presented](n2). These bounds together with a standard argument show that g(t):=limn→∞ex(n,K2,t(3))/(n2) exists and that [Formula presented]≤g(t)≤t4. Addressing the question of Mubayi and Verstraëte on the growth rate of g(t), we prove that as t→∞, g(t)=Θ(t1+o(1)).
Original language | English (US) |
---|---|
Article number | 105299 |
Journal | Journal of Combinatorial Theory. Series A |
Volume | 176 |
DOIs | |
State | Published - Nov 2020 |
Externally published | Yes |
Keywords
- Bipartite Turán
- Degenerate problem
- Extremal hypergraphs
- Hypergraph Turán problem
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics