Balanced spanning trees in random geometric graphs
Time: 11:00 -- Location: https://bbb.lix.polytechnique.fr/b/jer-03d-hps-zlj
In a recent breakthrough, Montgomery showed that the Erdos-Rényi random graph G(n,p) typically contains all n-vertex trees of maximum degree Delta slightly above the (sharp) connectivity threshold. We consider the random geometric graph G_d(n,r) obtained by independently assigning a uniformly random position in [0,1]^d to each of the n vertices of the graph and connecting two vertices by an edge whenever they are at Euclidean distance is at most r. In this talk, we will see that Montgomery's result is very far from being correct for random geometric graphs and identify a sharp threshold for the event that G_d(n,r) contains a class of balanced spanning trees. Our methods also provide a polynomial-time algorithm for finding copies of such trees above the threshold. The talk is based on a joint work with Alberto Espuny Diaz, Dieter Mitsche and Alexandra Wesolek.