Kirchhoff's Matrix Tree Theorem and Uniform Spanning Trees on the Infinite Square Lattice

Abstract

This Bachelor thesis is a literature review, in which we first study uniform spanning trees (USTs) on finite, undirected and simple graphs, after which we extend our analysis to the infinite two-dimensional undirected square lattice L2. In the first part of this thesis, our goal is to prove Kirchhoff's matrix tree theorem. Kirchhoff's theorem states that the number of spanning trees in a finite, simple and undirected graph is given by a formula involving the eigenvalues of the graph Laplacian and the number of vertices in the graph. The proof given in this thesis utilizes Wilson's algorithm, which uses loop-erased random walks to generate a UST. Proving that Wilson's algorithm generates any individual UST with a certain constant probability yields us Kirchhoff’s matrix tree theorem.

In the second part of the thesis, we shift our focus to the uniform spanning tree measures on the infinite two-dimensional undirected square lattice L2. Since there are infinitely many uniform spanning trees on L2, USTs cannot be directly defined on this graph. Therefore, we first define the UST measures on a finite subgraph Lambda, and take the weak limit of the measures as Lambda approaches L2 In this thesis, the subgraph Lambda is a box centered at the origin. There are two natural ways to define the boundary condition of Lambda, called the wired boundary condition and the free boundary condition. These boundary conditions also give rise to two UST measures, called the wired UST measure and the free UST measures. The goal of this second part is first to show that these two UST measures converge weakly to probability measures as Lambda approaches L2, and then to conclude that these weak limits are actually equal.

Tämä kandidaatintyö on kirjallisuuskatsaus, jossa tarkastellaan tasajakautuneita virittäjäpuita (engl. uniform spanning tree) ensin äärellisissä, yksinkertaisissa ja suuntaamattomissa graafeissa ja tämän jälkeen kaksiulotteisessa äärettömässä suuntaamattomassa neliöhilassa L2. Työn ensimmäinen tavoite on todistaa Kirchhoffin matriisipuuteoreema. Kirchhoffin teoreema ilmaisee virittäjäpuiden tarkan lukumäärän äärellisessä, yksinkertaisessa ja suuntaamattomassa graafissa sen Laplacen matriisin (engl. graph Laplacian) ominaisarvojen ja graafin solmujen lukumäärän avulla. Tässä työssä teoreema todistetaan tutkimalla tasajakautuneiden virittäjäpuiden tuottamiseen käytettyä Wilsonin algoritmia, joka hyödyntää silmukattomia satunnaiskävelyjä (engl. loop-erased random walk). Työssä osoitetaan, että Wilsonin algoritmi tuottaa yksittäisiä virittäjäpuita tietyllä vakiotodennäköisyydellä, mikä todistaa samalla Kirchhoffin matriisipuuteoreeman.

Työn toisena tavoitteena on määritellä tasajakautuneen virittäjäpuun todennäköisyysmitta (engl. uniform spanning tree measure) kaksiulotteisessa äärettömässä suuntaamattomassa neliöhilassa L2. Koska virittäjäpuita on L2-graafissa äärettömän monta, tasajakautuneita virittäjäpuita ei voida suoraan määritellä. Tämän vuoksi todennäköisyysmitta määritellään ensin äärellisissä aligraafeissa, josta mitat laajennetaan heikon raja-arvon avulla koko L2-graafiin. Aligraafeina tässä työssä käytettiin origokeskeisiä laatikoita, joihin voidaan määritellä kaksi luonnollista reunaehtoa: vapaa reunaehto (engl. free boundary condition) ja kytketty reunaehto (engl. wired boundary condition). Kumpikin näistä reunaehdoista määrittää oman tasajakautuneen virittäjäpuun todennäköisyysmittansa, jotka molemmat suppenevat heikosti johonkin todennäköisyysmittaan, kun laatikkograafin kokoa kasvatetaan rajatta kohti L2-graafia. Lopuksi työssä osoitetaan, että nämä kaksi tasajakautuneen virittäjäpuun mittaa suppenevat heikosti samaan todennäköisyysmittaan L2-graafissa.