Optimal threshold for a random graph to be 2-universal. (English) Zbl 1420.05161
Summary: For a family of graphs \(\mathcal{F},\) a graph \(G\) is \(\mathcal{F}\)-universal if \(G\) contains every graph in \(\mathcal{F}\) as a (not necessarily induced) subgraph. For the family of all graphs on \(n\) vertices and of maximum degree at most two, \(\mathcal{H}(n,2),\) we prove that there exists a constant \(C\) such that for \(p \geq C \left ( \frac{\log n}{n^2} \right )^{\frac{1}{3}},\) the binomial random graph \(G(n,p)\) is typically \(\mathcal{H}(n,2)\)-universal. This bound is optimal up to the constant factor as illustrated in the seminal work of A. Johansson et al. [Random Struct. Algorithms 33, No. 1, 1–28 (2008; Zbl 1146.05040)] for triangle factors. Our result improves significantly on the previous best bound of \(p \geq C \left (\frac{\log n}{n}\right )^{\frac{1}{2}}\) due to J. H. Kim and S. J. Lee [SIAM J. Discrete Math. 28, No. 3, 1467–1478 (2014; Zbl 1305.05209)]. In fact, we prove the stronger result that for \(\mathcal{H}^{\ell }(n,2),\) the family of all graphs on \(n\) vertices, of maximum degree at most two and of girth at least \(\ell , G(n,p)\) is typically \(\mathcal H^{\ell }(n,2)\)-universal when \(p \geq C \left (\frac{\log n}{n^{\ell -1}}\right )^{\frac{1}{\ell }}.\) This result is also optimal up to the constant factor. Our results verify (in a weak form) a classical conjecture of J. Kahn and G. Kalai [Comb. Probab. Comput. 16, No. 3, 495–502 (2007; Zbl 1118.05093)].
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C75 | Structural characterization of families of graphs |
References:
| [1] | Alon, Noga; Asodi, Vera, Sparse universal graphs, J. Comput. Appl. Math., 142, 1, 1-11 (2002) · Zbl 0997.05047 · doi:10.1016/S0377-0427(01)00455-1 |
| [2] | Alon, Noga; Capalbo, Michael, Sparse universal graphs for bounded-degree graphs, Random Structures Algorithms, 31, 2, 123-133 (2007) · Zbl 1133.05095 · doi:10.1002/rsa.20143 |
| [3] | Alon, Noga; Capalbo, Michael, Optimal universal graphs with deterministic embedding. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 373-378 (2008), ACM, New York · Zbl 1192.05074 |
| [4] | Alon, Noga; Capalbo, Michael; Kohayakawa, Yoshiharu; R\`“{o}dl, Vojt\v{e}ch; Ruci\'”{n}ski, Andrzej; Szemer\'{e}di, Endre, Universality and tolerance (extended abstract). 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, 2000, 14-21 (2000), IEEE Comput. Soc. Press, Los Alamitos, CA · doi:10.1109/SFCS.2000.892007 |
| [5] | Alon, Noga; Capalbo, Michael; Kohayakawa, Yoshiharu; R\`“{o}dl, Vojt\v{e}ch; Ruci\'”{n}ski, Andrzej; Szemer\'{e}di, Endre, Near-optimum universal graphs for graphs with bounded degrees (extended abstract). Approximation, randomization, and combinatorial optimization, Berkeley, CA, 2001, Lecture Notes in Comput. Sci. 2129, 170-180 (2001), Springer, Berlin · Zbl 1001.05086 · doi:10.1007/3-540-44666-4\_20 |
| [6] | Alon, Noga; F\`“{u}redi, Zolt\'”{a}n, Spanning subgraphs of random graphs, Graphs Combin., 8, 1, 91-94 (1992) · Zbl 0767.05082 · doi:10.1007/BF01271712 |
| [7] | Alon, Noga; Krivelevich, Michael; Sudakov, Benny, Embedding nearly-spanning bounded degree trees, Combinatorica, 27, 6, 629-644 (2007) · Zbl 1164.05032 · doi:10.1007/s00493-007-2182-z |
| [8] | Alon, Noga; Spencer, Joel H., The probabilistic method, Wiley Series in Discrete Mathematics and Optimization, xiv+375 pp. (2016), John Wiley & Sons, Inc., Hoboken, NJ · Zbl 1333.05001 |
| [9] | Babai, L.; Chung, F. R. K.; Erd\H{o}s, P.; Graham, R. L.; Spencer, J. H., On graphs which contain all sparse graphs. Theory and practice of combinatorics, North-Holland Math. Stud. 60, 21-26 (1982), North-Holland, Amsterdam · Zbl 0495.05035 |
| [10] | Balogh, J\'{o}zsef; Csaba, B\'{e}la; Pei, Martin; Samotij, Wojciech, Large bounded degree trees in expanding graphs, Electron. J. Combin., 17, 1, Research Paper 6, 9 pp. pp. (2010) · Zbl 1184.05022 |
| [11] | Balogh, J\'{o}zsef; Csaba, B\'{e}la; Samotij, Wojciech, Local resilience of almost spanning trees in random graphs, Random Structures Algorithms, 38, 1-2, 121-139 (2011) · Zbl 1215.05154 · doi:10.1002/rsa.20345 |
| [12] | Bednarska, Ma\l gorzata; \L uczak, Tomasz, Biased positional games for which random strategies are nearly optimal, Combinatorica, 20, 4, 477-488 (2000) · Zbl 0973.91013 · doi:10.1007/s004930070002 |
| [13] | Bhatt, Sandeep N.; Chung, F. R. K.; Leighton, F. T.; Rosenberg, Arnold L., Universal graphs for bounded-degree trees and planar graphs, SIAM J. Discrete Math., 2, 2, 145-155 (1989) · Zbl 0674.05037 · doi:10.1137/0402014 |
| [14] | Bollob\'{a}s, B\'{e}la, Modern graph theory, Graduate Texts in Mathematics 184, xiv+394 pp. (1998), Springer-Verlag, New York · Zbl 0902.05016 · doi:10.1007/978-1-4612-0619-4 |
| [15] | Capalbo, M. R.; Kosaraju, S. R., Small universal graphs. Annual ACM Symposium on Theory of Computing, Atlanta, GA, 1999, 741-749 (1999), ACM, New York · Zbl 1345.05097 · doi:10.1145/301250.301446 |
| [16] | Chung, F. R. K.; Graham, R. L., On graphs which contain all small trees, J. Combinatorial Theory Ser. B, 24, 1, 14-23 (1978) · Zbl 0374.05042 |
| [17] | Chung, F. R. K.; Graham, R. L., On universal graphs. Second International Conference on Combinatorial Mathematics (New York, 1978), Ann. New York Acad. Sci. 319, 136-140 (1979), New York Acad. Sci., New York · Zbl 0478.05056 |
| [18] | Chung, F. R. K.; Graham, R. L., On universal graphs for spanning trees, J. London Math. Soc. (2), 27, 2, 203-211 (1983) · Zbl 0509.05033 · doi:10.1112/jlms/s2-27.2.203 |
| [19] | Chung, F. R. K.; Graham, R. L.; Pippenger, N., On graphs which contain all small trees. II. Combinatorics, Proc. Fifth Hungarian Colloq., Keszthely, 1976, 213-223 (1978), North-Holland, Amsterdam · Zbl 0395.05049 |
| [20] | Conlon, David; Ferber, Asaf; Nenadov, Rajko; Skori\'{c}, Nemanja, Almost-spanning universality in random graphs, Random Structures Algorithms, 50, 3, 380-393 (2017) · Zbl 1364.05061 · doi:10.1002/rsa.20661 |
| [21] | Dellamonica, Domingos, Jr.; Kohayakawa, Yoshiharu; R\`“{o}dl, Vojt\v{e}ch; Ruci\'”{n}ski, Andrzej, An improved upper bound on the density of universal random graphs, Random Structures Algorithms, 46, 2, 274-299 (2015) · Zbl 1309.05160 · doi:10.1002/rsa.20545 |
| [22] | Erd\H{o}s, P.; R\'{e}nyi, A., On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutat\'{o} Int. K\"{o}zl., 5, 17-61 (1960) · Zbl 0103.16301 |
| [23] | Erd\H{o}s, P.; R\'{e}nyi, A., On the existence of a factor of degree one of a connected random graph, Acta Math. Acad. Sci. Hungar., 17, 359-368 (1966) · Zbl 0203.56902 · doi:10.1007/BF01894879 |
| [24] | Ferber, Asaf; Luh, Kyle; Nguyen, Oanh, Embedding large graphs into a random graph, Bull. Lond. Math. Soc., 49, 5, 784-797 (2017) · Zbl 1372.05199 · doi:10.1112/blms.12066 |
| [25] | Ferber, Asaf; Nenadov, Rajko; Peter, Ueli, Universality of random graphs and rainbow embedding, Random Structures Algorithms, 48, 3, 546-564 (2016) · Zbl 1338.05248 · doi:10.1002/rsa.20596 |
| [26] | Friedman, J.; Pippenger, N., Expanding graphs contain all small trees, Combinatorica, 7, 1, 71-76 (1987) · Zbl 0624.05028 · doi:10.1007/BF02579202 |
| [27] | Haxell, P. E., Tree embeddings, J. Graph Theory, 36, 3, 121-130 (2001) · Zbl 0967.05029 · doi:10.1002/1097-0118(200103)36:\(3\langle121\)::AID-JGT |
| [28] | Janson, Svante; \L uczak, Tomasz; Ruci\'{n}ski, Andrzej, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. Random graphs ’87, Pozna\'{n}, 1987, 73-87 (1990), Wiley, Chichester · Zbl 0733.05073 |
| [29] | Janson, Svante; \L uczak, Tomasz; Ruci\'{n}ski, Andrzej, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. Random graphs ’87, Pozna\'{n}, 1987, 73-87 (1990), Wiley, Chichester · Zbl 0733.05073 |
| [30] | Johannsen, Daniel; Krivelevich, Michael; Samotij, Wojciech, Expanders are universal for the class of all spanning trees, Combin. Probab. Comput., 22, 2, 253-281 (2013) · Zbl 1260.05081 · doi:10.1017/S0963548312000533 |
| [31] | Johansson, Anders; Kahn, Jeff; Vu, Van, Factors in random graphs, Random Structures Algorithms, 33, 1, 1-28 (2008) · Zbl 1146.05040 · doi:10.1002/rsa.20224 |
| [32] | Kahn, Jeff; Kalai, Gil, Thresholds and expectation thresholds, Combin. Probab. Comput., 16, 3, 495-502 (2007) · Zbl 1118.05093 · doi:10.1017/S0963548307008474 |
| [33] | Kim, Jeong Han; Lee, Sang June, Universality of random graphs for graphs of maximum degree two, SIAM J. Discrete Math., 28, 3, 1467-1478 (2014) · Zbl 1305.05209 · doi:10.1137/130942437 |
| [34] | Krivelevich, Michael, Embedding spanning trees in random graphs, SIAM J. Discrete Math., 24, 4, 1495-1500 (2010) · Zbl 1221.05283 · doi:10.1137/100805753 |
| [35] | montgomery2014embedding R. Montgomery, Embedding bounded degree spanning trees in random graphs, preprint, arXiv:1405.6559, 2014. |
| [36] | P\'{o}sa, L., Hamiltonian circuits in random graphs, Discrete Math., 14, 4, 359-364 (1976) · Zbl 0322.05127 · doi:10.1016/0012-365X(76)90068-6 |
| [37] | Riordan, Oliver, Spanning subgraphs of random graphs, Combin. Probab. Comput., 9, 2, 125-148 (2000) · Zbl 0964.05058 · doi:10.1017/S0963548399004150 |
| [38] | R\"{o}dl, Vojt\v{e}ch, A note on universal graphs, Ars Combin., 11, 225-229 (1981) · Zbl 0468.05040 |
| [39] | West, Douglas B., Introduction to graph theory, xvi+512 pp. (1996), Prentice Hall, Inc., Upper Saddle River, NJ · Zbl 0845.05001 |
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.
