On connectivity in random graph models with limited dependencies. (English) Zbl 07904973
Summary: We consider random graph models in which the events describing the inclusion of potential edges have to be independent of each other if the corresponding edges are non-adjacent and ask: what is the minimum probability \(\rho (n)\), such that for any distribution \(\mathcal{G}\) (in this model) on graphs with \(n\) vertices in which each potential edge has a marginal probability of being present at least \(\rho (n)\), a graph drawn from \(\mathcal{G}\) is connected with non-zero probability? The answer to this question is sensitive to the formalization of the independence condition. We introduce a strict hierarchy of five conditions, which give rise to at least three different functions \(\rho (n)\). For each condition, we provide upper and lower bounds for \(\rho (n)\). For the strongest condition, the coloring model, we show that \(\rho (n) \to 2 - \phi \approx 0.38\) for \(n \to \infty\). In contrast, for the weakest condition, pairwise independence, we show that \(\rho (n)\) lies within \(O(1/n^2)\) of the threshold \(1-2/n\) for completely arbitrary distributions.
© 2024 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.
© 2024 The Authors. Random Structures & Algorithms published by Wiley Periodicals LLC.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05D40 | Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) |
| 05C40 | Connectivity |
References:
| [1] | J.Aaronson, D.Gilat, M.Keane, and V.deValk, An algebraic construction of a class of one‐dependent processes, Ann. Probab.17 (1989), no. 1, 128-143. · Zbl 0681.60038 |
| [2] | N.Alon and J. H.Spencer, The probabilistic method, John Wiley & Sons, Hoboken, New Jersey, US, 2016. https://doi.org/10.1002/9780470277331. · Zbl 1333.05001 · doi:10.1002/9780470277331 |
| [3] | N.Alon and A.Nussboim. k‐wise independent random graphs. 2008 49th annual IEEE symposium on foundations of computer science, pages 813-822. 2008https://doi.org/10.1109/FOCS.2008.61. · doi:10.1109/FOCS.2008.61 |
| [4] | K.Azuma, Weighted sums of certain dependent random variables, Tohoku Math J19 (1967), no. 3, 357-367. https://doi.org/10.2748/tmj/1178243286. · Zbl 0178.21103 · doi:10.2748/tmj/1178243286 |
| [5] | L.Badakhshian, V.Falgas‐Ravry, and M.Sharifzadeh. On density conditions for transversal trees in multipartite graphs. arXiv preprint. 2023https://doi.org/10.48550/arXiv.2305.05713. · doi:10.48550/arXiv.2305.05713 |
| [6] | P.Balister and B.Bollobás, Critical probabilities of 1‐independent percolation models, Comb. Probab. Comput.21 (2012), no. 1‐2, 11-22. https://doi.org/10.1017/S0963548311000538. · Zbl 1241.05099 · doi:10.1017/S0963548311000538 |
| [7] | P.Balister, B.Bollobás, and M.Walters, Random transceiver networks, Adv. Appl. Probab.41 (2009), no. 2, 323-343. https://doi.org/10.1239/aap/1246886613. · Zbl 1220.60056 · doi:10.1239/aap/1246886613 |
| [8] | P.Balister, T.Johnston, M.Savery, and A.Scott. Improved bounds for 1‐independent percolation on [( {\mathbb{Z}}^n \]\). arXiv preprint. 2022https://doi.org/10.48550/arXiv.2206.12335. · doi:10.48550/arXiv.2206.12335 |
| [9] | B.Bollobás, The isoperimetric number of random regular graphs, Eur. J. Comb.9 (1988), no. 3, 241-244. https://doi.org/10.1016/S0195‐6698(88)80014‐3. · Zbl 0673.05086 · doi:10.1016/S0195‐6698(88)80014‐3 |
| [10] | A.Bondy, J.Shen, S.Thomassé, and C.Thomassen, Density conditions for triangles in multipartite graphs, Combinatorica26 (2006), no. 2, 121-131. https://doi.org/10.1007/s00493‐006‐0009‐y. · Zbl 1174.05406 · doi:10.1007/s00493‐006‐0009‐y |
| [11] | K.Bringmann, R.Keusch, and J.Lengler, Geometric inhomogeneous random graphs, Theor. Comput. Sci.760 (2019), 35-54. https://doi.org/10.1016/j.tcs.2018.08.014. · Zbl 1414.05264 · doi:10.1016/j.tcs.2018.08.014 |
| [12] | R. M.Burton, M.Goulet, and R.Meester, On 1‐dependent processes and [( k \]\)‐block factors, Ann. Probab.21 (1993), no. 4, 2157-2168. https://doi.org/10.1214/aop/1176989014. · Zbl 0788.60049 · doi:10.1214/aop/1176989014 |
| [13] | C.Carathéodory, Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen, Math. Ann.64 (1907), no. 1, 95-115. https://doi.org/10.1007/BF01449883. · JFM 38.0448.01 · doi:10.1007/BF01449883 |
| [14] | F.Chung and L.Linyuan, Connected components in random graphs with given expected degree sequences, Ann. Comb.6 (2002), no. 2, 125-145. https://doi.org/10.1007/PL00012580. · Zbl 1009.05124 · doi:10.1007/PL00012580 |
| [15] | P.Csikvári and Z. L.Nagy, The density Turán problem, Comb. Probab. Comput.21 (2012), no. 4, 531-553. https://doi.org/10.1017/S0963548312000016. · Zbl 1247.05113 · doi:10.1017/S0963548312000016 |
| [16] | M.Deijfen, R.van derHofstad, and G.Hooghiemstra, Scale‐free percolation, Ann l’IHP Probab Stat49 (2013), no. 3, 817-838. https://doi.org/10.1214/12‐AIHP480. · Zbl 1274.60290 · doi:10.1214/12‐AIHP480 |
| [17] | P.Erdős, Graph theory and probability, Can. J. Math.11 (1959), 34-38. https://doi.org/10.4153/CJM‐1959‐003‐9. · Zbl 0084.39602 · doi:10.4153/CJM‐1959‐003‐9 |
| [18] | V.Falgas‐Ravry and V.Pfenninger, One‐independent percolation on Z^2 × K_n, Random Struct. Algoritm.62 (2022), no. 4, 887‐910. https://doi.org/10.1002/rsa.21129. · Zbl 1525.05095 · doi:10.1002/rsa.21129 |
| [19] | H.Gebauer, R. A.Moser, D.Scheder, and E.Welzl, “The Lovász local lemma and satisfiability,” Efficient algorithms: Essays dedicated to Kurt Mehlhorn on the occasion of his 60th birthday, S.Albers (ed.), H.Alt (ed.), and S.Näher (ed.) (eds.), Springer, Berlin, Heidelberg, 2009, pp. 30-54. https://doi.org/10.1007/978‐3‐642‐03456‐5.3. · Zbl 1258.68067 · doi:10.1007/978‐3‐642‐03456‐5.3 |
| [20] | A. E.Holroyd and T. M.Liggett, “Finitely dependent coloring,” Forum of mathematics, pi, Vol 4, Cambridge University Press, Cambridge, UK, 2016, pp. 9. https://doi.org/10.1017/fmp.2016.7. · Zbl 1361.60025 · doi:10.1017/fmp.2016.7 |
| [21] | S.Janson, A.Ruciński, and T.Łuczak, Random graphs, Wiley Series in Discrete Mathematics and Optimization, Wiley, Hoboken, New Jersey, US, 2011. https://doi.org/10.1002/9781118032718. · doi:10.1002/9781118032718 |
| [22] | A.Johansson, Asymptotic choice number for triangle free graphs, Technical Report, DIMACS, Piscataway, New Jersey, US, 1996, 91-95. |
| [23] | B.Karrer and M. E. J.Newman, Stochastic blockmodels and community structure in networks, Phys. Rev. E83 (2011), no. 1, 016107. https://doi.org/10.1103/PhysRevE.83.016107. · doi:10.1103/PhysRevE.83.016107 |
| [24] | D.Krioukov, F.Papadopoulos, M.Kitsak, A.Vahdat, and M.Boguná, Hyperbolic geometry of complex networks, Phys. Rev. E82 (2010), no. 3, 036106. https://doi.org/10.1103/PhysRevE.82.036106. · doi:10.1103/PhysRevE.82.036106 |
| [25] | T. M.Liggett, R. H.Schonmann, and A. M.Stacey, Domination by product measures, Ann. Probab.25 (1997), no. 1, 71-95. https://doi.org/10.1214/aop/1024404279. · Zbl 0882.60046 · doi:10.1214/aop/1024404279 |
| [26] | M.Molloy, The list chromatic number of graphs with small clique number, J Combin Theory Ser B134 (2019), no. 1, 264-284. https://doi.org/10.1016/j.jctb.2018.06.007. · Zbl 1402.05076 · doi:10.1016/j.jctb.2018.06.007 |
| [27] | Z. L.Nagy, A multipartite version of the Turán problem - Density conditions and eigenvalues, Electron. J. Comb.18 (2011), no. 1, P46. https://doi.org/10.37236/533. · Zbl 1217.05127 · doi:10.37236/533 |
| [28] | A.Nicholas Day, V.Falgas‐Ravry, and R.Hancock, Long paths and connectivity in 1‐independent random graphs, Random Struct. Algoritm.57 (2020), no. 4, 1007-1049. https://doi.org/10.1002/rsa.20972. · Zbl 1454.05108 · doi:10.1002/rsa.20972 |
| [29] | M.Penrose, Random geometric graphs, Oxford University Press, Oxford, UK, 2003. https://doi.org/10.1093/acprof:oso/9780198506263.001.0001. · Zbl 1029.60007 · doi:10.1093/acprof:oso/9780198506263.001.0001 |
| [30] | F.Pfender, Complete subgraphs in multipartite graphs, Combinatorica32 (2012), 483-495. https://doi.org/10.1007/s00493‐012‐2425‐5. · Zbl 1289.05231 · doi:10.1007/s00493‐012‐2425‐5 |
| [31] | H.Reittu and I.Norros, “Random graph models of communication network topologies,” Unifying themes in complex systems VII: Proceedings of the seventh international conference on complex systems, Springer, Berlin, Heidelberg, 2012, pp. 214-221. https://doi.org/10.1007/978‐3‐642‐18003‐3_21. · doi:10.1007/978‐3‐642‐18003‐3_21 |
| [32] | J. B.Shearer, On a problem of Spencer, Combinatorica5 (1985), no. 3, 241-245. https://doi.org/10.1007/BF02579368. · Zbl 0587.60012 · doi:10.1007/BF02579368 |
| [33] | K. B.Singer, Random intersection graphs, The Johns Hopkins University, Baltimore, Maryland, US, 1996. |
| [34] | J.Spencer, Asymptotic lower bounds for Ramsey functions, Discret. Math.20 (1977), 69-76. https://doi.org/10.1016/0012‐365X(77)90044‐9. · Zbl 0375.05033 · doi:10.1016/0012‐365X(77)90044‐9 |
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.
