Organizers : Jeff Kahn, Bhargav Narayanan and Jinyoung Park.
Date: November 25th, 2019
Speaker: Andrey Kupavskii (IAS)
Title: Concentration inequalities for finding rainbow matchings
Abstract: Consider a k-partite k-uniform hypergraph on [n]^k. It is not difficult to see that any such hypergraph with more than (s-1)n^{k-1} edges contains a matching of size s. Aharoni and Berger asked a "transversal" variant of this question: given s hypergraphs, each having more than (s-1)n^{k-1} edges, can we guarantee the existence of an s-matching with the i-th edge coming from the i-th hypergraph? In this talk, I will present our progress on this problem using a certain concentration inequality for the intersection of a family with a random matching.
Joint work with Sergei Kiselev.
Date: November 18th, 2019
Speaker: Mathias Schacht (University of Hamburg)
Title: Canonical Ramsey numbers for edge-ordered hypergraphs
Abstract: We consider quantitative aspects of a Ramsey theoretic result of Leeb. Leeb showed that any sufficiently large complete k-uniform hypergraph with ordered vertex set and ordered edge set must contain one of k!2^k "canonical" subhypergraphs on a given number (say m) of vertices. We obtain estimates for the corresponding Ramsey numbers. In particular, we show that for graphs these Ramsey numbers grow doubly exponential in m. For general hypergraphs the obtained lower and upper bound differ in the height of the tower functions by 2.
This is joint work with M. Tadeu Sales, Chr. Reiher, and V. Rödl.
Date: November 11th, 2019
Speaker: Gwen McKinley (MIT)
Title: Super-logarithmic cliques in dense inhomogeneous random graphs
Abstract: In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1]^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G(n,W), that can be viewed as a generalization of the Erdos-Renyi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order log(n) for the size of the largest clique in G(n,W) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G(n,W) will be of order √n almost surely. We also give a family of examples with clique number of order n^c for any c in (0,1), and some conditions under which the clique number of G(n,W) will be o(√n) or omega(√n). This talk assumes no previous knowledge of graphons.
Date: November 4th, 2019
Speaker: Annika Heckel (LMU Munich)
Title: Non-concentration of the chromatic number of G(n, 1/2)
Abstract: There are many impressive results asserting that the chromatic number of G(n,p) is sharply concentrated. In 1987, Shamir and Spencer showed that for any function p=p(n), the chromatic number of G(n,p) is concentrated on at most about n^(1/2) consecutive values. For sparse random graphs with p<n^(-1/2-epsilon), much sharper concentration is known to hold: Alon and Krivelevich showed that in this case, the chromatic number of G(n,p) is concentrated on only two consecutive values.
However, until recently there had been no non-trivial cases where the chromatic number of G(n,p) was known not to be extremely narrowly concentrated. In 1992, Erdős asked whether the chromatic number of G(n, 1/2) can be shown not to be concentrated on constantly many values. In 2004, Bollobás asked for any non-trivial results asserting a lack of concentration, noting that even the weakest such results would be of interest.
In this talk, we show that the chromatic number of G(n, 1/2) is not concentrated on any sequence of intervals of length n^(1/2-epsilon) for any constant epsilon>0. Up to the epsilon, this exponent matches the upper bound from the classic result of Shamir and Spencer.
Joint work with Oliver Riordan.
Date: October 28th, 2019
Speaker: Peter Ralli (Princeton)
Title: Graph Powering and Spectral Robustness
Abstract: Given an original graph G and positive integer r, graph powering produces a graph connecting vertices from the original graph that are within distance r. I will discuss the use of graph powering for spectral clustering: in a sparse graph the spectrum of the adjacency matrix might be contaminated by non-informational top eigenvalues. It is shown that graph powering regularizes the graph and decontaminates its spectrum in the following sense: if the graph is drawn from the sparse Erdős-Rényi ensemble, which has no spectral gap, it is shown that graph powering produces a `maximal' spectral gap, which is justified by establishing an Alon-Boppana result for powered graphs.
Joint works with E. Abbe, E. Boix, and C. Sandon.
Date: October 21st, 2019
Speaker: Ryan Alweiss (Princeton)
Title: Improved bounds for sunflowers
Abstract: An r-sunflower is a collection of r sets so that the intersection of any two are the same. Given a fixed constant r, how many sets of size w can we have so that no r of them form an r-sunflower? Erdos and Rado introduced this problem in 1960 and proved a bound of w^(w(1+o(1)), and until recently the best known bound was still of this form. Furthermore, Erdos offered $1000 for a proof of a bound of c^w, where c depends on r. We prove a bound of (log w)^(w(1+o(1)).
Joint work with Shachar Lovett, Kewen Wu, and Jiapeng Zhang.
Date: October 14th, 2019
Speaker: Dor Minzer (IAS)
Title: Hypercontractivity, Sharp Thresholds and Extremal Combinatorics
Abstract: The classical hypercontractive inequality for the Boolean hypercube lies at the core of many results in analysis of Boolean functions. Though extensions of the inequality to different domains (e.g. the biased hypercube) are known, they are often times quantitatively weak, making them hard to apply.
We will discuss new forms of this inequality and some of their consequences, such as quantitatively tight version of Bourgains sharp threshold theorem and sharp threshold results for sparse families. Time permitting, we will also discuss applications to two problems in extremal combinatorics: the Erdos matching conjecture, and families avoiding a fixed intersection in the multi-cube, {0,1,...,m-1}^n, for m>=3.
Based on joint works with Peter Keevash, Noam Lifshitz and Eoin Long.
Date: October 7th, 2019
Speaker: Mozhgan Mirzaei (UCSD)
Title: Extremal Configurations in Point-Line Arrangements
Abstract: Click here
Date: September 30th, 2019
Speaker: Joonkyung Lee (University of Hamburg)
Title: On some properties of graph norms
Abstract: Click here
Date: September 23rd, 2019
Speaker: Pablo Soberon (Baruch College, City University of New York)
Title: Exact quantitative versions of Helly’s theorem
Abstract: Helly’s theorem gives a characterization of families of convex sets in R^d with non-empty intersection. Its quantitative versions aim to characterize families of convex sets with “large” intersection, which can be done by giving lower bounds on its volume or diameter. During this talk we will discuss several quantitative Helly-type theorems where the size of the convex sets is witnessed by a low-complexity subset. For instance, we prove Helly-type theorems which conclude that the intersection of a family of convex sets contains an ellipsoid of volume one, or that it contains a box of diameter one. We use methods from classic convexity and from topological combinatorics to obtain our results.
Date: September 16th, 2019
Speaker: Yuval Peled (NYU)
Title: On the threshold for simple connectivity in random 2-complexes
Abstract: Connectivity of random graphs is one of the classical and well-studied topics in random graph theory. We will talk about a topological 2-dimensional counterpart of this question. Consider a random 2-dimensional simplicial complex Y ~ Y_2(n,p) in which each 2-dimensional face is chosen independently with probability p=p(n). Babson, Hoffman and Kahle proved that Y is not simply connected with high probability, provided that p << n^{-1/2}. Here we show that Y is simply connected with high probability if p > (c n)^{-1/2} where the constant c=4^4/3^3, and conjecture that this threshold is sharp.
In fact, we prove that (cn)^{-1/2} is a sharp threshold for the stronger property that every cycle of length 3 is the boundary of a triangulated topological disk that is embedded in Y. The proof uses the Poisson paradigm and a classical theorem of Tutte on the enumeration of planar triangulations.
Joint work with Zur Luria.
Date: September 9th, 2019
Speaker: Jinyoung Park (Rutgers University)
Title: The number of maximal independent sets in the Hamming cube
Abstract: Let Q_n be the n-dimensional Hamming cube (hypercube) and N = 2^n . We prove that the number of maximal independent sets in Q_n is asymptotically 2n2^(N/4), as was conjectured by Ilinca and Kahn in connection with a question of Duffus, Frankl and Rödl. The value is a natural lower bound derived from a connection between maximal independent sets and induced matchings. The proof of the upper bound draws on various tools, among them “stability” results for maximal independent set counts and old and new results on isoperimetric behavior in Q_n.
This is joint with Jeff Kahn.