Sharp threshold for embedding balanced spanning trees in random geometric graphs

EUROCOMB’23

Abstract
Consider the random geometric graph $\mathcal{G}(n,r)$ obtained by independently assigning a uniformly random position in $[0,1]^2$ to each of the $n$ vertices of the graph and connecting two vertices by an edge whenever their Euclidean distance is at most $r$. We study the event that $\mathcal{G}(n,r)$ contains a spanning copy of a balanced tree $T$ and obtain sharp thresholds for these events. Our methods provide a polynomial-time algorithm for finding a copy of such trees $T$ above the threshold.

Pages:
433–440
References

I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, Wireless sensor networks: a survey. Comput. Netw. 38.4 (2002), 393--422, doi: 10.1016/S1389-1286(01)00302-4.
https://doi.org/10.1016/S1389-1286(01)00302-4

M. Bradonjić and W. Perkins, On sharp thresholds in random geometric graphs. Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 17th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2014) and the 18th international workshop on randomization and computation (RANDOM 2014), Universitat Politècnica de Catalunya, Barcelona, Spain, September 4-6, 2014, 500-514, Wadern: Schloss Dagstuhl - Leibniz Zentrum für Informatik, ISBN 978-3-939897-74-3 (2014), doi: 10.4230/LIPIcs.APPROX-RANDOM.2014.500.

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms. MIT Press, Cambridge, MA, 4th ed. (2022), ISBN 978-0-262-04630-5.

J. Díaz, D. Mitsche and X. Pérez, Sharp Threshold for Hamiltonicity of Random Geometric Graphs. SIAM J. Discrete Math. 21 (2007), 57-65, doi: 10.1137/060665300.
https://doi.org/10.1137/060665300

A. Espuny Díaz, L. Lichev, D. Mitsche and A. Wesolek, Sharp threshold for embedding balanced spanning trees in random geometric graphs. arXiv e-prints (2023). arXiv: 2303.14229.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-060

D. Funke, S. Lamm, U. Meyer, M. Penschuck, P. Sanders, C. Schulz, D. Strash and M. von Looz, Communication-free massively distributed graph generation. J. Parallel Distrib. Comput. 131 (2019), 200-217, doi: 10.1016/j.jpdc.2019.03.011.
https://doi.org/10.1016/j.jpdc.2019.03.011

E. N. Gilbert, Random Plane Networks. J. Soc. Ind. Appl. Math. 9 (1961), 533-543, doi: 10.1137/0109045.
https://doi.org/10.1137/0109045

A. Goel, S. Rai and B. Krishnamachari, Monotone properties of random geometric graphs have sharp thresholds. Ann. Appl. Probab. 15.4 (2005), 2535-2552, doi: 10.1214/105051605000000575.
https://doi.org/10.1214/105051605000000575

P. Gupta and P. R. Kumar, Critical power for asymptotic connectivity in wireless networks. W. M. McEneaney, G. G. Yin and Q. Zhang (eds.), Stochastic analysis, control, optimization and applications. A volume in honor of Wendell H. Fleming, on the occasion of his 70th birthday, 547-566, Birkhäuser, Boston, ISBN 0-8176-4078-9 (1999), doi: 10.1007/978-1-4612-1784-8_33.
https://doi.org/10.1007/978-1-4612-1784-8_33

R. Montgomery, Spanning trees in random graphs. Adv. Math. 356 (2019), 92, doi: 10.1016/j.aim.2019.106793. Id/No 106793.
https://doi.org/10.1016/j.aim.2019.106793

M. Nekovee, Worm epidemics in wireless ad-hoc networks. New J. Phys. 9.6 (2007), paper n. 189, doi: 10.1088/1367-2630/9/6/189.
https://doi.org/10.1088/1367-2630/9/6/189

M. Penrose, The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7.2 (1997), 340-361, doi: 10.1214/aoap/1034625335.
https://doi.org/10.1214/aoap/1034625335

M. Penrose, Random geometric graphs, Oxf. Stud. Probab., vol. 5. Oxford: Oxford University Press (2003).
https://doi.org/10.1093/acprof:oso/9780198506263.001.0001

M. Penrose, Lectures on random geometric graphs. Random graphs, geometry and asymptotic structure, 67-101, Cambridge: Cambridge University Press (2016), doi: 10.1017/CBO9781316479988.004.
https://doi.org/10.1017/CBO9781316479988.004

Metrics

0

Views

0

PDF views