Seminars and Colloquia by Series

Friday, January 22, 2010 - 15:05 , Location: Skiles 255 , Keni-chi Kawarabayashi , National Institute of Informatics , Organizer: Prasad Tetali
Hajos' conjecture is false, and it seems that graphs without a subdivision of a big complete graph do not behave as well as those without a minor of a big complete graph. In fact, the graph minor theorem (a proof of Wagner's conjecture) is not true if we replace the minor relation by the subdivision relation. I.e, For every infinite sequence G_1,G_2, ... of graphs, there exist distinct integers i < j such that G_i is a minor of G_j, but if we replace ''minor" by ''subdivision", this is no longer true. This is partially because we do not really know what the graphs without a subdivision of a big complete graph look like. In this talk, we shall discuss this issue. In particular, assuming some moderate connectivity condition, we can say something, which we will present in this talk. Topics also include coloring graphs without a subdivision of a large complete graph, and some algorithmic aspects. Some of the results are joint work with Theo Muller.
Friday, November 20, 2009 - 15:05 , Location: Skiles 255 , Mark Ellingham , Vanderbilt University , Organizer: Xingxing Yu

Linkage involves finding a set of internally disjoint paths in a graph with specified endpoints. Given graphs G and H, we say G is H-linked if for every injective mapping f:V(H) -> V(G) we can find a subgraph H' of G which is a subdivision of H, with f(v) being the vertex of H' corresponding to each vertex v of H. We describe two results on H-linkage for small graphs H.

(1) Goddard showed that 4-connected planar triangulations are 4-ordered, or in other words C_4-linked. We strengthen this by showing that 4-connected planar triangulations are (K_4-e)-linked.

(2) Xingxing Yu characterized certain graphs related to P_4-linkage. We use his characterization to show that every 7-connected graph is P_4-linked, and to construct 6-connected graphs that are not P_4-linked.

This is joint work with Michael D. Plummer and Gexin Yu.

Friday, November 13, 2009 - 15:05 , Location: Skiles 255 , Miklos Simonovits , Alfred Renyi Institute, Budapest, Hungary , Organizer: Robin Thomas

Stability methods are often used in extremal graph theory, Ramsey theory and similar areas, where an extremal problem is to be solved and

  1. we have a conjecture about the structure of the conjectured extremal configurations and according to our conjecture, it has some given property \mathcal P;
  2. we can prove that all the almost extremal structures are near to the property \mathcal P, in some sense;
  3. if we knew that if a structure is near to the property \mathcal P and is extremal, then it is already the conjectured structure.

Of course, stability methods can also be used in other cases, but we restrict ourselves to the above two areas.

In my lecture I will give an introduction to the applications of the stability methods in extremal graph theory, describe cases in extremal graph theory, extremal hypergraph theory, in the Erdos-Frankl-Rold (= generalized Erdos-Kleitman-Rothschild theory) ...

In the second part of my lecture I shall describe the application of this method to the Erdos-Sos conjecture. This is part of our work with Ajtai, Komlos and Szemeredi.

Friday, November 6, 2009 - 15:05 , Location: Skiles 255 , Albert Bush , School of Mathematics, Georgia Tech , Organizer: Xingxing Yu

This is joint work with Dr. Yi Zhao.

Graph tiling problems can be summarized as follows: given a graph H, what conditions do we need to find a spanning subgraph of some larger graph G that consists entirely of disjoint copies of H. The most familiar example of a graph tiling problem is finding a matching in a graph. With the Regularity Lemma and the Blow-up Lemma as our main tools, we prove a degree condition that guarantees an arbitrary bipartite graph G will be tiled by an arbitrary bipartite graph H. We also prove this degree condition is best possible up to a constant. This answers a question of Zhao and proves an asymptotic version of a result of Kuhn and Osthus for bipartite graphs.
Friday, October 16, 2009 - 15:05 , Location: Skiles 255 , Nina Balcan , Computing Science & Systems, Georgia Tech , Organizer: Prasad Tetali
There has been substantial work on approximation algorithms for clustering data under distance-based objective functions such as k-median, k-means, and min-sum objectives. This work is fueled in part by the hope that approximating these objectives well will indeed yield more accurate solutions. That is, for problems such as clustering proteins by function, or clustering images by subject, there is some unknown correct "target" clustering and the implicit assumption is that clusterings that are approximately optimal in terms of these distance-based measures are also approximately correct in terms of error with respect to the target. In this work we show that if we make this implicit assumption explicit -- that is, if we assume that any c-approximation to the given clustering objective Phi is epsilon-close to the target -- then we can produce clusterings that are O(epsilon)-close to the target, even for values c for which obtaining a c-approximation is NP-hard. In particular, for the k-median, k-means, and min-sum objectives, we show that we can achieve this guarantee for any constant c > 1. Our results show how by explicitly considering the alignment between the objective function used and the true underlying clustering goals, one can bypass computational barriers and perform as if these objectives were computationally substantially easier. This talk is based on joint work with Avrim Blum and Anupam Gupta (SODA 2009), Mark Braverman (COLT 2009), and Heiko Roeglin and Shang-Hua Teng (ALT 2009).
Friday, October 9, 2009 - 15:05 , Location: Skiles 255 , Ernie Croot , School of Math, Georgia Tech , Organizer: Prasad Tetali
In this talk I will discuss a new technique discovered by myself and Olof Sisask which produces many new insights in additive combinatorics, not to mention new proofs of classical theorems previously proved only using harmonic analysis. Among these new proofs is one for Roth's theorem on three-term arithmetic progressions, which gives the best bounds so far achieved by any combinatorial method. And another is a new proof that positive density subsets of the integers mod p contain very long arithmetic progressions, first proved by Bourgain, and improved upon by Ben Green and Tom Sanders. If time permits, I will discuss how the method can be applied to the 2D corners problem.
Friday, October 2, 2009 - 15:05 , Location: Skiles 255 , Farbod Shokrieh , Georgia Tech , , Organizer: Prasad Tetali
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.
Friday, September 25, 2009 - 15:00 , Location: Skiles 255 , Mihyun Kang , Technische Universitat Berlin , Organizer: Prasad Tetali
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)
Friday, September 11, 2009 - 15:00 , Location: Skiles 255 , Jinwoo Shin , MIT , Organizer: Prasad Tetali
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)
Friday, September 4, 2009 - 15:00 , Location: Skiles 255 , Karthekeyan Chandrasekaran , College of Computing , Organizer: Prasad Tetali
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.