Circle packing and its applications

One topic of this year's lecture of Saint-flour is about the circle packing, a very nice theory abridging complex analysis, probability and graph theory. I will record some main results in the two week's lectures.

Drawing circle packing : finite and infinite

A circle packing is a collection of disk $P$ to represent a planar graph.$G = (V, E)$, where the center of disk represents the vertex of graph and two disks are tangent if and only if the two vertex are connected.

For a circle  packing, we could draw easily a graph, but could we construct a circle packing from any planar graph ? This is the first question. The question could be answered by two steps : in finite case, we could have an algorithm to solve it by minimizing the energy, which depending only on the radius and for given radius we could draw the graph. Moreover, this drawing unique up to Mobius transform if we add an infinite point to make the out face a triangle.

In infinite case, the question is completed. However,  if we suppose that the bounded degree condition, this is a direct result of compactness.

Reversible Markov chain and electric network

The main question of the topic is to study the recurrence of a reversible Markov chain. In fact, we could always realize it by a electric network by designing conductance on the edges. The recurrence of an infinite simple random walk on this graph (Markov chain) is equivalent to say  $R_{eff}(x \leftrightarrow \infty) = \infty$. Very intuitively, this means that the effective resistance is infinite so we could not go to infinite freely.

Two useful lemma may be Dirichlet and Thomson : the voltage is a harmonic function which minimizes the energy and the current is unit flow which minimize the energy. 

By the electric network, the problem of recurrence is transformed to a problem of analysis of graph.

He-Schramn theorem : Classification of by circle packing

However, it's not easy to analyze the effective resistance. But He-Schramm theorem tells a classification of the infinite graph with only bounded degree : hyperbolic, circle packing in unit disk and transient; or parabolic, circle packing in plane and recurrent.

The main idea is that the circle packing provides a new view point to see the graph. The radius of disk gives something more than the distance on the graph, and this geometric information matches well with the analysis of resistance. If the circle packing is in plane, it could have a log increment of the effective resistance.

Benjamini-Schramm theorem

Our final object should be that of UIPT, which is a random object and the bounded degree condition is missing. To go pass it, a more powerful tool of Benjamini-Schramm theorem is called. This says that we could always start from some limit graph and if the object studied is a local limit of the finite, uniform rooted graph of bounded degree, it's current.

The proof of this theorem is tricky and depends mainly on a very nice estimate called "magic" lemma. Personally, I believe that this lemma has something to do with the maximal inequality and Whitney covering.

Recurrence of UIPT

The final step to prove UIPT requires all the preparation. Moreover, we apply some surgery to replacing some big degree vertex by some trees. This modification makes the Benjamini-Schramm theorem work since it reduces the degree of vertex. Moreover, some quantitative analysis is also needed to calibrate the increment of effective resistance, for example, we should know that the distribution of degree is exponential.


A final remark is that this  seems a nice proof, but how we collect all the necessary result of probability, graph theory and complex analysis ? This is a nice question. And the connection between these three area could be more profound in all senses.