Organizers : Jeff Kahn, Bhargav Narayanan, and Corrine Yap
Date: December 6, 2021
Speaker: Fan Wei (Princeton)
Title: On the topic of Ramsey multiplicities
Abstract: A common theme in extremal combinatorics is when the random construction is close to optimal. In 1962, Erd\H{o}s conjectured that the random $2$-edge-coloring minimizes the number of monochromatic copies of $K_k$, and the conjecture was extended by Burr and Rosta to all graphs. A classification of graphs whose number of monochromatic copies is minimized by the random $2$-edge-coloring, which are referred to as common graphs, remains a challenging question. In this talk we address some progresses towards open questions in this and related topics, answering questions raised by Jagger, Stovicek, Thomason (1996), Hatami, Hladk\'y, Kr\'al', Norine and Razborov (2012), and Conlon, Fox and Sudakov (2015). This talk is based on joint works with Fox, Kral', Volec, Noel, Norin.
Date: December 3, 2021 at 11:30am via Zoom
Speaker: Rajko Nenadov (Google Zurich)
Title: From Janson's inequality to hypergraph containers
Abstract: Start with a complete graph with n vertices, and choose m edges uniformly at random. This basic model of random graphs is known as the Erdős–Rényi G(n,m) model. One of the fundamental questions is how does the probability that G(n,m) does not contain some chosen graph H change as m goes from 1 to ex(H, n), the largest number of edges in an H-free graph. A standard approach to this question is via Janson's inequality. Surprisingly, and in contrast to the binomial random graph model G(n,p), this approach does not always correctly determine the order of the logarithm of the probability when H is a bipartite graph. In particular, a recent result of Balogh, Morris, and Samotij shows that in this case the probability eventually becomes super-exponentially small in m, whereas Janson's inequality reaches a plateau at an exponential bound.
In the first part of the talk we discuss a new proof of this result and its connection to the celebrated KŁR conjecture. In the second part we discuss applications of these results in Ramsey theory and the motivation for revisiting the problem. Finally, generalising the presented ideas, we give a strengthening of Janson's inequality in the spirit of the so-called hypergraph containers, one of the most influential results in probabilistic combinatorics in the last decade.
Date: November 29, 2021 at 1:30PM via Zoom
Speaker: Swee Hong Chan (UCLA)
Title: Combinatorial atlas for log-concave inequalities
Abstract: The study of log-concave inequalities for combinatorial objects have seen much progress in recent years. One such progress is the solution to the strongest form of Mason's conjecture (independently by Anari et. al. and Brándën-Huh). In the case of graphs, this says that the sequence $f_k$ of the number of forests with $k$ edges, form an ultra log-concave sequence. In this talk, we discuss an improved version of all these results, proved by using a new tool called the combinatorial atlas method. This is a joint work with Igor Pak. This talk is aimed at a general audience.
Date: November 22, 2021
Speaker: Matija Bucic (Princeton, IAS)
Title: Tight Ramsey bounds for multiple copies of a graph
Abstract: The Ramsey number r(G) of a graph G is the smallest integer n such that any 2-colouring of the edges of a clique on n vertices contains a monochromatic copy of G. Determining the Ramsey number of G is a central problem of Ramsey theory with a long history. Despite this there are very few classes of graphs G for which the value of r(G) is known exactly. One such family consists of large vertex disjoint unions of a fixed graph H, we denote such
a graph, consisting of n copies of H by nH. This classical result was proved by Burr, Erdős and Spencer in 1975, who showed r(nH)=(2|H|−α(H))n+c, for some c=c(H), provided n is large enough. Since it did not follow from their arguments, Burr, Erdős and Spencer further asked to determine the number of copies we need to take in order to see this long term behaviour and the value of c. More than 30 years ago Burr gave a way of determining c(H), which only applies when the number of copies n is triple exponential in |H|. We obtain an essentially tight answer to this very old problem of Burr, Erdős and Spencer by showing that the long term behaviour occurs already when the number of copies is single exponential.
Joint work with B. Sudakov.
Date: November 8, 2021
Speaker: Quentin Dubroff (Rutgers)
Title: Linear cover time is exponentially unlikely
Abstract: Proving a 2009 conjecture of Itai Benjamini, we show: For any C, there is a > 0 such that for any simple random walk on an n-vertex graph G, the probability that the first Cn steps of the walk hit every vertex of G is at most exp[-an]. A first ingredient of the proof is a similar statement for Markov chains in which all transition probabilities are less than a suitable function of C. Joint with Jeff Kahn.
Date: November 1, 2021
Speaker: Gil Kalai (Hebrew University of Jerusalem, Reichman University, and NYU)
Title: Helly-type problems: topology, the cascade conjecture, and graph coloring.
*Introductory 16-minute video (not required for the talk itself; if it does not load, try a different browser)
Abstract: Helly-type theorems and problems form a nice area of discrete geometry. In the lecture I will start with the notable theorems of Radon and Tverberg and mention the following conjectural
extension.
For a set X of points x(1), x(2),...,x(n) in some real vector space V we denote by T(X;r) the set of points
in X that belong to the convex hulls of r pairwise disjoint subsets of X. We let t(X;r)=1+dim (T(X;r)).
Radon's theorem asserts that if t(X,1)< |X| then t(X,2) >0.
The first open case of the cascade conjecture asserts that if t(X,1)+t(X,2) < |X| then t(X,3) >0.
In the lecture I will discuss connections with topology and with graph coloring.
Date: October 25, 2021
Speaker: Ronen Eldan (Weizmann)
Title: Localization and Concentration of measures on the discrete hypercube with applications to interacting particle systems.
Abstract: For a probability measure $\mu$ on the discrete hypercube, we are interested in finding sufficient conditions under which $\mu$ either (a) Exhibits concentration (either in the sense of Lipschitz functions, or in a stronger sense such as a Poincare inequality), or (b) Can be expressed as a mixture of a rather small number of "localized" measures which in turn exhibit some sort of concentration. We will present several results in those directions, whose proofs all rely on a localization technique that we will try to explain. We will mention some applications of these results towards mean field approximation, pure state decomposition, mixing time of the Glauber dynamics on Ising models and concentration of negatively dependent variables. Based on joint works with Koehler, Shamir and Zeitouni.
Date: October 18, 2021
Speaker: Xiaoyu He (Princeton)
Title: Long common subsequences between bitstrings
Abstract: A binary code of positive rate is a subset of {0,1}^n with size exponentially large in n. In any binary code of positive rate, one can find twocodewords sharing the same majority bit and thus a common subsequence of length at least n/2. Surprisingly, whether this trivial constant 1/2 could be improved was a longstanding open problem in coding theory, and we solve it in a strengthened form. That is, we show that there exist A, c > 0 such that among any 2^{(log n)^A} bitstrings of length n, some two have a common subsequence of length at least (1/2 + c)n. In the language of coding theory, this means that the zero-rate threshold for coding against adversarial bit-deletion is strictly less than 1/2.
The main idea of the proof is to develop a classification system for bitstrings according to their "oscillation patterns," very roughly analogous to Fourier phases; one key ingredient of this classification is a new entropy-increment variant of the string regularity lemma of Axenovitch, Person, and Puzynina.
Joint work with Venkatesan Guruswami and Ray Li.
Date: October 11, 2021
Speaker: Sepehr Assadi (Rutgers)
Title: Palette Sparsification for Vertex Coloring
Abstract: We prove that for every graph with maximum degree Delta, if we sample O(log n) colors independently and uniformly at random for each vertex from colors {1,...,Delta+1}, then with high probability, there is a proper coloring of G using only the sampled colors for each vertex. We discuss the origins of this problem in sublinear algorithms for graph coloring, some of its connection to classical work in graph theory, and its more recent extensions to other graph coloring problems.
Based on the following joint work:
https://arxiv.org/abs/1807.08886 with Yu Chen and Sanjeev Khanna;
https://arxiv.org/abs/2006.10456 with Noga Alon;
https://arxiv.org/abs/2109.14891 with Andrew Chen and Glenn Sun.
Date: October 4, 2021
Speaker: Corrine Yap (Rutgers)
Title: A Topological Turán Problem
Abstract: The classical Turán problem asks: given a graph H, how many edges can an n-vertex graph have while containing no isomorphic copy of H? By viewing (k+1)-uniform hypergraphs as k-dimensional simplicial complexes, we can ask a topological version of this, (first posed by Nati Linial): given a k-dimensional simplicial complex S, how many facets can an n-vertex k-dimensional simplicial complex have while containing no homeomorphic copy of S? Until recently, little was known for k > 2. In this talk, we give an answer for general k, by way of dependent random choice and the combinatorial notion of a trace-bounded hypergraph. Joint work with Jason Long and Bhargav Narayanan.
Date: September 27, 2021
Speaker: Swee Hong Chan (UCLA)
Title: Combinatorial Atlas for Log-concave Inequalities
Abstract: The study of log-concave inequalities for combinatorial objects has seen much progress in recent years. One such progress is the solution to the strongest form of Mason's conjecture (independently by Anari et. al. and Brándën-Huh) that the f-vectors of matroid independence complex is ultra-log-concave. In this talk, we discuss a new proof of this result through linear algebra, and discuss generalizations to greedoids and posets.
This is joint work with Igor Pak. This talk is aimed at a general audience.
Date: September 20, 2021
Speaker: Sarah Peluse (Princeton/IAS)
Title: Bounds for subsets of $\mathbb{F}_p^n \times \mathbb{F}_p^n$ without L-shaped configurations
Abstract: I will discuss the difficult problem of proving reasonable bounds in the multidimensional generalization of Szemer\’edi’s theorem and describe a proof of such bounds for sets lacking nontrivial configurations of the form $(x,y), (x,y+z), (x,y+2z), (x+z,y)$ in the finite field model setting.
Date: September 13, 2021
Speaker: Benjamin Gunby (Rutgers University)
Title: Upper Tails of Subgraph Counts in Sparse Regular Graphs
Abstract: Given a random graph G, what is the probability that it contains a constant fraction more copies of a fixed graph K than expected? This question has been well-studied when G is the Erdős–Rényi graph G(n,p). When G is instead a random d-regular graph G_{n,d}, when K is also regular this question was answered by Bhattacharya and Dembo. We discuss several new results in the case where K is not regular, including surprising behavior that does not show up in the Erdős–Rényi case.