Organizers : Jeff Kahn, Bhargav Narayanan, Abigail Raz and Jinyoung Park.
Date: April 29th, 2019
Speaker: Jeroen Zuiddam, IAS
Title: The asymptotic spectrum of graphs: duality for Shannon capacity
Abstract: We give a dual description of the Shannon capacity of graphs. The Shannon capacity of a graph is the rate of growth of the independence number under taking the strong power, or in different language, it is the maximum rate at which information can be transmitted over a noisy communication channel. Our dual description gives Shannon capacity as a minimization over the "asymptotic spectrum of graphs", which as a consequence unifies previous results and naturally gives rise to new questions. Besides a gentle introduction to this topic we discuss the general idea of “asymptotic spectra”.
Date: April 22nd, 2019
Speaker: Tomas Juškevičius, Vilnius University
Title: The Littlewood-Offord problem in groups
Abstract: The goal of the talk is to talk about some recent developments regarding the Littlewood-Offord problem. We shall consider this problem in the group theoretic setting. The first results of this type were obtained by Griggs (1993) in cyclic groups and very recently by Tiep and Vu (2015) in certain matrix groups. We shall present an optimal version of such inequalities in arbitary groups. Many variations of the Littlewood-Offord problem have been explored during the years - the so called inverse version (pioneered by Tao and Vu), the resilience version (Bandeira, Ferber and Kwan) etc. In this talk we shall talk about a yet another extension - a non-uniform version of the Littlewood-Offord problem. To be more precise, we shall bound the probability of hitting a particular vector $v$ by a sum of independent symmetric steps in terms of the length of $v$.
The talk is based on joint work with G. Šemetulskis and D. Dzindzalieta.
Date: April 8th, 2019
Speaker: Imre Bárány, Hungarian Academy of Sciences and University College London
Title: Convex cones, integral zonotopes, and their limit shape
Abstract: Given a convex cone C in R^d, an integral zonotope T is the sum of segments [0,v_i] (i=1, ... ,m) where each v_i \in C is a vector with integer coordinates. The endpoint of T is k=\sum_1^m v_i. Let F(C,k) be the family of all integral zonotopes in C whose endpoint is k \in C. We prove that, for large k, the zonotopes in F(C,k) have a limit shape, meaning that, after suitable scaling, the overwhelming majority of the zonotopes in F(C,k) are very close to a fixed convex set which is actually a zonoid. We also establish several combinatorial properties of a typical zonotope in F(C,k). This is joint work with Julien Bureaux and Ben Lund.
Date: April 1st, 2019
Speaker: Jeff Kahn, Rutgers
Title: Hitting times for Shamir's Problem
Abstract: Shamir's Problem (circa 1980) asks: for fixed r at least 3 and n a (large) multiple of r, how large should M be so that M random r-subsets of {1, ... ,n} are likely to contain a perfect matching (i.e., n/r disjoint r-sets)? About ten years ago Johansson, Vu and I proved the natural conjecture that this is true if M > C n ln(n), for some large C=C(r). Some listeners may have heard me talk a while back on the asymptotically precise statement: the same behavior holds for any fixed C> 1/r. Here I'll try to say something about the definitive "hitting time" version.
Date: March 25th, 2019
Speaker: Cole Franks, Rutgers
Title: Three permutations, simplified
Abstract: A k-permutation family on n vertices is a set system consisting of the intervals of k permutations of [n]. Both 1- and 2-permutation families have discrepancy 1, that is, one can color the vertices red and blue such that the number of reds and blues in each edge differs by at most one. That is, their discrepancy is bounded by one. Beck conjectured that the discrepancy of for 3-permutation families is also O(1), but Newman and Nikolov disproved this conjecture in 2011. We give a simpler proof that Newman and Nikolov's sequence of 3-permutation families has discrepancy at least logarithmic in n. We also exhibit a new, tight lower bound for the related notion of root-mean-squared discrepancy of a 6-permutation family.
Date: March 11th, 2019
Speaker: Sophie Spirkl, Rutgers
Title: Detecting an odd hole
Abstract: I will talk about a polynomial-time algorithm that decides whether a graph contains an induced cycle of odd length k > 3. Joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.
Date: February 25th, 2019
Speaker: Vishwas Bhargava, Rutgers
Title: Are factors of Sparse polynomials sparse?
Abstract: The main question we will discuss is, how number of terms of a polynomial(a.k.a Sparsity) relates to number of terms of its factors. This is a fundamental problem which lies at the intersection of Algebra and Combinatorics and attracted attention from several authors, including Erdös, Freud, Rényi, Schinzel and Verdenius.
We show a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular, we show if f is an s-sparse polynomial in n variables, with individual degrees of its variables bounded by d, then the sparsity of each factor of f is bounded by s^{O({d^2\log{n}})}. This is the first nontrivial bound on factor sparsity for d >2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem.
Our work addresses and partially answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials.
Joint work with Shubhangi Saraf and Ilya Volkovich.
Date: February 18th, 2019
Speaker: Yufei Zhao, MIT
Title: A Reverse Sidorenko Inequality
Abstract: We prove a number of tight graph homomorphism inequalities, where, for a fixed H, we wish to maximize the number of homomorphism from G to H (after exponentially normalizing by the size of G) under certain degree constraints on G (e.g., d-regular). A highlight of our results is that, among d-regular graphs of the same size, a disjoint complete bipartite graphs has the most number of proper q-colorings. Our results also extend to irregular graphs and list colorings. These results settle a number of conjectures by Kahn, Galvin-Tetali, Galvin, and Cohen-Csikvári-Perkins-Tetali.
Joint work with Ashwin Sah, Mehtaab Sawhney, and David Stoner
Date: February 11th, 2019
Speaker: Andrei Deneanu, Yale
Title: The probability that a matrix with Rademacher entries is normal
Abstract: We consider a random nxn matrix, M_n, whose entries are independent and identically distributed (i.i.d.) Rademacher random variables (taking values {-1,1} with probability 1/2) and prove
2^{-(0.5+o(1))n^2} <=P (M_n is normal) <= 2^{-(0.302+o(1))n^{2}}.
We conjecture that the lower bound is sharp.
Date: February 4th, 2019
Speaker: Guy Moshkovitz, IAS
Title: A Tight Bound for Hypergraph Regularity
Abstract: The hypergraph regularity lemma — the extension of Szemeredi’s graph regularity lemma to the setting of k-graphs — is one of the most celebrated combinatorial results obtained in the past decade. By now there are various (very different) proofs of this lemma, obtained by Gowers, Rodl, et al. and Tao. Unfortunately, what all these proofs have in common is that they yield partitions whose order is given by the k-th Ackermann function. We prove that such Ackermann-type bounds are unavoidable for every k>=2, thus confirming a prediction of Tao.
Date: January 28th, 2019
Speaker: Lionel Levine, Cornell University
Title: CoEulerian Graphs
Abstract: In joint work with Matt Farrell, http://arxiv.org/abs/1502.04690 we suggest a measure of "Eulerianness" of a finite directed graph, and define a class of "coEulerian" graphs. These are the strongly connected graphs whose Laplacian lattice is as large as possible. As an application, we address a problem posed by Bjorner, Lovasz, and Shor in 1991. They asked how to tell if a given chip-firing game will be finite or infinite. Bjorner and Lovasz gave a decision procedure in 1992, which takes exponential time in the worst case. We show this can be improved to linear time (!) if the graph is coEulerian. A recent theorem of Nguyen and Wood, confirming a conjecture of Koplewitz, shows that coEulerian graphs are not rare: The directed random graph G(n,p) is coEulerian with limiting probability 1/(zeta(2)*zeta(3)*zeta(4)*...). So (in case you were wondering) about 43.58% of all simple directed graphs are coEulerian.