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
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?)


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
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

DOI: https://doi.org/10.1090/proc/15042
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