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:

We present a general approach for determining the maximum number of edges in an \(n\)-vertex \(r\)-uniform hypergraph that does not contain \(t+1\) vertex-disjoint copies of \(F\), when \(n\) is large, \(t = o(n)\), and \(F\) is nondegenerate. This extends old results of Simonovits and Moon on complete graphs.
Based on joint work with Jianfeng Hou, Heng Li, Long-Tu Yuan, and Yixiao Zhang.

 

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

 

Abstract:

A graph is Ramsey if its largest clique or independent set is of size logarithmic in the number of vertices. While almost all graphs are Ramsey, there is still no known explicit construction of Ramsey graphs. We discuss recent progress on finding these “dark matter” of graphs. Along the way, we study some fundamental problems in additive combinatorics, and discover that group structure is superfluous for these problems. Joint work with David Conlon, Jacob Fox, and Liana Yepremyan.

 

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

 

Abstract:

Suppose we are given matchings \(M_1, \cdots ,M_N\) of size \(t\) in some \(r\)-uniform hypergraph, and let us think of each matching having a different color. How large does \(N\) need to be (in terms of \(t\) and \(r\)) such that we can always find a rainbow matching of size \(t\)? This problem was first introduced by Aharoni and Berger, and has since been studied by several different authors. While interesting for its own sake in the context of finding transversals in Latin Squares (e.g. the Ryser–Brualdi–Stein Conjecture), it is perhaps not too surprising that this question is also connected with different sides of additive combinatorics. In this talk, we will survey some of these connections, discuss some recent results that more or less completely answer the original question when one of the parameters t or r is fixed, and then end with some (fairly arbitrary) speculations/open problems. Joint work with Lisa Sauermann and Dmitrii Zakharov.

 

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:

A fundamental theorem of Rademacher from 1941 led to the study of supersaturation problems of graphs, which aim to count the minimum number of copies of a given graph \(F\) among all graphs with \(n\) vertices and \(m\) edges. This is closely related to a central concept in Extremal Graph Theory — the Turán number of \(F\), which denotes the maximum number of edges in an \(n\)-vertex graph which does not contain \(F\) as a subgraph. Famous results of Erdős, and Lovász and Simonovits determine the minimum number of cliques \(K_r\) in graphs whose number of edges exceed the Turán number of \(K_r\). Subsequent works of Mubayi as well as Pikhurko and Yilma extend these classical results from cliques to color-critical graphs, a rich family playing important roles in extremal problems. In this talk, we will discuss supersaturation problems beyond color-critical graphs and investigate natural enumerative parameters.

 

Our results go beyond the previous results and show that supersaturation problems for general graphs can be rather complicated. Among others, we disprove a conjecture of Mubayi. Joint work with Long-Tu Yuan.

 

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

 

Abstract:

The Kakeya conjecture suggests a fundamental phenomenon in Euclidean space: (thin) tubes with different directions are essentially disjoint. The problem also arises naturally in other contexts, (e.g. Fourier analysis, geometric measure theory), and it often serves as a main enemy—tool. In this talk, I will briefly survey the conjecture and some techniques people developed to attack it. Along the way, I will also discuss some recent progress and applications.

 

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

 

Abstract:

Let d be a fixed positive integer and let \(A\) be a finite set of n elements in \(\mathbb{R}^d\). A classical result of Freiman then suggests that if \(A\) is not contained in a translate of some hyperplane, then \(|A+A| \ge (d+1)n – d(d+1)/2,\) where \(A+A = \{a + b : a, b \in A\}\). This is known to be sharp by setting \(A\) to be a union of arithmetic progressions. Naturally, one may ask whether a corresponding result holds for the difference set \(A-A = \{a – b : a, b \in A\}\). This forms a conjecture of Uhrin from 1980, which was subsequently raised again by Ruzsa in 1994. While the \(d=1,2\) and \(d=3\) cases of this problem were solved by Freiman-Heppes-Uhrin (1989) and Stanchsecu (1998) respectively, the \(d> 3\) case was open till quite recently. In this talk, we will survey some of the recent results in this direction, including our own work which shows that whenever \(d>3\) and \(A\) is not lying in some affine hyperplane, we have \(|A-A| \ge (2d-2 + \frac{1}{d-1})n – O(n^{1-c}),\) for some constant \(c = c(d) >0\). The main term here is sharp, thus resolving the conjecture of Uhrin and Ruzsa up to a polynomially small error term.

 

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.