- You are here:
- GT Home
- Home
- News & Events

Series: Combinatorics Seminar

It is known that, relative to any fixed vertex q of a finite graph, there
exists a unique q-reduced divisor (G-Parking function based at q) in
each linear equivalence class of divisors.
In this talk, I will give an efficient algorithm for finding such reduced
divisors. Using this, I will give an explicit and efficient bijection
between the Jacobian group and the set of spanning trees of the graph. Then
I will outline some applications of the main results, including a new
approach to the Random Spanning Tree problem, efficient computation of the
group law in the critical and sandpile group, efficient algorithm for the
chip-firing game of Baker and Norine, and the relation to the Riemann-Roch
theory on finite graphs.

Series: Combinatorics Seminar

Since the seminal work of Erdos and Renyi the phase transition of the largest components in random graphs became one of the central topics in random graph theory and discrete probability theory. Of particular interest in recent years are random graphs with constraints (e.g. degree distribution, forbidden substructures) including random planar graphs. Let G(n,M) be a uniform random graph, a graph picked uniformly at random among all graphs on vertex set [n]={1,...,n} with M edges. Let P(n,M) be a uniform random planar graph, a graph picked uniformly at random among all graphs on vertex set [n] with M edges that are embeddable in the plane. Erodos-Renyi, Bollobas, and Janson-Knuth-Luczak-Pittel amongst others studied the critical behaviour of the largest components in G(n,M) when M= n/2+o(n) with scaling window of size n^{2/3}. For example, when M=n/2+s with s=o(n) and s \gg n^{2/3}, a.a.s. (i.e. with probability tending to 1 as n approaches \infty) G(n,M) contains a unique largest component (the giant component) of size (4+o(1))s. In contract to G(n,M) one can observe two critical behaviour in P(n,M), when M=n/2+o(n) with scaling window of size n^{2/3}, and when M=n+o(n) with scaling window of size n^{3/5}. For example, when M=n/2+s with s = o(n) and s \gg n^{2/3}, a.a.s. the largest component in P(n,M) is of size (2+o(1))s, roughly half the size of the largest component in G(n,M), whereas when M=n+t with t = o(n) and t \gg n^{3/5}, a.a.s. the number of vertices outside the giant component is \Theta(n^{3/2}t^{-3/2}). (Joint work with Tomasz Luczak)

Series: Combinatorics Seminar

We consider the #P complete problem of counting the number of independent
sets in a given graph. Our interest is in understanding the effectiveness of
the popular Belief Propagation (BP) heuristic. BP is a simple and iterative
algorithm that is known to have at least one fixed point. Each fixed point
corresponds to a stationary point of the Bethe free energy (introduced by
Yedidia, Freeman and Weiss (2004) in recognition of Hans Bethe's earlier
work (1935)). The evaluation of the Bethe Free Energy at such a stationary
point (or BP fixed point) leads to the Bethe approximation to the number of
independent sets of the given graph. In general BP is not known to converge
nor is an efficient, convergent procedure for finding stationary points of
the Bethe free energy known. Further, effectiveness of Bethe approximation
is not well understood.
As the first result of this paper, we propose a BP-like algorithm that
always converges to a BP fixed point for any graph. Further, it finds an \epsilon
approximate fixed point in poly(n, 2^d, 1/\epsilon) iterations for a graph of n
nodes with max-degree d. As the next step, we study the quality of this
approximation. Using the recently developed 'loop series' approach by
Chertkov and Chernyak, we establish that for any graph of n nodes with
max-degree d and girth larger than 8d log n, the multiplicative error decays
as 1 + O(n^-\gamma) for some \gamma > 0. This provides a deterministic counting
algorithm that leads to strictly different results compared to a recent
result of Weitz (2006). Finally as a consequence of our results, we prove
that the Bethe approximation is exceedingly good for a random 3-regular
graph conditioned on the Shortest Cycle Cover Conjecture of Alon and Tarsi
(1985) being true.
(Joint work with Venkat Chandrasekaran, Michael Chertkov, David Gamarnik and
Devavrat Shah)

Series: Combinatorics Seminar

Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application of LLL is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d \le 2^k/e other clauses then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment was given by Moser. Subsequently Moser and Tardos gave a randomized algorithm to construct the structures guaranteed by the LLL in a very general algorithmic framework. We will address the main problem left open by Moser and Tardos of derandomizing their algorithm efficiently when the number of other events that any bad event depends on is possibly unbounded. An interesting special case of the open problem is the k-CNF problem when k = \omega(1), that is, when k is more than a constant.

Series: Combinatorics Seminar

In this lecture, I will explain the greedy approximation algorithm on submodular function maximization due to Nemhauser, Wolsey, and Fisher. Then I will apply this algorithm to the problem of approximating an monotone submodular functions by another submodular function with succinct representation. This approximation method is based on the maximum volume ellipsoid inscribed in a centrally symmetric convex body. This is joint work with Michel Goemans, Nick Harvey, and Vahab Mirrokni.

Series: Combinatorics Seminar

In this lecture, I will review combinatorial algorithms for minimizing submodular functions. In particular, I will present a new combinatorial algorithm obtained in my recent joint work with Jim Orlin.

Series: Combinatorics Seminar

In this lecture, I will explain connections between graph theory and submodular optimization. The topics include theorems of Nash-Williams on orientation and detachment of graphs.

Series: Combinatorics Seminar

We consider the Ulam "liar" and "pathological liar" games, natural and well-studied variants of "20 questions" in which the adversarial respondent is permitted to lie some fraction of the time. We give an improved upper bound for the optimal strategy (aka minimum-size covering code), coming within a triply iterated log factor of the so-called "sphere covering" lower bound. The approach is twofold: (1) use a greedy-type strategy until the game is nearly over, then (2) switch to applying the "liar machine" to the remaining Berlekamp position vector. The liar machine is a deterministic (countable) automaton which we show to be very close in behavior to a simple random walk, and this resemblance translates into a nearly optimal strategy for the pathological liar game.

Series: Combinatorics Seminar

We develop an information-theoretic foundation for compound Poisson
approximation and limit theorems (analogous to the corresponding
developments for the central limit theorem and for simple Poisson
approximation). First, sufficient conditions are given under which the
compound Poisson distribution has maximal entropy within a natural
class of probability measures on the nonnegative integers. In
particular, it is shown that a maximum entropy property is valid
if the measures under consideration are log-concave, but that it
fails in general. Second, approximation bounds in the (strong)
relative entropy sense are given for distributional approximation
of sums of independent nonnegative integer valued random variables
by compound Poisson distributions. The proof techniques involve the
use of a notion of local information quantities that generalize the
classical Fisher information used for normal approximation, as well
as the use of ingredients from Stein's method for compound Poisson
approximation. This work is joint with Andrew Barbour (Zurich),
Oliver Johnson (Bristol) and Ioannis Kontoyiannis (AUEB).

Series: Combinatorics Seminar

Let G be a graph and K be a field. We associate to G a projective toric variety X_G over K, the cut variety of the graph G. The cut ideal I_G of the graph G is the ideal defining the cut variety. In this talk, we show that, if G is a subgraph of a subdivision of a book or an outerplanar graph, then the minimal generators are quadrics. Furthermore we describe the generators of the cut ideal of a subdivision of a book.