Árboles generadores en grafos aleatorios I

Abstract: En 2015, Kahn conjeturó que para todo ∆ ∊ ℕ, existe un C > 0 tal que para toda secuencia de árboles (Tn)_{n in ℕ}, donde Tn es un árbol en n vértices con ∆(Tn) ≤ ∆, la probabilidad de que el grafo aleatorio G(n,Clogn/n) contenga Tn tiende a 1 cuando n tiende al infinito. Montgomery en el artículo “Spanning trees in random graphs” de 2019, demostró que esta conjetura es cierta. Además, demostró que G(n,Clogn/n) es universal para árboles con grado máximo acotado. En este seminario, veremos un caso específico de este resultado para árboles con grado máximo acotado y muchas hojas apartadas.

Posted on Oct 4, 2022 in Seminario de Grafos, Seminars