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

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 Press. 77-81

[10] Erdős P. Rosenstiehl P. Some recent results on extremal problem in graph theory. Theory of Graphs. 1967 New York: Gordon and Breach. 117-123

[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, 34 241-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

[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$-flower. J. Graph Theory. 2018, 89 26-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)