Generating uniform spanning trees from conditioned Bienaym´e–Galton–Watson trees

• Vives, Albert ^[1]
  1. [1] Universitat Politècnica de Catalunya

     Universitat Politècnica de Catalunya

     Barcelona, España

     
• Localización: Reports@SCM: an electronic journal of the Societat Catalana de Matemàtiques, ISSN-e 2385-4227, Vol. 10, Nº. 1, 2025, págs. 1-12
• Idioma: inglés
• Títulos paralelos:
  • Generació d'arbres d'expansió uniformes a partir d'arbres de Bienaymé-Galton-Watson condicionats
• Enlaces
  • Texto completo
• Resumen
  • català

    Aquest article explora la generació d’arbres generadors uniformes (UST), fonamentals en combinatòria i probabilitat, amb aplicacions en teoria de xarxes i física. Utilitzant processos de Bienaymé–Galton–Watson (BGW) condicionats a un nombre fix de vèrtexs, s’introdueix un mètode per generar arbres generadors uniformes i s’examinen propietats estructurals com l’alçada i l’amplada.

  • English

    This report explores uniform spanning tree (UST) generation, essential in combinatorics and probability with applications in network theory and physics. Using conditioned Bienaymé–Galton–Watson (BGW) processes, it introduces a method to generate USTs. Rigorous proofs show that conditioning on a fixed number of vertices ensures uniform distribution and let us examine structural properties like height and width.