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

Series: Combinatorics Seminar

The importance of analyzing big data and in particular very large networks has shown that the traditional notion of a fast algorithm, one that runs in polynomial time, is often insufficient. This is where property testing comes in, whose goal is to very quickly distinguish between objects that satisfy a certain property from those that are ε-far from satisfying that property. It turns out to be closely related to major developments in combinatorics, number theory, discrete geometry, and theoretical computer science. Some of the most general results in this area give "constant query complexity" algorithms, which means the amount of information it looks at is independent of the input size. These results are proved using regularity lemmas or graph limits. Unfortunately, typically the proofs come with no explicit bound for the query complexity, or enormous bounds, of tower-type or worse, as a function of 1/ε, making them impractical. We show by entirely new methods that for permutations, such general results still hold with query complexity only polynomial in 1/ε. We also prove stronger results for graphs through the study of new metrics. These are joint works with Jacob Fox.

Series: Combinatorics Seminar

We present a new algorithm for sampling contingency tables with fixed margins. This algorithm runs in polynomial time for certain broad classes of sparse tables. We compare the performance of our algorithm theoretically and experimentally to existing methods, including the Diaconis-Gangolli Markov chain and sequential importance sampling. Joint work with Igor Pak.

Series: Combinatorics Seminar

Since Erdős–Rényi introduced random graphs in 1959, two closely related models for random graphs have been extensively studied. In the G(n,m) model, a graph is chosen uniformly at random from the collection of all graphs that have n vertices and m edges. In the G(n,p) model, a graph is constructed by connecting each pair of two vertices randomly. Each edge is included in the graph G(n,p) with probability p independently of all other edges. Researchers have studied when the random graph G(n,m) (or G(n,p), resp.) satisfies certain properties in terms of n and m (or n and p, resp.). If G(n,m) (or G(n,p), resp.) satisfies a property with probability close to 1, then one may say that a `typical graph’ with m edges (or expected edge density p, resp.) on n vertices has the property. Random graphs and their variants are also widely used to prove the existence of graphs with certain properties. In this talk, two problems for these categories will be discussed. First, a new approach will be introduced for the problem of the emergence of a giant component of G(n,p), which was first considered by Erdős–Rényi in 1960. Second, a variant of the graph process G(n,1), G(n,2), …, G(n,m), … will be considered to find a tight lower bound for Ramsey number R(3,t) up to a constant factor. (No prior knowledge of graph theory is needed in this talk.)

Series: Combinatorics Seminar

Series: Combinatorics Seminar

Series: Combinatorics Seminar

Let P be a system of unique shortest paths through a graph with real edge weights (i.e. a finite metric). An obvious fact is that P is "consistent," meaning that no two of these paths can intersect each other, split apart, and then intersect again later. But is that all? Can any consistent path system be realized as unique shortest paths in some graph? Or are there more forbidden combinatorial intersection patterns out there to be found?
In this talk, we will characterize exactly which path systems can or can't be realized as unique shortest paths in some graph by giving a complete list of new forbidden intersection patterns along these lines. Our characterization theorem is based on a new connection between graph metrics and certain boundary operators used in some recent graph homology theories. This connection also leads to a principled topological understanding of some of the popular algebraic tricks currently used in the literature on shortest paths. We will also discuss some applications in theoretical computer science.

Series: Combinatorics Seminar

(1) A set D of natural numbers is called t-intersective if every positive upper density subset A of natural numbers contains a (t+1)-length arithmetic progression (AP) whose common differences is in D. Szemeredi's theorem states that the set of all natural numbers is t-intersective for every t. But there are other non-trivial examples like {p-1: p prime}, {1^k,2^k,3^k,\dots} for any k etc. which are t-intersective for every t. A natural question to study is at what density random subsets of natural numbers become t-intersective?
(2) Let X_t be the number of t-APs in a random subset of Z/NZ where each element is selected with probability p independently. Can we prove precise estimates on the probability that X_t is much larger than its expectation?
(3) Locally decodable codes (LDCs) are error correcting codes which allow ultra fast decoding of any message bit from a corrupted encoding of the message. What is the smallest encoding length of such codes?
These seemingly unrelated problems can be addressed by studying the Gaussian width of images of low degree polynomial mappings, which seems to be a fundamental tool applicable to many such problems. Adapting ideas from existing LDC lower bounds, we can prove a general bound on Gaussian width of such sets which reproves the known LDC lower bounds and also implies new bounds for the above mentioned problems. Our bounds are still far from conjectured bounds which suggests that there is plenty of room for improvement. If time permits, we will discuss connections to type constants of injective tensor products of Banach spaces (or chernoff bounds for tensors in simpler terms).
Joint work with Jop Briet.

Series: Combinatorics Seminar

The purpose of this talk is to explain the following result.
Let n > 2 be an integer. Let H be a 3-connected minor of a
3-connected graph G. If G is sufficiently large (relative to
n and the size of H) then G has a 3-connected minor obtained
from H by “adding” K_{3,n} or W_n.

Series: Combinatorics Seminar

We discuss some recent developments on the critical behavior of percolation on finite random networks. In a seminal paper, Aldous (1997) identified the scaling limit for the component sizes in the critical window of phase transition for the Erdos-Renyi random graph (ERRG). Subsequently, there has been a surge in the literature, revealing several interesting scaling limits of these critical components, namely, the component size, diameter, or the component itself when viewed as a metric space. Fascinatingly, when the third moment of the asymptotic degree distribution is finite, many random graph models has been shown to exhibit a universality phenomenon in the sense that their scaling exponents and limit laws are the same as the ERRG. In contrast, when the asymptotic degree distribution is heavy-tailed (having an infinite third moment), the limit law turns out to be fundamentally different from the ERRG case and in particular, becomes sensitive to the precise asymptotics of the highest degree vertices. In this talk, we will focus on random graphs with a prescribed degree sequence. We start by discussing recent scaling limit results, and explore the universality classes that arise from heavy-tailed networks. Of particular interest is a new universality class that arises when the asymptotic degree distribution has an infinite second moment. Not only it gives rise to a completely new universality class, it also exhibits several surprising features that have never been observed in any other universality class so far. This is based on joint works with Shankar Bhamidi, Remco van der Hofstad, Johan van Leeuwaarden and Sanchayan Sen.

Series: Combinatorics Seminar

How can d+k vectors in R^d be arranged so that they are as close
to orthogonal as possible? We show intimate connection of this problem to
the problem of equiangular lines, and to the problem of bounding the first
moment of isotropic measures. Using these connections, we pin down the
answer precisely for several values of k and establish asymptotics for all k.
Joint work with Chris Cox.