2026-04-14T02:57:49Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/4234382025-07-22T16:07:30Zcom_2072_1033col_2072_452951

Generating Uniform Spanning Trees from conditioned Bienaymé-Galton-Watson trees Vives Batalla, Albert Universitat Politècnica de Catalunya. Departament de Matemàtiques Serra Albó, Oriol Àrees temàtiques de la UPC::Matemàtiques i estadística Graph theory Stochastic processes Random Trees Bienaymé-Galton-Watson trees Grafs, Teoria de Processos estocàstics Classificació AMS::05 Combinatorics::05C Graph theory Classificació AMS::60 Probability theory and stochastic processes::60J Markov processes Aquesta tesi explora el problema de generar arbres generadors uniformes, que són estructures essencials en combinatòria i probabilitat amb aplicacions en teoria de xarxes i física. Utilitzant processos de Bienaymé–Galton–Watson (BGW), proposa una metodologia innovadora per generar arbres generadors de manera uniforme. Mitjançant demostracions rigoroses, mostra que condicionar aquests models estocàstics al nombre de vèrtexs produeix arbres generadors distribuïts uniformement. A més d’explorar propietats estructurals com l’alçada, l’amplada i la distribució de fulles, la tesi proporciona límits inferiors precisos per a l’alçada i l’amplada dels arbres, avalats per demostracions rigoroses. Aquests resultats no només enriqueixen la comprensió teòrica i pràctica dels arbres generadors uniformes, sinó que també connecten els processos estocàstics amb aplicacions combinatòries, oferint noves perspectives i eines per a la generació d’arbres generadors. Esta tesis explora el problema de generar árboles generadores uniformes, que son estructuras esenciales en combinatoria y probabilidad con aplicaciones en teoría de redes y física. Utilizando procesos de Bienaymé–Galton–Watson (BGW), propone una metodología novedosa para generar árboles generadores de manera uniforme. Mediante pruebas rigurosas, demuestra que condicionar estos modelos estocásticos al número de vértices produce árboles generadores distribuidos uniformemente. Además de explorar propiedades estructurales como la altura, la anchura y la distribución de hojas, la tesis proporciona límites inferiores precisos para la altura y la anchura de los árboles, respaldados por demostraciones rigurosas. Estos hallazgos no solo enriquecen la comprensión teórica y práctica de los árboles generadores uniformes, sino que también conectan los procesos estocásticos con aplicaciones combinatorias, ofreciendo nuevas perspectivas y herramientas para la generación de árboles generadores. This thesis explores the problem of generating uniform spanning trees (USTs), which are essential structures in combinatorics and probability with applications in network theory and physics. Using conditioned Bienaymé–Galton–Watson (BGW) processes, it proposes a novel methodology to generate USTs uniformly. Through rigorous proofs, it shows that conditioning these stochastic models on the number of vertices produces uniformly distributed spanning trees. In addition to exploring structural properties such as height, width, and leaf distribution, the thesis provides sharp lower bounds for the height and width of the trees, supported by rigorous proofs. These findings not only enrich the theoretical and practical understanding of USTs but also bridge stochastic processes with combinatorial applications, offering new insights and tools for spanning tree generation. 2025-01-22 Bachelor thesis https://hdl.handle.net/2117/423438 PRISMA-193698 eng http://creativecommons.org/licenses/by-nd/4.0/ Open Access Attribution-NoDerivs 4.0 International application/pdf Universitat Politècnica de Catalunya