Date/Time : 04 Sep 2024 14:00
Venue : S17 #04-05 (SR2)
Speaker : Peng Fei, National University of Singapore

A quasi-kernel of a digraph is an independent set Q such that every vertex can reach Q in at most two steps. The 48-year-old small QK conjecture says that every sink-free digraph contains a quasi-kernel of size at most n/2. Spiro posed the large QK conjecture, which states that every digraph contains a quasi-kernel Q such that |N^-[Q]| ≥ n/2, and showed that it follows from the small QK conjecture. We show that the converse is true with a weaker constant. We also show that every sink-free digraph contains a quasi-kernel of size at most (1−1/k)n, where k is the digraph’s kernel-perfect number, generalizing a result by Kostochka, Luo and Shan. Joint work with Ai and Liu.

Add to calendar :

Date/Time : 28 Aug 2024 14:00
Venue : S17 #05-12 (SR4)
Speaker : Lim Jeck, California Institute of Technology

We show that if l_1, … , l_k are algebraic numbers, then, for any finite subset A of ℂ,

|A + l_1·A + … + l_k·A| >= H(l_1,…,l_k)|A|-o(|A|),

where H(l_1,…,l_k) is an explicit constant that is best possible. The case k=1 already confirms a conjecture of Krachun and Petrov. Joint work with David Conlon.

Add to calendar :

Date/Time : 21 Aug 2024 14:00
Venue : S17 #05-12 (SR4)
Speaker : Yang Tianchi, National University of Singapore

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 4-cycles and 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.

Add to calendar :

Date/Time : 14 Aug 2024 14:00
Venue : S17 #04-04 (SR3)
Speaker : Jie Han, Beijing Institute of Technology

Random graphs are important objects in discrete probability theory. There has been a growing interest in extending graph theory theorems into the random graph setting. We will survey this line of problems and mention some recent developments.

Add to calendar :

Date/Time : 08 May 2024 14:00
Venue : S17 #04-05 (SR2)
Speaker : Xiaofan Yuan, Arizona State University

Resolving a recent problem of Bell, Frieze, and Marbach, we establish the threshold result of Frankston–Kahn–Narayanan–Park in the rainbow setting. This is joint work with Jie Han.

Add to calendar :

Date/Time : 12 Apr 2024 16:00
Venue : S17 #04-04 (SR3)
Speaker : Yan Wang, Shanghai Jiao Tong University

A maximum matching in a graph can be found in polynomial time. However, Karp shows that it is NP-hard to find even for 3-uniform hypergraphs. Much effort has been devoted to finding good sufficient conditions for the existence of a large matching in uniform hypergraphs, including Dirac type conditions. In this talk, I will talk about some recent progress on hypergraph matching problems.

Add to calendar :

Date/Time : 15 Nov 2023 10:00
Venue : via Zoom
Speaker : Alex Cohen, Massachusetts Institute of Technology

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

Meeting ID: 810 4646 2775
Passcode: 23571113

Heilbronn’s triangle problem asks, how small is the smallest triangle formed by a set of points? Suppose n points are placed in the unit square and Delta is the smallest area triangle formed by three of these points. It is not too hard to see that Delta < C n^{-1}. Komlos, Pintz, and Szemeredi proved in 1981 that Delta << C n^{-8/7} by building on an ingenious method of Roth. We improve the bound to Delta < C n^{-8/7-1/2000}. The improvement comes from establishing new connections between Heilbronn’s problem and projection theory.

All joint with Dmitrii Zakharov and Cosmin Pohoata.

Add to calendar :

Date/Time : 25 Oct 2023 14:00
Venue : via Zoom
Speaker : Simon Machado, ETH Zurich

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

Meeting ID: 810 4646 2775
Passcode: 23571113

Abstract: The doubling constant of a subset $A$ of a group is defined as the ratio of the size of $A^2$ (the set of products of two elements of $A$) by the size of $A$. It is now well-established that the doubling constant $K$ of $A$ captures a great deal of information about the additive structure of $A$. For instance, if $K < 3/2$, then $A$ itself must be a coset of a group. The generalised Breuillard—Green conjecture asserts that, conversely, if one knows that $A$ is a subset of a compact simple Lie group, then $K$ must be bounded below by an explicit dimensional constant, and provides examples saturating this inequality.

I will discuss a proof of that conjecture assuming that $A$ is sufficiently small to begin with. This will take us through the theory of additive combinatorics and, perhaps surprisingly, some optimal transport. If time permits I will also discuss what we know about subsets whose doubling constant is near the minimal value.

Add to calendar :

Date/Time : 18 Oct 2023 13:00
Venue : S17 #05-11 (SR5)
Speaker : Chandrima Kayal, Indian Statistical Insitute, Kolkata

Suppose we want to cover all the vertices of the n-dimensional Boolean cube using a minimum number of hyperplanes. Observe that this can be done using only two hyperplanes. Moreover, no single hyperplane can cover all the vertices. Now what if we want to cover only a subset of the Boolean cube? For example, suppose we want to cover all the vertices except one, viz. the origin. One can observe that n hyperplanes are sufficient. But can we do better? The celebrated covering result by Alon and Füredi shows that at least n hyperplanes will be required to cover all the vertices of the n-dimensional cube leaving out exactly one vertex.

We shall discuss different versions of this covering problem, and give a generalization of Alon and Füredi’s covering result for any symmetric subset of the Boolean cube. Also, we shall show a strict separation between the size of a polynomial cover and a hyperplane cover.

This work was jointly done with Arijit Ghosh, Soumi Nandi and S. Venkitesh.

Add to calendar :