기초과학연구원 이산수학그룹
Andreas Holmsen from KAIST gave a talk at Discrete Math Seminar on March 12, 2019 under the title “large cliques in hypergraphs with forbidden substructures.” His work extended a result of extremal graph theory due to Gyárfás, Hubenko, and Solymosi, answering a question of Erdős to hypergraphs and has interesting consequences in topological combinatorics and abstract convexity.
A result due to Gyárfás, Hubenko, and Solymosi, answering a question of Erdős, asserts that if a graph $G$ does not contain $K_{2,2}$ as an induced subgraph yet has at least $c\binom{n}{2}$ edges, then $G$ has a complete subgraph on at least $\frac{c^2}{10}n$ vertices. In this paper we suggest a “higher-dimensional” analogue of the notion of an induced $K_{2,2}$, which allows us to extend their result to $k$-uniform hypergraphs. Our result also has interesting consequences in topological combinatorics and abstract convexity, where it can be used to answer questions by Bukh, Kalai, and several others.