报告题目：Near-optimal combinatorial configurations from near-perfect hypergraph matchings

报告人：上官冲，山东大学

报告时间：2024.8.30, 3:00pm

报告地点：五教5206

摘要：

An (n,r,k)-packing is an r-uniform hypergraph on n vertices such that every k-subset of the vertices is contained in at most one edge. 1985, Rödl famously showed that for all fixed r, k, and n tending to infinity, near-optimal (n,r,k)-packings always exist. Rödl’s proof has the following two essential steps: (1) define an auxiliary hypergraph, and show that there is an one-to-one correspondence between (n,r,k)-packings and matchings in this hypergraph; (2) use probabilistic method (a.k.a Rödl’s nibble) to show that the auxiliary hypergraph has a near-perfect matching. Rödl’s idea is very influential and it has found various applications in design theory, coding theory and extremal combinatorics. In this talk, I will introduce some of its recent applications.