Random induced subgraphs of generalized \(n\)-cubes. (English) Zbl 0898.05075
Asymptotic results are given for connected components of the random subgraph induced by independently selected vertices from a generalized \(n\)-cube.
Reviewer: O.Frank (Stockholm)
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C40 | Connectivity |
References:
| [1] | Ajtai, M.; Komlós, J.; Szemerédi, E., Largest random component of a \(k\), Combinatorica, 2, 1-7 (1982) · Zbl 0489.05053 |
| [2] | Aldous, D.; Diaconis, P., Strong uniform times and finite random walks, Adv. in Appl. Math., 2, 69-97 (1987) · Zbl 0631.60065 |
| [3] | Alon, N.; Spencer, J.; Erdös, P., The Probabilistic Method. The Probabilistic Method, Discrete Math. and Optimization Series (1991), Wiley Interscience: Wiley Interscience New York |
| [4] | L. Babai, 1991, Local expansion of vertex transitive graphs and random generation in finite groups, Proceedings of the Twenty-Third ACM Symposium on Theory of Computing, 1, 164, 174, ACM Press, New York; L. Babai, 1991, Local expansion of vertex transitive graphs and random generation in finite groups, Proceedings of the Twenty-Third ACM Symposium on Theory of Computing, 1, 164, 174, ACM Press, New York |
| [5] | Babai, L.; Sos, V., Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin., 1, 1-11 (1985) · Zbl 0573.05032 |
| [6] | Bollobás, B., Random Graphs (1985), Academic Press: Academic Press New York · Zbl 0567.05042 |
| [7] | Chernoff, H., A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statist., 23, 493-509 (1952) · Zbl 0048.11804 |
| [8] | Erdös, P.; Rényi, A., Probabilistic methods in group theory, J. Anal. Math., 14, 127-138 (1965) · Zbl 0247.20045 |
| [9] | L. Harper, Minimal numberings and isoperimetric problems on cubes, Theory of Graphs, International Symposium, Rome, 1996; L. Harper, Minimal numberings and isoperimetric problems on cubes, Theory of Graphs, International Symposium, Rome, 1996 |
| [10] | Harris, T. E., The Theory of Branching Processes (1963), Springer: Springer New York · Zbl 0117.13002 |
| [11] | C. Reidys, 1995, Neutral Networks of RNA Secondary Structures, Math. Faculty, Friedrich Schiller Universität, Jena; C. Reidys, 1995, Neutral Networks of RNA Secondary Structures, Math. Faculty, Friedrich Schiller Universität, Jena · Zbl 0864.92010 |
| [12] | C. Reidys, Mapping in random-structures; C. Reidys, Mapping in random-structures · Zbl 1012.05060 |
| [13] | C. Reidys, F. Stadler, P. Schuster, Generic properties of combinatory maps and neutral networks of RNA secondary structures, Bull. Math. Biol. 59, 339, 397; C. Reidys, F. Stadler, P. Schuster, Generic properties of combinatory maps and neutral networks of RNA secondary structures, Bull. Math. Biol. 59, 339, 397 · Zbl 0925.92006 |
| [14] | Erdös, P.; Rényi, A., On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5, 17-61 (1960) · Zbl 0103.16301 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
