Date/Time : 26 Oct 2022 14:00
Venue : via Zoom
Speaker : Yuval Wigderson, Tel Aviv University

Join Zoom Meeting
https://nus-sg.zoom.us/j/89613913454?pwd=Q3N5VWdFUUZGRmEzRFhOU1p1QmpCdz09

Meeting ID: 896 1391 3454
Passcode: 23571113

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.

Add to calendar :

Date/Time : 19 Oct 2022 14:00
Venue : S17 #04-04 (SR3)
Speaker : Yang Tianchi, National University of Singapore

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.

Add to calendar :

Date/Time : 12 Oct 2022 10:00
Venue : via Zoom
Speaker : Mehtaab Sawhney, MIT

Join Zoom Meeting
https://nus-sg.zoom.us/j/85443285113?pwd=eVE5bFk4d01pN2FQbjFzZmtKbnVzQT09

Meeting ID: 854 4328 5113
Passcode: 23571113

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.

Add to calendar :

Date/Time : 05 Oct 2022 15:00
Venue : S17 #05-12 (SR4)
Speaker : Abdul Basit, Johns Hopkins University

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.

Add to calendar :

Date/Time : 28 Sep 2022 15:00
Venue : via Zoom
Speaker : István Tomon, Umeå University

Join Zoom Meeting
https://nus-sg.zoom.us/j/88686191741?pwd=ZHVWbmcvejludWpPRmRLUlBjZ00yQT09

Meeting ID: 886 8619 1741
Passcode: 23571113

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.

Add to calendar :

Date/Time : 14 Sep 2022 14:00
Venue : S17 #04-04 (SR3)
Speaker : Ta Duy-Hoang, ENS Lyon

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.

Add to calendar :

Date/Time : 09 Sep 2022 10:00
Venue : S17 #05-11 (SR5)
Speaker : Anirban Basak, International Centre for Theoretical Sciences

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.

Add to calendar :

Date/Time : 07 Sep 2022 14:00
Venue : S17 #04-04 (SR3)
Speaker : Hao Huang, National University of Singapore

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 ≡ 0 or -1 (mod k).

Joint work with Jinye He and Jie Ma (USTC).

Add to calendar :

Date/Time : 31 Aug 2022 14:00
Venue : S17 #04-04 (SR3)
Speaker : Lim Jeck, California Institute of Technology

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.

Add to calendar :