Discrete Mathematics Group

Stefan Weltge, The relaxation complexity of the standard simplex is logarithmic
2026-06-19 16:30 - 17:30 (Asia/Seoul) | Room B332, IBS (기초과학연구원)
For a set $X$ of integer points, the relaxation complexity $operatorname{rc}(X)$ is the smallest number of facets of any polyhedron P whose integer points are precisely those of X. In this paper, we focus on the case where X is the discrete standard simplex $Delta_d = {0, e_1, …, e_d}$. We show that $operatorname{rc}(Delta_d) = O(log d)$ by an explicit, elementary construction. This improves upon the previously best-known upper bound $operatorname{rc}(Delta_d) = O(d / sqrt{log d})$ due to Aprile, Averkov, Di Summa, and Hojny (2022) and matches an asymptotic lower bound by Averkov and Schymura (2020). This is joint work with Simon Keil.

Ting-Wei Chao, The Oddtown Problem Modulo a Composite Number
2026-07-10 16:30 - 17:30
A family of sets in $[n]$ is called an $ell$-Oddtown if the sizes of all sets are not divisible by $ell$, but the sizes of pairwise intersections are divisible by $ell$. The problem was completely solved when $ell$ is a prime via an elegant linear algebraic method, showing that the family has size at most $n$. However, not much was known for composite numbers. By splitting the family into families correspond to each prime factor of $ell$, one can show that the number is at most $omega n$, where $omega$ is the number of prime factors of $ell$. We used both combinatorial and Fourier analytic arguments to prove that the number of sets in any $ell$-Oddtown is at most $omega n-(2omega+varepsilon)log_2 n$ for most $n,ell$.

Meike Hatzel, TBA
2026-08-05 16:30 - 17:30

Jinyoung Park (박진영), TBA
2026-08-18 16:30 - 17:30
