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 :

Date/Time : 17 Aug 2022 14:00
Venue : S17 #04-04 (SR3)
Speaker : Tran Chieu Minh, National University of Singapore

Abstract: (Joint with Jing Yifan) Suppose G is a compact simple Lie group, μ is the normalized Haar measure on G, and A, A^2 ⊆ G are measurable. I will discuss a measure growth gap result where we show that μ(A^2) ≥ (2 + η)μ(A) when μ(A) < c with η and c independent of the choice of G quantitatively determined. This is in contrast with the situation in compact connected solvable Lie group, where the Kemperman’s lower bound μ(A^2) ≥ min{2μ(A), 1} cannot be improved.

I will also survey the connections of this result to sumproduct phenomena, a conjecture by Breuillard and Green, the nonabelian Brunn—Minkowski conjecture, the effective Gleason—Yamabe conjecture, and the Kemperman inverse problem.

Add to calendar :

Date/Time : 10 Aug 2022 14:00
Venue : S17 #04-04 (Seminar Room 3)
Speaker : Yifan Jing, University of Oxford

Abstract:  Given natural numbers $s$ and $k$, we say that a finite set $X$ of integers is an additive $B_{s}[k]$ set if for any integer $n$, the number of solutions to the equation \[ n = x_1 + … + x_s, \] with $x_1, …, x_s$ lying in $X$, is at most $k$, where we consider two such solutions to be the same if they differ only in the ordering of the summands. We define a multiplicative $B_{s}[k]$ set analogously. These sets have been studied thoroughly from various different perspectives in combinatorial and additive number theory. In this talk, we will discuss sum-product phenomena for these sets. We show that there is either an exceptionally large additive $B_{s}[k]$ set, or an exceptionally large multiplicative $B_{s}[k]$ set, with $k \ll s$. This is joint work with Akshat Mudgal.

Add to calendar :