Date/Time : 23 Oct 2024 14:00
Venue : S17 #04-04 (SR3)
Speaker : Wei Xin, University of Science and Technology of China

Separating hash families (SHFs) are useful combinatorial structures which generalize several well-studied objects in cryptography and coding theory, including perfect hash families, frameproof codes and parent-identifying codes. The classical upper and lower bounds for the extremum size of SHFs as a function of the alphabet size do not match. In 2008, Blackburn et al. conjectured that the upper bound has the correct exponent.Before our work, the only nontrivial known cases of this conjecture was by Shangguan and Ge in 2016, when the type sum of the SHF goes no larger than 4.

In this talk, I will discuss our recent proof of all the cases of Blackburn’s conjecture when the upper bound exponent is equal to 2. We do this by transforming the problem into finding a large common solution-free set of a large collection of related linear equations. The new idea is to use an algorithm to create a link from each equation to a class of equations with some good quality in finite many steps, while the good quality can be passed backwards through the link.

Add to calendar :

Date/Time : 16 Oct 2024 14:00
Venue : S17 #04-04 (SR3)
Speaker : Zhang Xin, The University of Hong Kong

It is a discovery of Margulis in 1970s that congruence quotients of SL_2(Z) can be used to construct expanders, which are certain sparse but highly connected graphs and are ideal models for network building. The Super Approximation Conjec- ture of Salehi-Golsefidy and Varju gives a precise prediction on which more general subgroups of SL_d(Z) have this property.

In this talk, I will survey the history of this conjecture, and describe a recent progress by Tang Jincheng and myself that all Zariski dense subgroups of SL_2(Z) × SL_2(Z) or SL_2(Z) w Z_2 have this property. This progress relies on the development of a key tool in arithmetic combinatorics conjectured by Salehi-Golsefidy.

Add to calendar :

Date/Time : 09 Oct 2024 14:00
Venue : S17 #04-05 (SR2)
Speaker : Ho Boon Suan, National University of Singapore

When traversing a graph, each subsequent node is typically chosen from the set of unvisited nodes adjacent to the already visited ones. In this talk, I will explore how to count the number of possible traversals, particularly in graphs with a lot of symmetry. We will see how these counting problems lead to interesting hypergeometric identities and how computational methods can help in establishing such identities. The talk is intended for a general mathematical audience.

Add to calendar :

Date/Time : 02 Oct 2024 14:00
Venue : via Zoom
Speaker : Jing Yu, Fudan University

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

Meeting ID: 810 4646 2775
Passcode: 23571113

In 1995, Levin and Linial, London, and Rabinovich conjectured that every connected graph $G$ of polynomial growth admits an injective homomorphism to the $n$-dimensional grid graph for some $n$. Moreover, they conjected that if every ball of radius $r$ in $G$ contains at most $O(r^\rho)$ vertices, then one can take $n = O(\rho)$. Krauthgamer and Lee confirmed the first part of this conjecture and refuted the second in 2007. By constructing some finite expander graphs, they showed best possible upper bound on $n$ is $O(\rho \log \rho)$.

Prompted by these results, Papasoglu asked whether a graph $G$ of polynomial growth admits a coarse embedding into a grid graph. We give an affirmative answer to this question. Moreover, it turns out that the dimension of the grid graph only needs to be linear in the asymptotic growth rate of $G$, which confirms the original Levin–Linial–London–Rabinovich conjecture “on the large scale.”

Besides, we find an alternative proof of the result of Papasoglu that graphs of polynomial growth rate $\rho < \infty$ have asymptotic dimension at most $\rho$.

Furthermore, our proof works in the Borel setting and shows that Borel graphs of polynomial growth rate $\rho < \infty$ have Borel asymptotic dimension at most $\rho$.

(This is joint work with Anton Bernshteyn.)

Add to calendar :

Date/Time : 18 Sep 2024 12:00
Venue : via Zoom
Speaker : Peter van Hintum, Institute for Advanced Study

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

Meeting ID: 810 4646 2775
Passcode: 23571113

The Brunn-Minkowski inequality is a foundational result in convex geometry asserting that if sets A and B in R^n have the same volume and t is some number in (0,1), then |tA+(1-t)B|>|A|. We’ll prove the following folklore conjecture on the stability of the Brunn-Minkowski inequality that if in fact |tA+(1-t)B|<(1+d) |A|, then there is a common convex hull K containing A and B so that |K|<(1+ O(sqrt(d)))|A| and |co(A)|<(1+O(d))|A|. We’ll additionally describe how this result neatly fits in the additive combinatorics study of sets with small sumset. (based on joint work with Alessio Figalli and Marius Tiba)

Add to calendar :

Date/Time : 11 Sep 2024 14:00
Venue : S17 #04-05 (SR2)
Speaker : Tran Chieu-Minh, National University of Singapore

A locally compact group is nonunimodular if it has no Haar measure (i.e. every left Haar measure m is not right invariant). Considering doubling ratio m(AA)/m(A) initially looks strange on such exotic setting but turns out to be crucial even for the purpose of studying doubling on unimodular locally compact groups. In this talk I will discuss this issue further including a recently published result in this direction. ( Based on joint works with Yifan Jing and Ruixiang Zhang).

Add to calendar :

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 :