Weakly saturated hypergraphs and a conjecture of Tuza

Shapira, Asaf; Tyomkyn, Mykhaylo

doi:10.1090/proc/16197

Weakly saturated hypergraphs and a conjecture of Tuza
HTML articles powered by AMS MathViewer

by Asaf Shapira and Mykhaylo Tyomkyn;

Proc. Amer. Math. Soc. 151 (2023), 2795-2805

DOI: https://doi.org/10.1090/proc/16197

Published electronically: April 7, 2023

HTML | PDF | Request permission

Abstract:

Given a fixed hypergraph $H$, let $\operatorname {wsat}(n,H)$ denote the smallest number of edges in an $n$-vertex hypergraph $G$, with the property that one can sequentially add the edges missing from $G$, so that whenever an edge is added, a new copy of $H$ is created. The study of $\operatorname {wsat}(n,H)$ was introduced by Bollobás in 1968, and turned out to be one of the most influential topics in extremal combinatorics. While for most $H$ very little is known regarding $\operatorname {wsat}(n,H)$, Alon proved in 1985 that for every graph $H$ there is a limiting constant $C_H$ so that $\operatorname {wsat}(n,H)=(C_H+o(1))n$. Tuza conjectured in 1992 that Alon’s theorem can be (appropriately) extended to arbitrary $r$-uniform hypergraphs. In this paper we prove this conjecture.

References

Noga Alon, An extremal problem for sets with applications to graph theory, J. Combin. Theory Ser. A 40 (1985), no. 1, 82–89. MR 804870, DOI 10.1016/0097-3165(85)90048-2
L. Babai and P. Frankl, Linear algebra methods in combinatorics, University of Chicago, 1988.
József Balogh, Béla Bollobás, Robert Morris, and Oliver Riordan, Linear algebra and bootstrap percolation, J. Combin. Theory Ser. A 119 (2012), no. 6, 1328–1335. MR 2915649, DOI 10.1016/j.jcta.2012.03.005
József Balogh and Gábor Pete, Random disease on the square grid, Proceedings of the Eighth International Conference “Random Structures and Algorithms” (Poznan, 1997), 1998, pp. 409–422. MR 1662792, DOI 10.1002/(SICI)1098-2418(199810/12)13:3/4<409::AID-RSA11>3.3.CO;2-5
Natalie C. Behague, Hypergraph saturation irregularities, Electron. J. Combin. 25 (2018), no. 2, Paper No. 2.11, 13. MR 3799429, DOI 10.37236/7727
A. Blokhuis, Solution of an extremal problem for sets using resultants of polynomials, Combinatorica 10 (1990), no. 4, 393–396. MR 1099252, DOI 10.1007/BF02128673
B. Bollobás, On generalized graphs, Acta Math. Acad. Sci. Hungar. 16 (1965), 447–452 (English, with Russian summary). MR 183653, DOI 10.1007/BF01904851
Béla Bollobás, Weakly $k$-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967) B. G. Teubner Verlagsgesellschaft, Leipzig, 1968, pp. 25–31. MR 244077
Denys Bulavka, Martin Tancer, and Mykhaylo Tyomkyn, Weak saturation of multipartite hypergraphs, Preprint, arXiv:2109.03703, 2021.
Debsoumya Chakraborti and Po-Shen Loh, Minimizing the numbers of cliques and cycles of fixed size in an $F$-saturated graph, European J. Combin. 90 (2020), 103185, 20. MR 4125530, DOI 10.1016/j.ejc.2020.103185
Jill R. Faudree, Ralph J. Faudree, and John R. Schmitt, A survey of minimum saturated graphs, Electron. J. Combin. DS19 (2011), no. Dynamic Surveys, 36. MR 4336221
P. Erdős, Problems and results in graph theory, The theory and applications of graphs (Kalamazoo, Mich., 1980) Wiley, New York, 1981, pp. 331–341. MR 634537
Paul Erdős, Some new problems and results in graph theory and other branches of combinatorial mathematics, Combinatorics and graph theory (Calcutta, 1980) Lecture Notes in Math., vol. 885, Springer, Berlin-New York, 1981, pp. 9–17. MR 655605
Paul Erdős, Zoltán Füredi, and Zsolt Tuza, Saturated $r$-uniform hypergraphs, Discrete Math. 98 (1991), no. 2, 95–104. MR 1144629, DOI 10.1016/0012-365X(91)90035-Z
P. Erdős, A. Hajnal, and J. W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964), 1107–1110. MR 170339, DOI 10.2307/2311408
P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), no. 1, 25–42. MR 602413, DOI 10.1007/BF02579174
Ralph J. Faudree and Ronald J. Gould, Weak saturation numbers for multiple copies, Discrete Math. 336 (2014), 1–6. MR 3254965, DOI 10.1016/j.disc.2014.07.012
Ralph J. Faudree, Ronald J. Gould, and Michael S. Jacobson, Weak saturation numbers for sparse graphs, Discuss. Math. Graph Theory 33 (2013), no. 4, 677–693. MR 3117048, DOI 10.7151/dmgt.1688
M. Fekete, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten, Math. Z. 17 (1923), no. 1, 228–249 (German). MR 1544613, DOI 10.1007/BF01504345
P. Frankl, An extremal problem for two families of sets, European J. Combin. 3 (1982), no. 2, 125–127. MR 670845, DOI 10.1016/S0195-6698(82)80025-5
Gil Kalai, Weakly saturated graphs are rigid, Convexity and graph theory (Jerusalem, 1981) North-Holland Math. Stud., vol. 87, North-Holland, Amsterdam, 1984, pp. 189–190. MR 791030, DOI 10.1016/S0304-0208(08)72824-X
Gil Kalai, Hyperconnectivity of graphs, Graphs Combin. 1 (1985), no. 1, 65–79. MR 796184, DOI 10.1007/BF02582930
Gyula Katona, Tibor Nemetz, and Miklós Simonovits, On a problem of Turán in the theory of graphs, Mat. Lapok 15 (1964), 228–238 (Hungarian, with English and Russian summaries). MR 172263
L. Lovász, Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977) Academic Press, London-New York, 1977, pp. 45–86. MR 480111
Natasha Morrison and Jonathan A. Noel, Extremal bounds for bootstrap percolation in the hypercube, J. Combin. Theory Ser. A 156 (2018), 61–84. MR 3762103, DOI 10.1016/j.jcta.2017.11.018
Guy Moshkovitz and Asaf Shapira, Exact bounds for some hypergraph saturation problems, J. Combin. Theory Ser. B 111 (2015), 242–248. MR 3315608, DOI 10.1016/j.jctb.2014.08.004
Jason O’Neill and Jacques Verstraete, A generalization of the Bollobás set pairs inequality, Electron. J. Combin. 28 (2021), no. 3, Paper No. 3.8, 14. MR 4281685, DOI 10.37236/9627
Oleg Pikhurko, The minimum size of saturated hypergraphs, Combin. Probab. Comput. 8 (1999), no. 5, 483–492. MR 1731983, DOI 10.1017/S0963548399003971
Oleg Pikhurko, Uniform families and count matroids, Graphs Combin. 17 (2001), no. 4, 729–740. MR 1876580, DOI 10.1007/s003730170012
Oleg Pikhurko, Weakly saturated hypergraphs and exterior algebra, Combin. Probab. Comput. 10 (2001), no. 5, 435–451. MR 1869050, DOI 10.1017/S0963548301004746
Oleg Pikhurko, Results and open problems on minimum saturated hypergraphs, Ars Combin. 72 (2004), 111–127. MR 2069050
J.-E. Pin, On two combinatorial problems arising from automata theory, Combinatorial mathematics (Marseille-Luminy, 1981) North-Holland Math. Stud., vol. 75, North-Holland, Amsterdam, 1983, pp. 535–548. MR 841339
Vojtěch Rödl, On a packing and covering problem, European J. Combin. 6 (1985), no. 1, 69–78. MR 793489, DOI 10.1016/S0195-6698(85)80023-8
Alex Scott and Elizabeth Wilmer, Combinatorics in the exterior algebra and the Bollobás two families theorem, J. Lond. Math. Soc. (2) 104 (2021), no. 4, 1812–1839. MR 4339952, DOI 10.1112/jlms.12484
Gabriel Semanišin, On some variations of extremal graph problems, Discuss. Math. Graph Theory 17 (1997), no. 1, 67–76. MR 1633276, DOI 10.7151/dmgt.1039
E. Sidorowicz, Size of weakly saturated graphs, Discrete Math. 307 (2007), no. 11-12, 1486–1492. MR 2311122, DOI 10.1016/j.disc.2005.11.085
Zs. Tuza, A generalization of saturated graphs for finite languages, Proceedings of the 4th international meeting of young computer scientists, IMYCS ’86 (Smolenice Castle, 1986), 1986, pp. 287–293. MR 894100
Zsolt Tuza, Extremal problems on saturated graphs and hypergraphs, Ars Combin. 25 (1988), no. B, 105–113. Eleventh British Combinatorial Conference (London, 1987). MR 942469
Zsolt Tuza, Asymptotic growth of sparse saturated structures is locally determined, Discrete Math. 108 (1992), no. 1-3, 397–402. Topological, algebraical and combinatorial structures. Frolík’s memorial volume. MR 1189861, DOI 10.1016/0012-365X(92)90692-9
A. A. Zykov, On some properties of linear complexes, Mat. Sbornik N.S. 24(66) (1949), 163–188 (Russian). MR 35428

AMS Website Down

Proceedings of the American Mathematical Society

Weakly saturated hypergraphs and a conjecture of Tuza
HTML articles powered by AMS MathViewer

Abstract: