Date/Time : 17 Apr 2025 13:00
Venue : S16 #03-06
Speaker : Abdul Basit, Monash University

The independent set sequence of a graph is the sequence whose k^th term is the number of independent sets of size k in the graph. Alavi, Malde, Schwenk and Erdős studied this sequence in 1987, and showed that it can exhibit any pattern of rises and falls. They raised the question, however, of whether the independent set sequence of a tree, or more generally a forest, is always unimodal — that is, has a single peak. This intriguing question is still very much open. I’ll survey some recent results about this question. (Some of this is joint work with David Galvin and Misha Isarev.)

Add to calendar :

Date/Time : 17 Apr 2025 14:00
Venue : S16 #03-06
Speaker : Cheng Yui To, National University of Singapore

Freiman’s theorem is a cornerstone of additive combinatorics, providing a structural description of finite sets of integers with small doubling. In this talk, I will present an extension of Freiman’s theorem to infinite subsets of the integers by replacing cardinality with density. Our main tool is the abelian Lie model theorem, which harnesses the powerful machinery of ultraproducts to pass from density—a less well-behaved notion—to Haar measures, where the classical proof strategy of Freiman’s theorem can be adapted. (Joint work with Peng Fei and Tran Chieu-Minh, part of undergrad honor project requirement).

Add to calendar :

Date/Time : 17 Apr 2025 15:00
Venue : S16 #03-06
Speaker : Kong Zuxiang, National University of Singapore

Convex sets in Euclidean space enjoy the elegant property that convexity is preserved under quotient projections. From the perspective of additive combinatorics, small doubling—a condition where a set grows slowly under addition—is a natural generalization of convexity, as illustrated by equality condition in the famous Brunn–Minkowski inequality. In this talk, I will discuss recent progress on how small doubling behaves under quotients in the setting of nonabelian locally compact groups. As part of my joint paper with Fei and Tran as well as my honors thesis, we improve on a work by An, Jing, Zhang, and Tran, by proving new bounds relating the doubling constant of a set to that of its image under a quotient map. In particular, we establish a sharp quadratic bound when the set is symmetric, a cubic bound in general, and a structural result showing that a large subset with linear doubling survives the quotient. These results offer a refined understanding of how additive structure interacts with quotient projections, and bridges geometry, analysis, and combinatorics in nonabelian settings. (Joint work with Peng Fei and Tran Chieu-Minh, part of undergrad honor project requirement).

Add to calendar :

Date/Time : 24 Mar 2025 14:00
Venue : S17 #05-11 (SR5)
Speaker : Wei-Hsuan Yu, National Central University

We address the maximum size of binary codes and binary constant weight codes with few distances. Previous works established a number of bounds for these quantities as well as the exact values for a range of small code lengths. As our main results, we determine the exact size of maximal binary codes with two distances for all lengths n≥6 as well as the exact size of maximal binary constant weight codes with 2,3, and 4 distances for several values of the weight and for all but small lengths.

Add to calendar :

Date/Time : 24 Mar 2025 15:00
Venue : S17 #05-11 (SR5)
Speaker : Chia-En Chiang, National Taiwan Normal University

An almost k-cover of the hypercube Q^n = {0,1}^n is a collection of hyperplanes that avoids the origin and covers every other vertex at least k times. When k is large with respect to the dimension n, Clifton and Huang asymptotically determined the minimum possible size of an almost k-cover. Central to their proof was an extension of the LYM inequality, concerning a weighted count of hyperplanes.

In this paper we completely characterise the hyperplanes of maximum weight, showing that there are $\binom{2n-1}{n}$ such hyperplanes. We further provide stability, bounding the weight of all hyperplanes that are not of maximum weight. These results allow us to effectively shrink the search space when using integer linear programming to construct small covers, and as a result we are able to determine the exact minimum size of an almost k-cover of Q^6 for most values of k. We further use the stability result to improve the Clifton–Huang lower bound for infinitely many choices of k in every sufficiently large dimension n.

Add to calendar :

Date/Time : 18 Dec 2024 14:00
Venue : S17 #04-04 (SR3)
Speaker : Wenjie Fang, Université Gustave Eiffel

We consider the number of occurrences of subwords (non-consecutive sub-sequences) in a given word. We first introduce the notion of subword entropy that measures the maximal number of occurrences among all possible subwords. We then give upper and lower bounds of minimal subword entropy for words of fixed length in a fixed alphabet, and show that minimal subword entropy per letter has a limit value. A better upper bound of minimal subword entropy for a binary alphabet is then given by looking at certain families of periodic words. We also give some conjectures based on experimental observations.

Add to calendar :

Date/Time : 05 Dec 2024 14:00
Venue : S17 #04-04 (SR3)
Speaker : Hong Liu, Institute for Basic Science, South Korea

A well-known theorem of Nikiforov asserts that any graph with a positive $K_r$-density contains a logarithmic blowup of $K_r$. We explore variants of Nikiforov’s result and investigate when positive clique density condition implies the existence of a significantly larger blowup of a clique. Our results study such problems for families of ordered graphs with forbidden induced monotone path, obtaining optimal bounds. As corollaries, we strengthen a result of Pach and Tomon, and resolve a conjecture of Tomon in a strong form. To find a large blowup, we reduce the embedding problem to a certain Ramsey problem. For optimal lower bound constructions, we make use of concentration of measure and the isodiametric inequality on high dimensional spheres.

Add to calendar :

Date/Time : 13 Nov 2024 14:00
Venue : S17 #04-05 (SR2)
Speaker : Tuan Tran, University of Science and Technology of China

Consider a multipartite graph G with maximum degree at most n-o(n), parts V1,…,Vk of size n each, and every vertex has at most o(n) neighbors in any part Vi. Loh and Sudakov proved that any such G has an independent transversal. They further conjectured that the vertex set of G can be decomposed into pairwise disjoint independent transversals. We resolve this conjecture approximately by showing that G contains n-o(n) pairwise disjoint independent transversals. As applications, we give approximate answers to questions of Yuster, and of Fischer, Kühn, and Osthus.

Joint work with Debsoumya Chakraborti.

Add to calendar :

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 :