Schedule for: 25w5348 - Frontiers in Combinatorics and Theoretical Computer Science

A set dinner is served daily between 5:30pm and 7:30pm in the Xianghu Lake National Tourist Resort.

Breakfast is served daily between 7 and 9am in the Xianghu Lake National Tourist Resort

A system of linear equations $L$ is said to be norming if a natural functional $t_L(\cdot)$ giving a weighted count for the set of solutions to the system can be used to define a norm on the space of real-valued functions on $\mathbb{F}_q^n$ for every $n > 0$. For example, Gowers uniformity norms arise in this way. We initiate the systematic study of norming linear systems by proving a range of necessary and sufficient conditions for a system to be norming. Some highlights include an isomorphism theorem for the functional $t_L(\cdot)$, a proof that any norming system must be variable-transitive and the classification of all norming systems of rank at most two. Joint work with Seokjoon Cho, Joonkyung Lee, Jozef Skokan and Leo Versteegen.

In 2003, Keevash and Sudakov showed that for $r\geq3$ and $1-\frac{1}{2(r-1)^{2}}\leq\alpha\leq1$, every $K_{r}$-free graph $G$ on $n$ vertices contains $\lfloor\alpha n\rfloor$ vertices spanning at most $\frac{r-2}{2(r-1)}(2\alpha-1)n^{2}$ edges, and if every $\lfloor\alpha n\rfloor$ vertices in $G$ span at least $\frac{r-2}{2(r-1)}(2\alpha-1)n^{2}$ edges, then $G$ is isomorphic to the Tur\'{a}n graph $T_{r-1}(n)$. They conjectured that the range of $\alpha$ can be extended to $1-\frac{1}{r-1}\leq \alpha\leq1$ when $r\geq4$. We show that this conjecture is true for all $r\geq5$. We also prove this conjecture for $r = 4$ and $\alpha\geq 0.76$, which greatly improves the previous range $\alpha\geq 0.861$. This is joint work with Xinyuan Li and Jiaao Li.

I will discuss a combinatorial and probabilistic approach to study sets with small sumsets. Quite surprisingly, while “forgetting” about much of the group structure involved, this approach has led to the resolution of longstanding questions in additive combinatorics, such as Ruzsa’s conjecture on sets with small doubling in abelian groups with bounded exponent. In this talk, we will focus on applications of this framework in the study of Ramsey Cayley graphs, motivated by an old conjecture of Alon, and the study of independent sets in sparse random Cayley graphs, which intimately connects with questions in additive combinatorics. Based on joint works with Alon, Conlon, Fox and Yepremyan.

Over the past decades, a fascinating computational phase transition has been identified in sampling from the hardcore model over weighted independent sets. However, the computational complexity at the critical point remains poorly understood, as previous algorithmic and hardness results all required a constant slack from this threshold. In this talk, I will introduce our recent result on resolving this open question at the critical threshold, thus completing the picture of the computational phase transition. Specifically, we show that for the critical hardcore model, the mixing time of Glauber dynamics is always polynomial and in the worst case super-linear in the number of vertices. Furthermore, we establish that on random regular graphs, rapid mixing holds far beyond the uniqueness threshold, showing that the worst-case and average-case complexities of sampling from the hardcore model are fundamentally different. Based on joint work with Xiaoyu Chen, Zejia Chen, Tianhui Jiang, Yitong Yin, and Xinyuan Zhang.

Lunch is served daily between 11:30am and 1:30pm in the Xianghu Lake National Tourist Resort

In this talk, I will present recent work on the median eigenvalues of subcubic graphs. Specifically, we show that for any connected subcubic graph, except the Heawood graph, the median eigenvalues lie within the interval [-1, 1]. This is joint work with Hricha Acharya and Benjamin Jeter.

We study Turán problems for hypergraphs with an additional uniformity condition on the edge distribution. This kind of Turán problems was introduced by Erdős and Sós in the 1980s but it took more than 30 years until the first non-trivial exact results were obtained. Central to the study of the uniform Turán density of hypergraphs are palette constructions, which were implicitly introduced by Rödl in the 1980s. We prove that palette constructions always yield tight lower bounds, unconditionally confirming present empirical evidence. This results in new and simpler approaches to determining uniform Turán densities, which completely bypass the use of the hypergraph regularity method.

The Turan-type problem is fundamental in extremal graph theory, guiding much of the field's progress. In this talk, we extend these classic results to hypergraphs, focusing on bipartite structures like complete bipartite graphs $K_{s,t}$​. Our result highlights a rare instance in hypergraph Turan problems where the solution depends on the parity of the uniformity.

The graph removal lemma with respect to the edit distance on graphs, which is a classical application of the Szemeredi’s regularity lemma, has numerous applications in combinatorics and theoretical computer science. In this talk, I will talk about some variants of the removal lemmas for graphs and other combinatorial objects with respect to different norms.

Breakfast is served daily between 7 and 9am in the Xianghu Lake National Tourist Resort

I plan to talk about 2-3 open combinatorial problems motivated by recent study of harmonic analysis.

We present notion of balanced coloring of signed graphs. We then show how it helps with stronger connection between minor theory and coloring as well as coloring and topological methods. 

A central problem in extremal combinatorics is concerned with estimating the number $forb(n,H)$ of $n$-vertex $H$-free hypergraphs. While it is well known that $forb(n,H)=2^{(1+o(1))ex(n,H)}$ holds for $k$-uniform hypergraphs that are not $k$-partite, where $ex(n,H)$ is the maximum number of edges in an $n$-vertex $H$-free graph, much less is known for $k$-partite (i.e. degenerate) $k$-graphs. Ferber, McKinley, and Samotij proved that $forb(n, H) = 2^{O(ex(n, H))}$ holds when H is a $k$-partite $k$-graph that satisfies a very mild condition. But it was not known if $forb(n,H)=2^{(1+o(1))ex(n,H)}$ holds for any degenerate $k$-graphs other than matchings. In this talk, we show that $forb(n,H)=2^{(1+o(1))ex(n,H)}$ holds for a wide class of degenerate hypergraphs known as $2$-contractible hypertrees. This is the first known infinite family of degenerate hypergraphs $H$ for which $forb(n,H)=2^{(1+o(1))ex(n,H)}$ holds. As a corollary, we obtain a sharp estimate on the number of $n$-vertex $k$-graphs not containing a linear $\ell$-cycle, for all pairs $k\geq 5, \ell\geq 3$, thus settling a question of Balogh, Narayanan, and Skokan affirmatively for all $k\geq 5, \ell\geq 3$. As the most interesting ingredient of our arguments, we develop a novel supersaturation variant of the celebrated delta systems method, which we hope will find further applications.

I will present a new conjecture claiming that it is computationally hard to distinguish a random regular graph from a random lift of a Ramanujan graph (provided a small amount of noise is applied to the latter). Together with the existence of certain small Ramanujan graphs, this conjecture implies by a statistical reduction argument that many "certification" tasks on random regular graphs are computationally hard. For instance, it implies that no polynomial-time algorithm can with high probability certify that a random 7-regular graph is not 3-colorable, though this is indeed true with high probability. The conjecture implies hardness results of this kind for various combinatorial certification problems on graphs, including certifying bounds on the size of the maximum cut, the independence number, the domination number, and the expansion. Lastly, I will describe a fascinating and challenging family of open problems that this approach leads to, asking to solve certain extremal combinatorics problems over Ramanujan graphs. For instance, how large can an independent set possibly be in a 3-regular Ramanujan graph? Based on joint work with Xifan Yu.

We discuss recent structural results in canonical Ramsey theory for graphs and hypergraphs.

Seymour's celebrated second neighborhood conjecture, now more than thirty years old, states that in every oriented digraph, there is a vertex $u$ such that the size of its second out-neighborhood $N^{++}(u)$ is at least as large as that of its first out-neighborhood $N^+(u)$. We prove the existence of $u$ for which $|N^{++}(u)|\ge0.715538|N^+(u)|$, providing the first improvement to the best known constant factor in over two decades. Joint work with Hao Huang.

I will present a mathematical problem that arises from A/B testing and causal inference. Consider two fixed sequences $a_1, ..., a_n$ and $b_1, ..., b_n$. In an A/B test, we observe, for each index i, exactly one of the two values $a_i$ or $b_i$, revealed with equal probability (not necessarily independently across i). The goal is to estimate the average treatment effect $\frac{1}{n}\sum_{i=1}^{n} (a_i-b_i)$. The classical 95% confidence interval is typically constructed using a normal approximation, but its actual coverage can be far below 95% when n is small. I will present a non-asymptotic solution based on concentration inequalities for random variables. The resulting interval is slightly wider than the Gaussian-based interval but guarantees the target coverage for any n. It raises open questions about how much narrower we can make the interval while still guaranteeing the required coverage. This is joint work with Nicole Pashley and Guanyang Wang.

In this talk, I will discuss several questions related to graph decompositions in random settings. For example, how many edge-disjoint triangles can be packed into $G(n,p)$? For which $d$ can the edges of a random $n$-vertex $d$-regular graph be decomposed into triangles? What is the threshold at which the edges of $K_n$ can be decomposed into triangles, when triangles are made available independently with probability $p$?

In this talk, we discuss recent progress on the determination of Erdos-Rogers functions, which are generalizations of Ramsey numbers.

In 2011, Bollobás and Scott introduced the concept of discrepancy between pairs of hypergraphs, which measures how uniformly and independently the edges of the two hypergraphs are distributed. They posed the natural question: how many $n$-vertex, $k$-uniform hypergraphs of moderate density are needed to ensure that some pair has a large discrepancy? This quantity is denoted as $\text{bs}(k)$. In this work, we establish an upper bound for $\text{bs}(k)$ in terms of a number-theoretic function. As a result, we determine the exact value of $\text{bs}(k)$ for all $2 \leq k \leq 14$ (a new result even for $k = 3$) and show that $\text{bs}(k) = O(k^{0.525})$, significantly improving the previous bound $\text{bs}(k) \leq k + 1$ given by Bollobás and Scott. Additionally, we prove that $\text{bs}(k) \geq 3$ for all $k \geq 3$. This is based on joint work with Yang Dilong and Diep Luong.

A family of $r$ distinct sets $\{A_1,\ldots, A_r\}$ is an {$r$-sunflower} if for all $1 \le i < j\le r$ and $1 \le i' < j'\le r$, we have $A_i\cap A_j = A_{i'}\cap A_{j'}$. Erd\H{o}s and Rado conjectured in 1960 that every family $\mathcal{H}$ of $\ell$-element sets of size at least $K(r)^\ell$ contains an $r$-sunflower, where $K(r)$ is some function that depends only on $r$. We prove that if $\mathcal{H}$ is a family of $\ell$-element sets of VC-dimension at most $d$ and $|\mathcal H| > (C r(\log d+\log^\ast\ell))^\ell$ for some absolute constant $C > 0$, then $\mathcal{H}$ contains an $r$-sunflower. This improves a recent result of Fox, Pach, and Suk. When $d=1$, we obtain a sharp bound, namely that $|\mathcal H| > (r-1)^\ell$ is sufficient. Along the way, we establish a strengthening of the Kahn--Kalai conjecture for set families of bounded VC-dimension, which is of independent interest.

In this talk I will discuss recent progress in approximation schemes and pseudo-polynomial time algorithms for Subset Sum. In Subset Sum, given is a multi-set $X$ of $n$ positive integers and a target $t$, and the goal is to determine whether there exists a subset of $X$ that sums to $t$. I will present an ${O}(n + 1/\eps)$-time algorithm that approximately solves Subset Sum by determining whether some subset of $X$ sums to an integer within $[(1-\epsilon)t, (1+\epsilon)t]$; and then briefly talk about how to extend the method to obtain an ${O}(n + \sqrt{wt})$-time algorithm that exactly solves Subset Sum, where $w$ is the maximum integer in $X$.

Let A be a set of numbers. What is the most efficient way to cover A by a sumset? For the same set A, the answer will depend on the meaning of the word `number'. In this talk, we discuss how much can the answer change as we go from rational numbers to integers and finally to natural numbers. Joint work with Peter van Hintum and Peter Keevash.

An $n$-vertex graph is \emph{degree 3-critical} if it has $2n - 2$ edges and no proper induced subgraph with minimum degree at least 3. In 1988, Erd\H{o}s, Faudree, Gy\'arf\'as, and Schelp asked whether one can always find cycles of all short lengths in these graphs, which was disproven by Narins, Pokrovskiy, and Szab\'o through a construction based on leaf-to-leaf paths in trees whose vertices have degree either 1 or 3. They went on to suggest several weaker conjectures about cycle lengths in degree 3-critical graphs and leaf-to-leaf path lengths in these so-called 1-3 trees. We resolve three of their questions either fully or up to a constant factor. Our main results are the following: 1. every $n$-vertex degree 3-critical graph has $\Omega(\log n)$ distinct cycle lengths; 2. every tree with maximum degree $\Delta \ge 3$ and $\ell$ leaves has at least $\log_{\Delta-1}\, ((\Delta-2)\ell)$ distinct leaf-to-leaf path lengths; 3. for every integer $N\geq 1$, there exist arbitrarily large 1--3 trees which have $O(N^{0.91})$ distinct leaf-to-leaf path lengths smaller than $N$, and, conversely, every 1--3 tree on at least $2^N$ vertices has $\Omega(N^{2/3})$ distinct leaf-to-leaf path lengths smaller than $N$. Several of our proofs rely on purely combinatorial means, while others exploit a connection to an additive problem that might be of independent interest.

Social choice theory studies rules that aggregate individual preferences over alternatives to make collective decisions—such as voters over candidates in voting, or agents over items in matching. One increasingly popular framework in this area is metric distortion, where all individuals and alternatives reside in a common but unknown metric space. The goal is to approximate the true optimum within a small factor, known as the distortion. This framework is best understood in voting. However, in the matching setting, the optimal worst-case distortion remains an open question. This talk considers stochastic distortion settings where agents and items are drawn from a distribution over a metric space. In particular, we show that the distortion of Random Serial Dictatorship (RSD) in certain stochastic settings is exponentially better than its worst-case distortion.

It is known that in matroids the list chromatic number is equal to the chromatic number. We investigate the gap within these pairs of parameters for hypergraphs that are the intersection of a given number $k$ of matroids. We prove that in such hypergraphs the list chromatic number is at most $k$ times the chromatic number and at most $2k-1$ times the maximum chromatic number among the $k$ matroids. The tools used are in part topological. The talk is based on works joint with Ron Aharoni, Eli Berger, and Daniel Kotlar. In this talk, there is no assumption about background knowledge of matroid theory or algebraic topology.