기초과학연구원 이산수학그룹
On December 23, 2024, Zixiang Xu (徐子翔) from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on using linear algebra to prove stability results in extremal set theory. The title of his talk was “Multilinear polynomial methods and stability results on set systems“.
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“.
The IBS discrete mathematics group welcomes Dr. Nika Salia and Dr. Zixiang Xu (徐子翔), new research fellows at the IBS Extremal Combinatorics and Probability Group from September 1, 2022.
Dr. Nika Salia received his Ph.D. from the Central European University in 2021 under the supervision of Prof. Ervin Győri.
Dr. Zixiang Xu (徐子翔) received his Ph.D. from the Capital Normal University of China in 2022 under the supervision of Prof. Gennian Ge.
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.