# Combinatorics & Graph Theory Seminar

**Upcoming Seminar talks (AY 2023/24):**

**Aug 30 (W), 2023** at 1pm, S17-05-11, **Max Wenqiang Xu (Stanford University)**, “Two recent applications of multiplicative energy”.

**Abstract:**

Multiplicative energy of a set \(A\) is defined to be the total number of solutions to the equation: \(m_1m_2=n_1n_2\) where the \(m_i\)’s and \(n_i\)’s are in the set \(A\).

The first application is to use this quantity to study the product set of set A. Yunkun Zhou and I managed to solve some conjectures of Elekes-Ruzsa by studying this quantity.

The second application is to use this quantity to prove central limit theorems for a random model of arithmetic functions. The random model nowadays is called random multiplicative functions. This part is mainly based on joint work with K. Soundararajan.

**Sep 6 (W), 2023** at 1pm, S17-05-11, **Yunkun Zhou (Stanford University)**, “Ramsey and Turán numbers of sparse hypergraphs”.

**Abstract:**

Degeneracy plays an important role in understanding Turán- and Ramsey-type properties of graphs. Unfortunately, the usual hypergraphical generalization of degeneracy fails to capture these properties. We define the skeletal degeneracy of a \(k\)-uniform hypergraph as the degeneracy of its \(1\)-skeleton (i.e., the graph formed by replacing every \(k\)-edge by a \(k\)-clique). We prove that skeletal degeneracy controls hypergraph Turán and Ramsey numbers in a similar manner to (graphical) degeneracy.

Specifically, we show that k-uniform hypergraphs with bounded skeletal degeneracy have linear Ramsey number. This is the hypergraph analogue of the Burr-Erdős conjecture (proved by Lee). In addition, we give upper and lower bounds of the same shape for the Turán number of a \(k\)-uniform \(k\)-partite hypergraph in terms of its skeletal degeneracy. The proofs of both results use the technique of dependent random choice. In addition, the proof of our Ramsey result uses the `random greedy process’ introduced by Lee in his resolution of the Burr-Erdős conjecture.

**Past talks (click ► for the abstract):**

**Sep 23 (W), 2023** at 1pm, S17-04-04, **Lim Jeck (Caltech)**, “Everywhere unbalanced configurations”.

**Abstract:**

An old problem in discrete geometry, originating with Kupitz, asks whether there is a fixed natural number \(k\) such that every finite set of points in the plane has a line through at least two of its points where the number of points on either side of this line differ by at most \(k\). We give a negative answer to a natural variant of this problem, showing that for every natural number \(k\) there exists a finite set of points in the plane together with a pseudoline arrangement such that each pseudoline contains at least two points and there is a pseudoline through any pair of points where the number of points on either side of each pseudoline differ by at least \(k\).

**Apr 5 (W), 2023** at 4pm, Zoom (pwd: 23571113),** Noam Lifshitz (Hebrew University)**, “Product free sets in groups”.

**Abstract:**

A subset \(A\) of a group is said to be product free if for all elements \(a, b\) in \(A\) their product \(ab\) is not in \(A\). In 1985 Babai and Sos posed the problem of determining the largest product free sets in the alternating group. We solve this problem completely when \(n\) is sufficiently large.

Our proof combines representation theory with a recent machinery we developed called `hypercontractvity for global functions’.

Based on joint works with Keevash, Long, and Minzer.

**Mar 29 (W), 2023** at 4pm, Zoom (pwd: 23571113), **Xizhi Liu (University of Warwick)**, “A step towards a general density Corrádi-Hajnal Theorem”.

**Abstract:**

**Mar 22 (W), 2023** at 3pm, Zoom (pwd: 23571113), **Huy Tuan Pham (Stanford University)**, “Ramsey graphs and additive combinatorics without addition”.

**Abstract:**

**Mar 15 (W), 2023** at 10am**,** Zoom (pwd: 23571113), **Cosmin Pohoata (Institute for Advanced Study)**, “Rainbow matchings in hypergraphs”.

**Abstract:**

**Mar 10 (F), 2023** at 2pm, S17-04-06, **Jie Ma (Univ. of Science and Technology of China)**, “Supersaturation beyond color-critical graphs”, jointly with YMLS.

**Abstract:**

**Mar 1 (W), 2023 **at 3pm, Zoom (pwd: 23571113), **Shukun Wu (Caltech)**, “A brief introduction to the Kakeya conjecture”.

**Abstract:**

**Feb 15 (W), 2023** at 4pm, Zoom (pwd: 23571113), **Akshat Mudgal (University of Oxford)**, “Difference sets in higher dimensions“

**Abstract:**

**Nov 9 (W), 2022** at 2pm, S17-04-04, **Debsoumya Chakraborti (Institute for Basic Science)**, “Rainbow generalizations of combinatorial results“

**Abstract:** There have been extensive studies on the following question: given \(k\) graphs \(G_1, \cdots, G_k\) over a common vertex set of size \(n\), what conditions on \(G_i\) ensure a rainbow copy of \(H\), i.e., a copy of \(H\) with at most one edge from each \(G_i\)? In this talk, we will survey some results on this topic.

Joos and Kim showed that for \(k=n\), the condition that each \(G_i\) has minimum degree at least \(n/2\) confirms a rainbow Hamiltonian cycle. This generalizes the classical Dirac’s theorem. In this talk, we will discuss our recent rainbow generalizations of some results on embedding Hamiltonian cycles in tournaments. This part of the talk will be based on a joint work with Jaehoon Kim, Hyunwoo Lee, and Jaehyeon Seo.

**Nov 2 (W), 2022** at 2pm, **Zoom (pwd: 23571113), Zilin Jiang (Arizona State University)**, “Forbidden subgraphs and spherical two-distance sets”

**Abstract: **A set of unit vectors in a Euclidean space is called a spherical two-distance set if the pairwise inner products of these vectors assume only two values α and β. It is known that the maximum size of a spherical two-distance grows quadratically as the dimension of the Euclidean space grows. However when the values α and β are held fixed, a very intricate behavior of the maximum size emerges. Building on our recent resolution in the equiangular case, that is β = -α, we make a plausible conjecture which connects this behavior with spectral theory of signed graphs in the regime β < 0 ≤ α, and we confirm this conjecture when α + 2β < 0 or (1 – α)/(β-α) < 2.0198. Joint work with Alexandr Polyanskii, Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao.

**Oct 26 (W), 2022** at 2pm, **Zoom**** (pwd: 23571113)**, **Yuval Wigderson**** (Tel Aviv)**, “Ramsey numbers upon vertex deletion”

**Abstract: **The Ramsey number \(r(G)\) of a graph \(G\) is the minimum \(N\) so that every red/blue edge-coloring of \(K_N\) contains a monochromatic copy of \(G\). Conlon, Fox, and Sudakov conjectured that if we delete a single vertex from \(G\), then the Ramsey number can decrease by at most a constant factor. Though very natural (and true in a variety of special cases), this conjecture turns out to be false in general. In this talk, I’ll explain how one disproves this conjecture, as well as the connections this problem has to a number of other questions in Ramsey theory.

**Oct 19 (W), 2022** at 2pm, S17-04-04, **Yang Tianchi (National University of Singapore)**, “Extremal results on 4-cycles”

**Abstract:** The study of the 4-cycle has an important enlightening effect on the development

of Turan type problems, especially the degenerate cases. In this talk, we focus on two conjectures about 4-cycles: a conjecture of Erdos on the upper bound of the Turan number ex(n,\(C_4\)), and a conjecture of Erdos-Simonovits on the supersaturation problem of 4-cycles.

**Oct 12 (W), 2022** at 10am, **Zoom (pwd: 23571113), Mehtaab Sawhney (MIT)**, “Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture”

**Abstract: **An \(n\)-vertex graph is called \(C\)-Ramsey if it has no clique or independent set of size \(C\log_2 n\) (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge-statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a \(C\)-Ramsey graph. This brings together two ongoing lines of research: the study of “random-like” properties of Ramsey graphs and the study of small-ball probability for low-degree polynomials of independent random variables. The proof proceeds via an “additive structure” dichotomy on the degree sequence, and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics, and low-rank approximation. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which he offered one of his notorious monetary prizes.

Joint w. Matthew Kwan, Ashwin Sah, and Lisa Sauermann.

**Oct 5 (W), 2022** at 3pm, S17-05-12, **Abdul Basit**** (Johns Hopkins University)**, “Some results on Tuza’s conjecture and a generalization to hypergraphs”

**Abstract:** A celebrated conjecture of Tuza says that in any (finite) graph, the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. We will discuss some recent results regarding a generalization of this conjecture to hypergraphs which was proposed by Aharoni and Zerbib.

**Sep 28 (W), 2022** at 3pm, **Zoom (pwd: 23571113), István Tomon (Umeå University)**, “Minimal hyperplane covers of finite spaces and applications”

**
Abstract:** At least how many hyperplanes are needed to cover the finite space \(\mathbb{F}_p^{n}\) if we require that the normal vectors of the hyperplanes span the whole space, and none of the hyperplanes is redundant? This question is related to a number of long-standing conjectures in linear algebra and group theory, such as the Alon-Jaeger-Tarsi conjecture on non-vanishing linear maps, the Additive Basis conjecture, and a conjecture of Pyber about irredundant coset covers. I will talk about some progress on this question, which in particular leads to a solution of the first conjecture in a strong form, makes substantial progress on the second conjecture, and fully resolves the third conjecture. This is based on a joint work with Janos Nagy and Peter Pal Pach.

**Sep 14 (W), 2022** at 2pm, S17-04-04, **Ta Duy-Hoang (ENS de Lyon)**, “Shannon capacity of hypergraphs”

**
Abstract:** There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the asymptotic growth of the size of the maximum independent sets in powers of a fixed small (directed or undirected) hypergraph, also called the Shannon capacity. An important instance of this is the corner problem studied in the context of multiparty communication complexity in the Number On the Forehead (NOF) model (and other important instances are the cap set problem in additive combinatorics and the USP capacity problem in the complexity theory of matrix multiplication).

We introduce a general method for lower bounding the Shannon capacity of hypergraphs via combinatorial degenerations, a combinatorial kind of “approximation” of subgraphs that originates from the study of matrix multiplication in algebraic complexity theory (and which plays an important role there) but which we use in a novel way. This allows us to obtain the best-known lower bounds for multiple combinatorial problems, including the corner problem and its application in communication complexity.

**Sep 9 (F), 2022** at 10am, S17-05-11, **Anirban Basak**** (International Center for Theorectial Sciences)**, “Large deviations in sparse random graphs”

**
Abstract: **The classical theory of large deviations deals with precise estimates on the probabilities of rare events (e.g. normalized sum of independent and identically distributed random variables exceed its expectation by a constant factor greater than one) involving linear functions of independent random variables. Beyond the linear setting, possibly the simplest non-trivial interesting question is the large deviations of the triangle counts in Erd\H{o}s-R\’enyi graphs. In the past fifteen years there has been a lot of work in this direction. In this talk we will discuss some of them, focusing mainly on the large deviations of (i) regular subgraph counts and (ii) the spectral radius for sparse Erd\H{o}s-R\’enyi graphs.

**Sep 7 (W), 2022** at 2pm, S17-04-04, **Hao Huang (NUS), “**A non-uniform extension of Baranyai’s Theorem”

**
Abstract: **One of the central themes in Combinatorics is to study whether or when a discrete object can be decomposed into smaller pieces of a given shape. A celebrated theorem of Baranyai states that when \(k\) divides \(n\), the family of all \(k\)-subsets of an \(n\)-element set can be partitioned into perfect matchings. In this talk, I will discuss an extension of Baranyai’s Theorem to the non-uniform setting. Our study shows that for fixed \(k\) and sufficiently large \(n\), the family consisting of all subsets of an \(n\)-element set of size at most \(k\) has such a decomposition if and only if \(n \equiv 0\) or \(-1 \pmod{k}\). Joint work with Jinye He and Jie Ma (USTC).

**Aug 31 (W), 2022** at 2pm, S17-04-04, **Lim Jeck (Caltech)**, “Sums of linear transformation”

**
Abstract: **We show that if \(L_1\) and \(L_2\) are linear transformations from \(Z^d\) to \(Z^d\) satisfying certain mild conditions, then, for any finite subset \(A\) of \(Z^d\),

$$|L_1 A+L_2 A|\geq (|\det(L_1)|^{1/d}+|\det(L_2)|^{1/d})^d |A|- o(|A|).$$

This result corrects and confirms the two-summand case of a conjecture of Bukh and is best possible up to the lower-order term for many choices of \(L_1\) and \(L_2\). As an application, we prove a lower bound for \(|A + \lambda \cdot A|\) when \(A\) is a finite set of real numbers and \(\lambda\) is an algebraic number.

**Aug 26 (F), 2022** at 9am, **Zoom, Jinyoung Park (Stanford University)**, “Thresholds”, jointly with YMLS.

**
Abstract:** Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will present recent progress on this topic. Based on joint work with Huy Tuan Pham.

**Aug 17 (W), 2022** at 2pm, S17-04-04, **Tran Chieu Minh (National University of Singapore)**, “Measure growth gap in simple Lie groups and sum-product phenomena”

**
Abstract:** Suppose G is a compact simple Lie group, μ is the normalized Haar measure on G, and A, A^2 ⊆ G are measurable. I will present a result joint with Jing Yifan where we show that μ(A^2) ≥ (2 + η)μ(A) when μ(A) < c with η and c independent of the choice of G quantitatively determined. I will also discuss the connection of this result to sumproduct phenomena, a conjecture by Breuillard and Green, the nonabelian Brunn—Minkowski conjecture, the effective Gleason—Yamabe conjecture, and the Kemperman inverse problem.

**Aug 10 (W), 2022** at 2pm, S17-04-04, **Yifan Jing (University of Oxford)**, “Sidon sets and sum-product phenomena”

**
Abstract:** Given natural numbers \(s\) and \(k\), we say that a finite set \(X\) of integers is an additive \(B_{s}[k]\) set if for any integer \(n\), the number of solutions to the equation

\[ n = x_1 + … + x_s, \] with \(x_1, …, x_s\) lying in \(X\), is at most \(k\), where we consider two such solutions to be the same if they differ only in the ordering of the summands. We define a multiplicative \(B_{s}[k]\) set analogously. These sets have been studied thoroughly from various different perspectives in combinatorial and additive number theory. In this talk, we will discuss sum-product phenomena for these sets. We show that there is either an exceptionally large additive \(B_{s}[k]\) set, or an exceptionally large multiplicative \(B_{s}[k]\) set, with \(k \ll s\). This is joint work with Akshat Mudgal.