In 1966, Kleitman established that if \( |A \triangle B| \leq d \) for any \( A, B \in \mathcal{F} \), then \( |\mathcal{F}| \leq \sum_{i=0}^{k} \binom{n}{i} \) for \( d = 2k \), and \( |\mathcal{F}| \leq 2 \sum_{i=0}^{k} \binom{n-1}{i} \) for \( d = 2k+1 \). These upper bounds are attained by the radius-\(k\) Hamming ball \( \mathcal{K}(n, k) := \{ F : F \subseteq [n], |F| \leq k \} \) in the even case, and by the family \( \mathcal{K}_y(n, k) := \{ F : F \subseteq [n], |F \setminus \{y\}| \leq k \} \) in the odd case. In 2017, Frankl provided a combinatorial proof of a stability result for Kleitman’s theorem, offering improved upper bounds for \( |\mathcal{F}| \) when \( \mathcal{F} \) is not the extremal structure.
In this talk, I will begin by demonstrating the application of multilinear polynomial methods in extremal set theory, highlighting some interesting techniques. I will then present an algebraic proof of the stability result for Kleitman’s theorem. Finally, I will discuss further applications and explore how to employ linear algebra methods more effectively and flexibly.
This talk is based on joint work with Jun Gao and Hong Liu.
On October 4, 2022, Zixiang Xu (徐子翔) from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on the Turán numbers of bipartite graphs and recent approaches. The title of his talk was “On the degenerate Turán problems“.
For a graph $F$, the Turán number is the maximum number of edges in an $n$-vertex simple graph not containing $F$. The celebrated Erdős-Stone-Simonovits Theorem gives that \[ \text{ex}(n,F)=\bigg(1-\frac{1}{\chi(F)-1}+o(1)\bigg)\binom{n}{2},\] where $\chi(F)$ is the chromatic number of $H$. This theorem asymptotically solves the problem when $\chi(F)\geqslant 3$. In case of bipartite graphs $F$, not even the order of magnitude is known in general. In this talk, I will introduce some recent progress on Turán numbers of bipartite graphs and related generalizations and discuss several methods developed in recent years. Finally, I will introduce some interesting open problems on this topic.
