Exact Results for Some Extremal Problems on Expansions I

Abstract

The expansion of a graph F, denoted by $F^3$, is the 3-graph obtained from F by adding a new vertex to each edge such that different edges receive different vertices. We establish a stability version of a theorem by Kostochka–Mubayi–Verstraëte (Kostochka et al in J Combin Theory Ser B 122:457–478, 2017) and demonstrate two applications of it by establishing tight upper bounds for large $n:$

•	The maximum number of edges in an n-vertex 3-graph that does not contain $T^3$ for certain class ${\mathcal {T}}$ of trees, thereby (partially) sharpening the asymptotic result of Kostochka–Mubayi–Verstraëte.
•	The minimum number of colors needed to color the complete n-vertex 3-graph to ensure the existence of a rainbow copy of $F^3$ when F is a graph obtained from some tree $T\in {\mathcal {T}}$ by adding a new edge, thereby extending anti-Ramsey results on $P_{2t}^3$ by Gu–Li–Shi and $C_{2t}^3$ by Tang–Li–Yan.

We introduce a framework that utilizes tools from Extremal Set Theory for solving certain generalized Turán problems. More specifically, we establish a parallel of the stability theorem above in generalized Turán problems. Using this stability theorem, we determine, for large n, the maximum number of triangles in an n-vertex graph that does not contain the shadow of $C_{k}^3$ or $T^3$ for $T\in {\mathcal {T}}$, thus answering a question of Lv et al. on generalized Turán problems.

Keywords

Hypergraph Turán problem / Anti-Ramsey problem / Generalized Turán problem / Expansion of trees / Linear cycles / Triple systems / Stability

References

[1] AlonN, FischerE, KrivelevichM, SzegedyM. Efficient testing of large graphs. Combinatorica, 2000, 20(4): 451-476

[2] AlonN, ShikhelmanC. Many $T$ copies in $H$-free graphs. J. Combin. Theory Ser. B, 2016, 121: 146-172

[3] BollobásB, DaykinDE, ErdősP. Sets of independent edges of a hypergraph. Quart. J. Math. Oxford Ser. (2), 1976, 27(105): 25-32

[4] BondyJA, MurtyUSRGraph theory with applications, 1976, New York. American Elsevier Publishing Co. Inc,.

[5] BushawN, KettleN. Turán numbers for forests of paths in hypergraphs. SIAM J. Discrete Math., 2014, 28(2): 711-721

[6] ErdősP. On the number of complete subgraphs contained in certain graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl., 1962, 7: 459-464

[7] Erdős, P.: Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pp. 29–36. Publ. House Czech. Acad. Sci., Prague, (1964)

[8] Erdős, P.: A problem on independent $r$-tuples. Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 8, 93–95, (1965)

[9] Erdős, P., Simonovits, M., Sós, V. T.: Anti-Ramsey theorems. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, Colloq. Math. Soc. János Bolyai, 10, 633–643. (1975)

[10] FoxJ . A new proof of the graph removal lemma. Ann. of Math., 2011, 174(1): 561-579

[11] FranklP. Improved bounds for Erdős’ matching conjecture. J. Combin. Theory Ser. A, 2013, 120(5): 1068-1072

[12] FranklP, FürediZ. Exact solution of some Turán-type problems. J. Combin. Theory Ser. A, 1987, 45(2): 226-262

[13] FranklP, KupavskiiA. Two problems on matchings in set families–in the footsteps of Erdős and Kleitman. J. Combin. Theory Ser. B, 2019, 138: 286-313

[14] FujitaS, MagnantC, OzekiK. Rainbow generalizations of Ramsey theory: a survey. Graphs Combin., 2010, 26(1): 1-30

[15] FürediZ. Linear trees in uniform hypergraphs. Eur. J. Combin., 2014, 35: 264-272

[16] FürediZ, JiangT. Hypergraph Turán numbers of linear cycles. J. Combin. Theory Ser. A, 2014, 123: 252-270

[17] Füredi, Z., Jiang, T.: Turán numbers of hypergraph trees. arXiv preprint arXiv:1505.03210, (2015)

[18] FürediZ, JiangT, KostochkaA, MubayiD, VerstraëteJ. Hypergraphs not containing a tight tree with a bounded trunk. SIAM J. Discrete Math., 2019, 33(2): 862-873

[19] Füredi, Z., Jiang, T., Kostochka, A., Mubayi, D., Verstraëte, J.: Tight paths in convex geometric hypergraphs. Adv. Comb., pages Paper No. 1, 14, (2020)

[20] FürediZ, JiangT, SeiverR. Exact solution of the hypergraph Turán problem for $k$-uniform linear paths. Combinatorica, 2014, 34(3): 299-322

[21] Füredi, Z., Kostochka, A.: Turán number for bushes. arXiv preprint arXiv:2307.04932, (2023)

[22] GuR, LiJ, ShiY. Anti-Ramsey numbers of paths and cycles in hypergraphs. SIAM J. Discrete Math., 2020, 34(1): 271-307

[23] Gu, R., Li, X., Shi, Y.: Hypergraph Turán numbers of vertex disjoint cycles. arXiv preprint arXiv:1305.5372, (2013)

[24] GuoM, LuH, PengX. Anti-Ramsey Number of Matchings in 3-uniform Hypergraphs. SIAM J. Discrete Math., 2023, 37(3): 1970-1987

[25] HallP. On Representatives of Subsets. J. London Math. Soc., 1935, 10(1): 26-30

[26] HuangH, LohP-S, SudakovB. The size of a hypergraph and its matching number. Combin. Probab. Comput., 2012, 21(3): 442-450

[27] Katona, G.: A theorem of finite sets. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 187–207. Academic Press, New York-London, (1968)

[28] KönigD. Graphs and matrices. Mat. és Fizikai Lapok, 1931, 38: 116-119

[29] KostochkaA, MubayiD, VerstraëteJ. Turán problems and shadows I: Paths and cycles. J. Combin. Theory Ser. A, 2015, 129: 57-79

[30] KostochkaA, MubayiD, VerstraëteJ. Turán problems and shadows III: expansions of graphs. SIAM J. Discrete Math., 2015, 29(2): 868-876

[31] KostochkaA, MubayiD, VerstraëteJ. Turán problems and shadows II: Trees. J. Combin. Theory Ser. B, 2017, 122: 457-478

[32] KövariT, SósVT, TuránP. On a problem of K. Zarankiewicz. Colloq. Math., 1954, 3: 50-57

[33] Kruskal, J. B.: The number of simplices in a complex. In Mathematical optimization techniques, pp. 251–278. Univ. California Press, Berkeley-Los Angeles, Calif., (1963)

[34] LiT, TangY, YanG, ZhouW. Rainbow Turán numbers of matchings and forests of hyperstars in uniform hypergraphs. Discrete Math., 2023, 3469113481

[35] LiuX, MubayiD. The feasible region of hypergraphs. J. Combin. Theory Ser. B, 2021, 148: 23-59

[36] LiuX, MubayiD. Tight bounds for Katona’s shadow intersection theorem. European J. Combin., 2021, 97103391

[37] LiuX, MukherjeeS. Stability theorems for some Kruskal-Katona type results. European J. Combin., 2023, 110103666

[38] Liu, X., Song, J.: Exact results for some extremal problems on expansions I. arXiv preprint arXiv:2310.01736, (2023)

[39] LvZ, GyőriE, HeZ, SaliaN, TompkinsC, VargaK, ZhuX. Generalized Turán numbers for the edge blow-up of a graph. Discrete Math., 2024, 3471113682

[40] MubayiD. A hypergraph extension of Turán’s theorem. J. Combin. Theory Ser. B, 2006, 96(1): 122-134

[41] Mubayi, D., Verstraëte, J.: A survey of Turán problems for expansions. In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl., pp. 117–143. Springer, [Cham], (2016)

[42] ÖzkahyaL, YoungM. Anti-Ramsey number of matchings in hypergraphs. Discrete Math., 2013, 313(20): 2359-2364

[43] Ruzsa, I. Z., Szemerédi, E.: Triple systems with no six points carrying three triangles. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, volume 18 of Colloq. Math. Soc. János Bolyai, p 939–945. North-Holland, Amsterdam-New York, (1978)

[44] Simonovits, M.: A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 279–319. (1968)

[45] Song, J.: Triangles in graphs without the expansion of $4$-cycle. submitted

[46] TangY, LiT, YanG. Anti-Ramsey number of expansions of paths and cycles in uniform hypergraphs. J. Graph Theory, 2022, 101(4): 668-685

[47] TangY, LiT, YanG. Anti-Ramsey number of disjoint union of star-like hypergraphs. Discrete Math., 2024, 3474113748

[48] TuránP. On an external problem in graph theory. Mat. Fiz. Lapok, 1941, 48: 436-452

[49] YuanL-T. Extremal graphs for edge blow-up of graphs. J. Combin. Theory Ser. B, 2022, 152: 379-398

[50] ZhangF, ChenY, GyőriE, ZhuX. Maximum cliques in a graph without disjoint given subgraph. Discrete Math., 2024, 3474113863

Funding

ERC Advanced Grant(101020255)

Leverhulme Research Project Grant(RPG-2018-424)

National Natural Science Foundation of China(12271169)

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

Just Accepted

This article has successfully passed peer review and final editorial review, and will soon enter typesetting, proofreading and other publishing processes. The currently displayed version is the accepted final manuscript. The officially published version will be updated with format, DOI and citation information upon launch. We recommend that you pay attention to subsequent journal notifications and preferentially cite the officially published version. Thank you for your support and cooperation.