Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Turán number of bipartite graphs with no $K_{t,t}$


Authors: Benny Sudakov and István Tomon
Journal: Proc. Amer. Math. Soc. 148 (2020), 2811-2818
MSC (2010): Primary 05C35
DOI: https://doi.org/10.1090/proc/15042
Published electronically: April 9, 2020
MathSciNet review: 4099770
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The extremal number of a graph $H$, denoted by $\textrm {ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices that does not contain $H$. The celebrated Kővári-Sós-Turán theorem says that for a complete bipartite graph with parts of size $t\leq s$ the extremal number is $\textrm {ex}(K_{s,t})=O(n^{2-1/t})$. It is also known that this bound is sharp if $s>(t-1)!$. In this paper, we prove that if $H$ is a bipartite graph such that all vertices in one of its parts have degree at most $t$ but $H$ contains no copy of $K_{t,t}$, then $\textrm {ex}(n,H)=o(n^{2-1/t})$. This verifies a conjecture of Conlon, Janzer, and Lee.


References [Enhancements On Off] (What's this?)

References

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C35

Retrieve articles in all journals with MSC (2010): 05C35


Additional Information

Benny Sudakov
Affiliation: Department of Mathematics, ETH Zurich, Rämistrasse 101, HG G 33.4, 8092 Zurich, Switzerland
MR Author ID: 602546
Email: benjamin.sudakov@math.ethz.ch

István Tomon
Affiliation: Department of Mathematics, ETH Zurich, Rämistrasse 101, HG G 33.4, 8092 Zurich, Switzerland
Email: istvan.tomon@math.ethz.ch

Received by editor(s): October 24, 2019
Published electronically: April 9, 2020
Additional Notes: Research supported by SNSF grant 200021-175573.
Communicated by: Patricia Hersh
Article copyright: © Copyright 2020 American Mathematical Society