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 :

Date/Time : 04 Oct 2023 13:00
Venue : via Zoom
Speaker : Shengtong Zhang, Stanford University

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

Meeting ID: 810 4646 2775
Passcode: 23571113

In this talk, we start with Nikiforov’s spectral version of Turan’s theorem. This leads us to an intriguing conjecture of Bollobas and Nikiforov on the first two eigenvalues of graphs. Despite its simple appearance, the conjecture has resisted attacks for over 15 years. We survey several partial results on this conjecture, up to some recent progress by the speaker confirming the conjecture in the case of regular graphs. Based on https://arxiv.org/abs/2309.08184.

Add to calendar :

Date/Time : 20 Sep 2023 15:00
Venue : S16 #04-35
Speaker : Goh Jun Le, National University of Singapore

We apply and reframe statements about graph decompositions, Latin squares, affine planes, etc. to statements about reductions between problems. In particular, we exhibit a statement (depending on n) which is equivalent to the existence of a finite affine plane of order n (open for many n). I expect this talk to be accessible to undergraduates.

Joint work with David Belanger and Damir Dzhafarov.

Add to calendar :

Date/Time : 13 Sep 2023 14:00
Venue : S17 #05-11 (SR5)
Speaker : Jan Dobrowolski, University of Manchester

We study the relation R of collinearity of triples of points on a smooth cubic surface X. Our aim is to understand sequences of triples (A,B,C) of finite sets with |A|=|B|=|C| whose Cartesian products have asymptotically maximal possible size of intersection with the relation R (i.e. growing roughly as quickly as the square of the size of the sets A,B,C). This is an instance of the so-called Elekes-Szabó problem, which is closely related to the sum-product phenomenon. It is well-known that such configurations can be built on planar cubic curves, hence we can find them in an intersection of X with a plane. We prove this is essentially the only way in which such configurations on X arise, i.e. every such configuration on X concentrates on its intersection with a plane.

This is a joint work with Martin Bays and Tingxiang Zou.

Add to calendar :