Organizers : Jeff Kahn, Bhargav Narayanan, Swee Hong Chan, and Quentin Dubroff

Date: April 29, 2024

Speaker: Xiaoyu He (Princeton)

Title: An exotic growth rate in Ramsey theory 

Abstract: The vast majority of natural Ramsey numbers studied to date have polynomial or exponential growth rates. We give a hypergraph Ramsey number - perhaps the simplest of its kind - with an unusual intermediate growth rate. Namely, let S_n be the 3-uniform star (with n+1 vertices and (n choose 2) edges) and let K_4 be the complete 3-uniform hypergraph on 4 vertices. We show  2^{c(\log n)^2} < r(K_4, S_n) < 2^{n^{2/3+o(1)}}.

Based on joint work with David Conlon, Jacob Fox, Dhruv Mubayi, Andrew Suk, and Jacques Verstraete.

Date: April 22, 2024

Speaker: Aristotelis Chaniotis (Waterloo)

Title: Local structure of graphs of large K_r-free chromatic number

Abstract: For r>=2, the K_r-free chromatic number of a graph G, denoted by χ_r(G), is the minimum size of a partition of the set of vertices of G into parts each of which induces a K_r-free graph. In this setting, the K_2-free chromatic number is the usual chromatic number.

Generalizing the notion of χ-boundedness, we say that a hereditary class of graphs is χ_r-bounded if there exists a function which provides an upper bound for the K_r-free chromatic number of each graph of the class in terms of the graph’s clique number. 

With an emphasis on a generalization of the Gyárfás-Sumner conjecture for χ_r-bounded classes of graphs and on applications on polynomial χ-boundedness, I will discuss some recent developments on χ_r-boundedness and related open problems. 

Based on joint work with Mathieu Rundström and Sophie Spirkl.

Date: April 8, 2024

Speaker: Micha Christoph (ETH)

Title: Resolution of the Kohayakawa--Kreuter conjecture 

Abstract: A graph G is said to be Ramsey for a tuple of graphs (H_1,...,H_r) if every r-coloring of the edges of G contains a monochromatic copy of H_i in color i, for some i. A fundamental question at the intersection of Ramsey theory and the theory of random graphs is to determine the threshold at which the binomial random graph G_{n,p} becomes a.a.s. Ramsey for a fixed tuple (H_1,...,H_r), and a famous conjecture of Kohayakawa and Kreuter predicts this threshold. Earlier work of Mousset-Nenadov-Samotij, Bowtell-Hancock-Hyde, and Kuperwasser--Samotij--Wigderson has reduced this probabilistic problem to a deterministic graph decomposition conjecture. We show that this deterministic graph decomposition conjecture is true. 

Date: April 1, 2024

Speaker: Elena Kosygina (Baruch) 

Title: Generalized Ray-Knight theorems: their applications and limitations 

Abstract: Generalized Ray-Knight theorems for edge local times have proved to be a very useful tool for studying the limiting behavior of a number of models of self-interacting random walks (SIRWs) on integers. I shall describe several classes of SIRWs introduced and studied by Balint Toth in late 1990s and discuss applications and limitations of generalized Ray-Knight theorems in establishing functional limit theorems for these models. The talk is based on joint work with Thomas Mountford (EPFL) and Jonathon Peterson (Purdue University).

Date: March 25, 2024

Speaker: Tomas Juskevicius (Vilnius University)

Title: Anticoncentration via the strong perfect graph theorem 

Abstract: In this talk we shall address anticoncentration inequalities for sums of random vectors. In particular, we shall discuss how to asymptotically establish two conjectures: one by Lee Jones (1978) and another by Leader-Radcliffe (1994). Perhaps surprisingly, the main ingredient to establish the latter result is the strong perfect graph theorem by Chudnovsky, Robertson, Seymour and Thomas (2002). Most of the talk will be centered not so much on the proofs, but more on how two seemingly different branches of mathematics can be linked in a useful way (Probability and Structural Graph Theory). The talk is based on joint work with V. Kurauskas (Vilnius University, Lithuania). 

Date: March 18, 2024

Speaker: Matija Bucic (Princeton)

Title: Essentially tight bounds for rainbow cycles in proper edge-colourings 

Abstract: An edge-coloured graph is said to be rainbow if it uses no colour more than once. Extremal problems involving rainbow objects have been a focus of much research as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge-coloured graph on n vertices without a rainbow cycle. Improving upon a series of earlier bounds, Tomon proved an upper bound of (log n)^(2+o(1)) for this question. Very recently, Janzer-Sudakov and Kim-Lee-Liu-Tran independently removed the o(1) term in Tomon's bound. We show that the answer to the question is equal to (log n)^(1+o(1)).  

Joint work with: Noga Alon, Lisa Sauermann, Dmitrii Zakharov and Or Zamir.

Date: March 4, 2024

Speaker: Yuzhou Gu (IAS)

Title: Weak recovery threshold for the hypergraph stochastic block model 

Abstract: We study the weak recovery problem on the r-uniform hypergraph stochastic block model (r-HSBM) with two balanced communities. In this model, n vertices are randomly divided into two communities, and size-r hyperedges are added randomly depending on whether all vertices in the hyperedge are in the same community. The goal of the weak recovery problem is to recover a non-trivial fraction of the communities given the hypergraph. This model generalizes the stochastic block model and has relationships with constraint satisfaction problems such as NAE-SAT and hypergraph bicoloring.

In the graph (r=2) case, Massoulié '14 and Mossel-Neeman-Sly '15 established that possibility of weak recovery is governed by a simple formula called the Kesten-Stigum (KS) threshold. For general r, Pal-Zhu '21 proved that weak recovery is always possible above the KS threshold. In this talk I will discuss a number of results regarding tightness of the KS threshold. In particular, we show that KS is tight when (a) r is at most four, or (b) r is at most six, and average degree d is large enough, or (c) d is small enough; KS is not tight when r is at least seven, and d is large. The impossibility results are proved using channel comparison tools from information theory. The possibility results are proved using a simple inefficient estimator.

Based on joint works with Aaradhya Pandey and Yury Polyanskiy. 

Date: February 26, 2024

Speaker: Yotam Dikstein (Weizmann)

Title: New Sparse Agreement Testers 

Abstract: Agreement testing (aka direct product testing), checks if consistent local information reveals global structure. Beyond its theoretical connections to probabilistic checkable proofs (PCPs), constructing agreement testers is a fundamental combinatorial question that has exciting applications in coding theory and hardness amplification.

     Let (V,S) be a hypergraph with vertices. The direct product encoding encodes a function $g:V \to \{0,1\}$ by its restrictions $F(g)=\{g|_s: s\in S\}$. Agreement testing asks the inverse question: Given $F=\{f_s:s \to \{0,1\}: s \in S\}$, can we test whether $F$ is non-trivially close to an encoding of some $g:V \to \{0,1\}$, by querying only two random functions? The test we consider samples two random $s,s' \in S$ and accepts if $f_s = f_{s'}$ on the shared intersection. In this talk we focus on the more challenging 1%-regime, where the probability that $F$ passes the test is non-negligible, but small (1%). Hypergraphs where passing the test with non-negligible probabiliy implies correlation with some $F(g)$, are called sound agreement tests.

    Constructing sound agreement tests was studied in the 90', and works in complexity inspired the goal of constructing agreement tests where the size of $S$ grows as slowly as possible with respect to $V$. Such sparse tests are an important prerequisite for derandomizing some fundamental PCP constructions.

    In the 99%-regime, Dinur and Kaufman showed existence agreement tests where $|S|=O(|V|)$ using high dimensional expanders, and conjectured that the same is true for the 1%-regime. Later on however, it was shown that some high dimensional expanders are not sound agreement tests in the 1% regime.

    In this work we overcome the barrier, and construct novel agreement tests for the 1%-regime, where $|S|=O(|V|)$. Quite surprisingly, constructing such tests requires the hypergraph to have no small connected topological covers, along with other more combinatorial properties. We construct such hypergraphs using subgroups of the symplectic group over the piadic numbers, along with a variety of other topological and combinatorial tools from high dimensional expander theory.

    This talk is based on joint work with Irit Dinur and Alex Lubotzky.

Date: February 19, 2024

Speaker: Yang Liu (IAS)

Title: Sparsifying generalized linear models 

Abstract: We consider the sparsification of sums $F : \mathbb{R}^n \to \mathbb{R}_+$ where $F(x) = f_1(\langle a_1,x \rangle) + ... + f_m(\langle a_m,x \rangle)$ for vectors $a_1, ..., a_m \in \mathbb{R}^n$ and functions $f_1, ... ,f_m : \mathbb{R} \to \mathbb{R}_+$. We show that $(1+\epsilon)$-approximate sparsifiers of $F$ with support size $\frac{n}{\epsilon^2} (\log \frac{n}{\epsilon})^{O(1)}$ exist whenever the functions $f_1, ... ,f_m$ are symmetric, monotone, and satisfy natural growth bounds. Additionally, we give efficient algorithms to compute such a sparsifier assuming each $f_i$ can be evaluated efficiently. Our results generalize the classic case of $\ell_p$ sparsification, where $f_i(z) = |z|^p$, for $p \in (0, 2]$, and give the first near-linear size sparsifiers in the well-studied setting of the Huber loss function and its generalizations, e.g., $f_i(z) = \min\{|z|^p, |z|^2\}$ for $0 ＜ p \leq 2$. Our sparsification algorithm can be applied to give near-optimal reductions for optimizing a variety of generalized linear models including $\ell_p$ regression for $p \in (1, 2]$ to high accuracy, via solving $(\log n)^{O(1)}$ sparse regression instances with $m \le n(\log n)^{O(1)}$, plus runtime proportional to the number of nonzero entries in the vectors $a_1, \dots, a_m$. Based on joint work with Arun Jambulapati, James Lee, and Aaron Sidford. 

Date: February 12, 2024

Speaker: Pablo Soberon (CUNY)

Title: Envy-free distributions in high dimensions 

Abstract: In fair partition results, we aim to distribute resources among several competing players.  One family of problems, known as mass partition problems, studies scenarios where we can guarantee that every player agrees that the value of each part is the same.  Another type of results are envy-free partitions, in which each player agrees that they received the best part according to their subjective preferences.  Envy-free partitions are well studied in dimension 1, and often allow us to satisfy more players than those in mass partition results.  In this talk, we discuss common generalizations to both types of results.  We focus on partitions in R^2 with few lines, and partitions in R^d into convex parts. 

Date: February 5, 2024

Speaker: Peter Winkler (Dartmouth)

Title: Sets that Support a Joint Distribution 

Abstract: Given a closed set on the plane and two probability distributions on the real line, when are there random variables with the given distributions whose joint distribution is supported by the given set?

We consider both discrete and continuous distributions; in the latter case, the problem is equivalent to asking which sets in the unit square can support a permuton, i.e., a Borel distribution on the unit square with uniform marginals.

Joint work with Chris Coscia and Martin Tassy.

Date: January 29, 2024

Speaker: Ron Peled (Tel Aviv/IAS)

Title: Minimal cuts in the Z^D lattice with random capacities 

Abstract: Endow the edges of the Z^D lattice with independent and identically distributed random capacities (e.g., uniformly distributed on [a,b] for some b>a>0). We wish to study the minimal cuts in the resulting network. Our focus is on the following setup: Consider the cube {-L,..., L}^D and the minimal cut separating the "upper" and "lower" halves of the boundary of the cube. How flat is this cut?

It is believed that the minimal cut is (power-law) rough in dimensions D=2,3 and flat in dimensions D>=6, and that it undergoes a roughening phase transition in dimension D=4 as the capacity distribution becomes more spread out. The case of dimension D=5 is more subtle. We discuss these predictions as well as rigorous results, and further mention rigorous results on related models of minimal surfaces in random environment.

The above combinatorial problem is further motivated by relations with first-passage percolation and disordered statistical physics models.

Based on joint works with Michal Bassan and Shoni Gilboa and with Barbara Dembin, Dor Elboim and Daniel Hadas.