기초과학연구원 이산수학그룹
On November 18, 2025, Fedor Noskov from MIPT, Russia gave a talk at the Discrete Math Seminar on hypergraph Turán-type problems and their connection to extremal set theory problems. The title of his talk was “Polynomial dependencies in hypergraph Turan-type problems“.
Consider a general Turan-type problem on hypergraphs. Let $\mathcal{F}$ be a family of $k$-subsets of $[n]$ that does not contain sets $F_1, \ldots, F_s$ satisfying some property $P$. We show that if $P$ is low-dimensional in some sense (e.g., is defined by intersections of bounded size) then, under polynomial dependencies between $n, k$ and the parameters of $P$, one can reduce the problem of maximizing the size of the family $|\mathcal{F}|$ to a finite extremal set theory problem independent of $n$ and $k$. We show that our technique implies new bounds in a number of Turan-type problems including the Erdős-Sós forbidden intersection problem, the Duke-Erdős forbidden sunflower problem, forbidden $(t, d)$-simplex problem and the forbidden hypergraph problem. Furthermore, we also briefly discuss the connection between the aforementioned reduction and the measure boosting argument based on the action of a certain semigroup on the Boolean cube. This connection turns out to be fruitful when extending extremal set theory problems to domains different from $\binom{[n]}{k}$.
Joint work with Liza Iarovikova, Andrey Kupavskii, Georgy Sokolov and Nikolai Terekhov