Turán Number of Nonbipartite Graphs and the Product Conjecture

Abstract

The decomposition family of a family of graphs often helps us to determine the error term in the well-known Erdős–Stone–Simonovits theorem. We study the Turán number of families of nonbipartite graphs such that their decomposition families contain a matching and a star. To be precisely, we prove tight bounds on the Turán number of such families of graphs. Moreover, we find a graph which is a counterexample to an old conjecture of Erdős and Simonovits, while all previous counterexamples are families of graphs.

Keywords

Turán number / Decomposition family / Matching / Star / Product conjecture / 05C35 / 05D99

References

[1] Abbott HL, Hanson D, Sauer H. Intersection theorems for systems of sets. J. Combin. Theory Ser. A. 1972, 12: 381-389.

[2] Balachandran N, Khare N. Graphs with restricted valency and matching number. Discrete Math.. 2009, 309: 4176-4180.

[3] Bollobás B. Extremal Graph Theory. 1978, New York, Academic Press

[4] Bukh B, Conlon D. Rational exponents in extremal graph theory. J. Eur. Math. Soc.. 2018, 20: 1747-1757.

[5] Chen G, Gould RJ, Pfender F, Wei B. Extremal graphs for intersecting cliques. J. Combin. Theory Ser. B. 2003, 89: 159-171.

[6] Chi C, Yuan L. The Turán number for the edge blow-up of trees: the missing case. Discrete Math.. 2023, 346(6): 113370.

[7] Chvátal V, Hanson D. Degrees and matchings. J. Combin. Theory Ser. B. 1976, 20: 128-138.

[8] Conlon, D., Janzer, O., Lee, J.: More on the extremal number of subdivisions, to appear in Combinatorica

[9] Erdős P. Erdős P, Katona G. On some new inequalities concering extremal properties of graphs. Theory of Graphs. 1968, New York, Academic Press77-81

[10] Erdős P. Rosenstiehl P. Some recent results on extremal problem in graph theory. Theory of Graphs. 1967, New York, Gordon and Breach117123

[11] Erdős P, Simonovits M. A limit theorem in graph theory. Studia Sci. Math. Hungar.. 1966, 1: 51-57

[12] Erdős P, Stone AH. On the structure of linear graphs. Bull. Amer. Math.. 1946, 52: 1089-1091

[13] Erdős P, Füredi Z, Gould RJ, Gunderson DS. Extremal graphs for intersecting triangles. J. Comb. Theory Ser. B. 1995, 64: 89-100.

[14] Füredi, Z., Simonovits, M.: The history of degenerate (bipartite) extremal graph problems. In: Erdős centennial, pp. 169–264 (2013)

[15] Gallai T. Neuer Beweis eines Tutte’schen Satzes, Magyar Tud. Akad. Mat. Kutató Int. Közl.. 1963, 8: 135-139

[16] Griggs JR, Simonovits M, Thomas GR. Extremal graphs with bounded densities of small subgraphs. J. Graph Theory. 1998, 29(3): 185-207.

[17] Hou X, Qiu Y, Liu B. Extremal graph for intersecting odd cycles. Electron. J. Combin.. 2016, 23: 9.

[18] Janzer O. The extremal number of the subdivisions of the complete bipartite graph. SIAM J. Discrete Math.. 2020, 34241-250.

[19] Jiang T. Qiu, Yu Many Turán exponents via subdivisions. Combin. Probab. Comput.. 2023, 32(1): 134-150.

[20] Jiang T, Jiang Z. Ma, Jie Negligible obstructions and Turán exponents. Ann. Appl. Math.. 2022, 38(3): 356-384.

[21] Jiang T, Ma J. Yepremyan, Liana On Turán exponents of bipartite graphs. Combin. Probab. Comput.. 2022, 31(2): 333-344.

[22] Kang DY, Kim J, Liu H. On the rational Turán exponents conjecture. J. Combin. Theory Ser. B. 2021, 148: 149-172.

[23] Ni Z, Kang L, Shan E, Zhu H. Extremal graphs for blow-ups of keyrings. Graphs Combin.. 2020, 36: 1827-1853.

[24] Simonovits, M.: A method for solving extremal problems in graph theory, stability problems. In: Theory of Graphs, Academic Press, New York, pp. 279–319 (1968)

[25] Simonovits, M.: Extremal problems and graph products, Studies in Pure Mathematics, pp. 669–680, (dedicated to the memory of P. Turán), Akadémiai Kiadó and Birkhäuser Verlag (1982)

[26] Simonovits M. The extremal graph problem of the icosahedron. J. Combin. Theory Ser. B. 1974, 17: 69-79.

[27] Turán P. On an extremal problem in graph theory (in Hungrarian). Mat. es Fiz. Lapok.. 1941, 48: 436-452

[28] Wang A, Hou X, Liu B, Ma Y. The Turán number for the edge blow-up of trees. Discrete Math.. 2021, 344. 112627

[29] Yuan L. Extremal graphs of the pth power of paths. Eur. J. Combin.. 2022, 104: 12.

[30] Yuan L. Extremal graphs for the k\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$k$$\end{document}-flower. J. Graph Theory. 2018, 8926-39.

[31] Yuan L. Extremal graphs for odd wheels. J. Graph Theory. 2021, 98(4): 691-707.

[32] Yuan L. Extremal graphs for edge blow-up of graphs. J. Combin. Theory Ser. B. 2022, 152: 379-398.

[33] Zhu H, Kang L, Shan E. Extremal graphs for odd-ballooning of paths and cycles. Gr. Combin.. 2020, 36: 755-766.

Funding

National Natural Science Foundation of China(11601380)

Anhui Provincial Natural Science Foundation(2208085J22)

Science and Technology Commission of Shanghai Municipality(22DZ2229014)

RIGHTS & PERMISSIONS

School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature