Random Structures and Algorithms 2011

The hard-core model has received much attention in the past couple of decades as a lattice gas model with hard constraints in statistical physics, a multicast model of calls in communication networks, and as a weighted independent set problem in combinatorics, probability and theoretical computer science. In this model, each independent set I in a graph G is weighted proportionally to λ|I|, for a positive real parameter λ. For large λ, computing the partition function (namely, the normalizing constant which makes the weighting a probability distribution on a finite graph) on graphs of maximum degree ∆ ≥ 3, is a well known computationally challenging problem. More concretely, let λc(T∆) denote the critical value for the so-called uniqueness threshold of the hard-core model on the infinite ∆-regular tree; recent breakthrough results of Dror Weitz (2006) and Allan Sly (2010) have identified λc(T∆) as a threshold where the hardness of estimating the above partition function undergoes a computational transition. We focus on the well-studied particular case of the square lattice Z2, and provide a new lower bound for the uniqueness threshold, in particular taking it well above λc(T4). Our technique refines and builds on the tree of self-avoiding walks approach of Weitz, resulting in a new technical sufficient criterion (of wider applicability) for establishing strong spatial mixing (and hence uniqueness) for the hard-core model. Our new criterion achieves better bounds on strong spatial mixing when the graph has extra structure, improving upon what can be achieved by just using the maximum degree. Applying our technique to Z2 we prove that strong spatial mixing holds for all λ < 2.3882, improving upon the work of Weitz that held for λ < λc(T4) = 27/16 = 1.6875. Our results imply a fully-polynomial deterministic approximation algorithm for estimating the partition function, as well as rapid mixing of the associated Glauber dynamics to sample from the hard-core distribution. This is joint work with Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, and Linji Yang. A preprint is available from the arXiv at: http://arxiv.org/abs/1105.0914

Erdös Magic proves the existence of an object but where is it? When the random object has only exponentially small chance of working this is especially challenging. The last years have seen two great successes. Lovász! Moser, followed by Tardos and others, have given an amazingly simple algorithm (the proof of correctness is not so simple!) to find objects whose existence is assured by the Lovász Local Lemma. Six Suffice! Many years ago this speaker showed that n sets on n points could be two colored so that all discrepancies were at most 6√n and long conjectured that no algorithm was possible. Wrong! Bansal, using semidefinite programming in a very nice extension of Goemans-Williamson ideas, finds the coloring . . . and much more.

Szemerédi’s regularity lemma is one of the most powerful tools in graph theory. It was introduced by Szemerédi in his proof of the celebrated Erdös-Turán conjecture on long arithmetic progressions in dense subsets of the integers. Roughly speaking, it says that every large graph can be partitioned into a small number of parts such that the bipartite subgraph between almost all pairs of parts is random- like. One of the most important applications is the graph removal lemma, which roughly says that every graph with few copies of a fixed graph H can be made H-free by removing few edges. It remains a significant problem to estimate the bounds in the regularity lemma and the removal lemma, and their variants. In this talk I discuss recent joint work with David Conlon which makes progress on this problem.

We consider two game theoretic network models - one concerning network formation, and the other concerning bargaining on exchange networks. In the first case, we define the model and show that it has equilibria which support many observed network structures, in- cluding triadic closure and heavy-tailed degree distributions. We do not, however, consider the problem of finding dynamics which con- verge to (some of) these equilibria. In the second case, we study the well-known Nash bargaining equilibria on exchange networks. We construct natural local dynamics, achievable by actual players, and show that this dynamics converges quickly to an approximate Nash bargaining equilibrium. This first part of the talk represents work with C. Borgs, J. Ding and B. Lucier, and the second work with M. Bayati, C. Borgs, Y. Kanoria and A. Montanari.

Over fifty years ago, Erdös and Rényi proved the striking result that the structure of the size-random graph G(n, m) undergoes a phase transition as m, the number of edges, grows from less than n/2 to more than n/2. For the past quarter of a century, this phase transition has been studied in great detail, with a host of detailed results emerging, such as the size of the scaling window, and the behaviour of the giant component outside this window. In particular, Pittel and Wormald proved a deep and difficult theorem about the asymptotic value and limiting distribution of the number of vertices in the giant component above the scaling window of this phase transition. Later, Nachmias and Peres used martingale arguments to study Karp’s exploration process, and obtained a simple proof of a weak form of this result. In this lecture I shall review some of the major theorems concerning the giant component, and then present the simple proof that Riordan and I have found of the full result of Pittel and Wormald.