KAIST Discrete Math Seminar

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 n(n-1)/2 edges, then G has a complete subgraph on at least c^2 n /10 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.