Date/Time : 15 Feb 2023 16:00
Venue : via Zoom
Speaker : Akshat Mudgal, University of Oxford

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

Meeting ID: 810 4646 2775
Passcode: 23571113

Let d be a fixed positive integer and let A be a finite set of n elements in R^d. A classical result of Freiman then suggests that if A is not contained in a translate of some hyperplane, then

|A+A| >= (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| >= (2d – 2 + 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.

Add to calendar :

Date/Time : 09 Nov 2022 14:00
Venue : S17 #04-04 (SR3)
Speaker : Debsoumya Chakraborti, Institute for Basic Science

Abstract:  There have been extensive studies on the following question: given k graphs G_1,… , 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.

Add to calendar :

Date/Time : 02 Nov 2022 14:00
Venue : via Zoom
Speaker : Zilin Jiang, Arizona State University

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

Meeting ID: 816 3960 4748
Passcode: 23571113

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.

Add to calendar :

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 :