Hostname: page-component-74656f9884-rngvg Total loading time: 0 Render date: 2026-11-06T02:08:30.753Z Has data issue: false hasContentIssue false
  • English
  • Français

Saturation in the Hypercube and Bootstrap Percolation

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  31 March 2016

NATASHA MORRISON ,
JONATHAN A. NOEL  and
ALEX SCOTT
NATASHA MORRISON
Affiliation:
Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK (e-mail: morrison@maths.ox.ac.uk, noel@maths.ox.ac.uk, scott@maths.ox.ac.uk)
JONATHAN A. NOEL
Affiliation:
Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK (e-mail: morrison@maths.ox.ac.uk, noel@maths.ox.ac.uk, scott@maths.ox.ac.uk)
ALEX SCOTT
Affiliation:
Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK (e-mail: morrison@maths.ox.ac.uk, noel@maths.ox.ac.uk, scott@maths.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let Qd denote the hypercube of dimension d. Given d ⩾ m, a spanning subgraph G of Qd is said to be (Qd , Qm )-saturated if it does not contain Qm as a subgraph but adding any edge of E(Qd )\E(G) creates a copy of Qm in G. Answering a question of Johnson and Pinto [27], we show that for every fixed m ⩾ 2 the minimum number of edges in a (Qd , Qm )-saturated graph is Θ(2d ).

We also study weak saturation, which is a form of bootstrap percolation. A spanning subgraph of Qd is said to be weakly (Qd , Qm )-saturated if the edges of E(Qd )\E(G) can be added to G one at a time so that each added edge creates a new copy of Qm . Answering another question of Johnson and Pinto [27], we determine the minimum number of edges in a weakly (Qd , Qm )-saturated graph for all d ⩾ m ⩾ 1. More generally, we determine the minimum number of edges in a subgraph of the d-dimensional grid Pkd which is weakly saturated with respect to ‘axis aligned’ copies of a smaller grid Prm . We also study weak saturation of cycles in the grid.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.) 05D99: None of the above, but in this section

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 1 , January 2017 , pp. 78 - 98
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Alon, N. (1985) An extremal problem for sets with applications to graph theory. J. Combin. Theory Ser. A 40 82–89.Google Scholar
[2] Baber, R. (2012) Turán densities of hypercubes. arXiv:1201.3587v2 Google Scholar
[3] Balister, P. N., Bollobás, B., Lee, J. D. and Narayanan, B. P. Line percolation, Random Struct. Alg., to appear.Google Scholar
[4] Balogh, J. and Bollobás, B. (2006) Bootstrap percolation on the hypercube. Probab. Theory Rel. Fields 134 624–648.Google Scholar
[5] Balogh, J., Bollobás, B. and Morris, R. (2012) Graph bootstrap percolation. Random Struct. Alg. 41 413–440.CrossRefGoogle Scholar
[6] Balogh, J., Bollobás, B., Morris, R. and Riordan, O. (2012) Linear algebra and bootstrap percolation. J. Combin. Theory Ser. A 119 1328–1335.Google Scholar
[7] Balogh, J., Hu, P., Lidický, B. and Liu, H. (2014) Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube. European J. Combin. 35 75–85.Google Scholar
[8] Barefoot, C. A., Clark, L. H., Entringer, R. C., Porter, T. D., Székely, L. A. and Tuza, Z. (1996) Cycle-saturated graphs of minimum size. Discrete Math. 150 31–48.CrossRefGoogle Scholar
[9] Bollobás, B. (1968) Weakly k-saturated graphs. In Beiträge zur Graphentheorie: Kolloquium, Manebach 1967, Teubner, pp. 25–31.Google Scholar
[10] Bollobás, B. (1978) Extremal graph theory, Vol. 11 of London Mathematical Society Monographs, Academic.Google Scholar
[11] Brass, P., Harborth, H. and Nienborg, H. (1995) On the maximum number of edges in a C 4-free subgraph of Qn . J. Graph Theory 19 17–23.Google Scholar
[12] Chen, Y.-C. (2009) Minimum C 5-saturated graphs. J. Graph Theory 61 111–126.Google Scholar
[13] Chen, Y.-C. (2011) All minimum C 5-saturated graphs. J. Graph Theory 67 9–26.Google Scholar
[14] Choi, S. and Guan, P. (2008) Minimum critical squarefree subgraph of a hypercube. In Proc. 39th Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 189 57–64.Google Scholar
[15] Chung, F. R. K. (1992) Subgraphs of a hypercube containing no small even cycles. J. Graph Theory 16 273–286.Google Scholar
[16] Conder, M. (1993) Hexagon-free subgraphs of hypercubes. J. Graph Theory 17 477–479.Google Scholar
[17] Conlon, D. (2010) An extremal theorem in the hypercube. Electron. J. Combin. 17 Research Paper 111.Google Scholar
[18] Day, A. N. (2014) Saturated graphs of prescribed minimum degree. arXiv:1407.6664v1 CrossRefGoogle Scholar
[19] Erdős, P. (1984) On some problems in graph theory, combinatorial analysis and combinatorial number theory. In Graph Theory and Combinatorics: Cambridge 1983, Academic, pp. 1–17.Google Scholar
[20] Erdős, P., Hajnal, A. and Moon, J. W. (1964) A problem in graph theory. Amer. Math. Monthly 71 1107–1110.Google Scholar
[21] Faudree, J. R., Faudree, R. J. and Schmitt, J. R. (2011) A survey of minimum saturated graphs. Electron. J. Combin. 18 Dynamic Survey 19.Google Scholar
[22] Füredi, Z. and Kim, Y. (2013) Cycle-saturated graphs with minimum number of edges. J. Graph Theory 73 203–215.Google Scholar
[23] Füredi, Z. and Özkahya, L. (2009) On 14-cycle-free subgraphs of the hypercube. Combin. Probab. Comput. 18 725–729.Google Scholar
[24] Füredi, Z. and Özkahya, L. (2011) On even-cycle-free subgraphs of the hypercube. J. Combin. Theory Ser. A 118 1816–1819.Google Scholar
[25] Gould, R., Łuczak, T. and Schmitt, J. (2006) Constructive upper bounds for cycle-saturated graphs of minimum size. Electron. J. Combin. 13 Research Paper 29.Google Scholar
[26] Hamming, R. W. (1950) Error detecting and error correcting codes. Bell System Tech. J. 29 147–160.CrossRefGoogle Scholar
[27] Johnson, J. R. and Pinto, T. (2014) Saturated subgraphs of the hypercube. arXiv:1406.1766v1 Google Scholar
[28] Kalai, G. (1984) Weakly saturated graphs are rigid. In Convexity and Graph Theory: Jerusalem 1981, Vol. 87 of North-Holland Mathematics Studies, North-Holland, pp. 189–190.Google Scholar
[29] Kalai, G. (1985) Hyperconnectivity of graphs. Graphs Combin. 1 65–79.Google Scholar
[30] MacWilliams, F. J. and Sloane, N. J. A. (1977) The Theory of Error-Correcting Codes I, Vol. 16 of North-Holland Mathematical Library, North-Holland.Google Scholar
[31] MacWilliams, F. J. and Sloane, N. J. A. (1977) The Theory of Error-Correcting Codes II, Vol. 16 of North-Holland Mathematical Library, North-Holland.Google Scholar
[32] Morrison, N., Noel, J. A. and Scott, A. (2014) On saturated k-Sperner systems. Electron. J. Combin. 21 Paper 3.22.CrossRefGoogle Scholar
[33] Ollmann, L. T. (1972) K 2,2 saturated graphs with a minimal number of edges. In Proc. 3rd South-eastern Conference on Combinatorics, Graph Theory, and Computing: Boca Raton 1972, pp. 367–392.Google Scholar
[34] Pikhurko, O. (1999) Extremal hypergraphs. PhD thesis, University of Cambridge.Google Scholar
[35] Pikhurko, O. (2001) Weakly saturated hypergraphs and exterior algebra. Combin. Probab. Comput. 10 435–451.Google Scholar
[36] Tuza, Z. (1992) Asymptotic growth of sparse saturated structures is locally determined. Discrete Math. 108 397–402.Google Scholar
[37] Zykov, A. A. (1949) On some properties of linear complexes. Mat. Sbornik (N.S.) 24 (66) 163–188.Google Scholar