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

HTML articles powered by AMS MathViewer

- by Benny Sudakov and István Tomon PDF
- Proc. Amer. Math. Soc.
**148**(2020), 2811-2818 Request permission

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

- Noga Alon, Michael Krivelevich, and Benny Sudakov,
*Turán numbers of bipartite graphs and related Ramsey-type questions*, Combin. Probab. Comput.**12**(2003), no. 5-6, 477–494. Special issue on Ramsey theory. MR**2037065**, DOI 10.1017/S0963548303005741 - Noga Alon, Lajos Rónyai, and Tibor Szabó,
*Norm-graphs: variations and applications*, J. Combin. Theory Ser. B**76**(1999), no. 2, 280–290. MR**1699238**, DOI 10.1006/jctb.1999.1906 - M. Balko, D. Gerbner, D. Y. Kang, Y. Kim, and C. Palmer,
*Hypergraph based Berge hypergraphs*, arXiv preprint, arXiv:1908.00092, 2019. - David Conlon, Jacob Fox, and Benny Sudakov,
*Short proofs of some extremal results II*, J. Combin. Theory Ser. B**121**(2016), 173–196. MR**3548291**, DOI 10.1016/j.jctb.2016.03.005 - D. Conlon, O. Janzer, and J. Lee,
*More on the extremal number of subdivisions*, preprint, arXiv:1903.1063, 2019. - D. Conlon and J. Lee,
*On the extremal number of subdivisions*, Int. Math. Res. Not. (to appear). - P. Erdős,
*On extremal problems of graphs and generalized graphs*, Israel J. Math.**2**(1964), 183–190. MR**183654**, DOI 10.1007/BF02759942 - Paul Erdős,
*Problems and results in combinatorial analysis and graph theory*, Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), 1988, pp. 81–92. MR**975526**, DOI 10.1016/0012-365X(88)90196-3 - P. Erdős and M. Simonovits,
*A limit theorem in graph theory*, Studia Sci. Math. Hungar.**1**(1966), 51–57. MR**205876** - P. Erdös and A. H. Stone,
*On the structure of linear graphs*, Bull. Amer. Math. Soc.**52**(1946), 1087–1091. MR**18807**, DOI 10.1090/S0002-9904-1946-08715-7 - Zoltán Füredi,
*On a Turán type problem of Erdős*, Combinatorica**11**(1991), no. 1, 75–79. MR**1112277**, DOI 10.1007/BF01375476 - A. Grzesik, O. Janzer, and Z. L. Nagy,
*The Turán number of blow-ups of tree*, preprint, arXiv:1904.07219, 2019. - W. T. Gowers,
*Hypergraph regularity and the multidimensional Szemerédi theorem*, Ann. of Math. (2)**166**(2007), no. 3, 897–946. MR**2373376**, DOI 10.4007/annals.2007.166.897 - Oliver Janzer,
*Improved bounds for the extremal number of subdivisions*, Electron. J. Combin.**26**(2019), no. 3, Paper No. 3.3, 6. MR**3982312** - T. Jiang, J. Ma, and L. Yepremyan,
*On Turán exponents of bipartite graphs*, preprint, arXiv:1806.02838, 2018. - T. Jiang and Y. Qiu,
*Turán numbers of bipartite subdivisions*, preprint, arXiv:1905.08994, 2019. - D. Y. Kang, J. Kim, and H. Liu,
*On the rational Turán exponents conjecture*, preprint, arXiv:1811.06916, 2018. - János Kollár, Lajos Rónyai, and Tibor Szabó,
*Norm-graphs and bipartite Turán numbers*, Combinatorica**16**(1996), no. 3, 399–406. MR**1417348**, DOI 10.1007/BF01261323 - T. Kövari, V. T. Sós, and P. Turán,
*On a problem of K. Zarankiewicz*, Colloq. Math.**3**(1954), 50–57. MR**65617**, DOI 10.4064/cm-3-1-50-57 - Brendan Nagle, Vojtěch Rödl, and Mathias Schacht,
*The counting lemma for regular $k$-uniform hypergraphs*, Random Structures Algorithms**28**(2006), no. 2, 113–179. MR**2198495**, DOI 10.1002/rsa.20117 - F. P. Ramsey,
*On a Problem of Formal Logic*, Proc. London Math. Soc. (2)**30**(1929), no. 4, 264–286. MR**1576401**, DOI 10.1112/plms/s2-30.1.264

## 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
- © Copyright 2020 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**148**(2020), 2811-2818 - MSC (2010): Primary 05C35
- DOI: https://doi.org/10.1090/proc/15042
- MathSciNet review: 4099770