IBS/KAIST Joint Discrete Math Seminar

Large cliques in hypergraphs with forbidden substructures

Andreas Holmsen

Department of Mathematical Sciences, KAIST

Department of Mathematical Sciences, KAIST

2019/03/12 Tue 4:30PM-5:30PM (Room B232, IBS)

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.