Turán number of bipartite graphs with no 𝐾_{𝑡,𝑡}

Sudakov, Benny; Tomon, István

doi:10.1090/proc/15042

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