2019/03/01 by Holmsen, Andreas F. · 1 citation
#05C35 #05C65 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1903.00245
A result due to Gyárfás, Hubenko, and Solymosi (answering a question of Erdös) states that if a graph G on n vertices does not contain K2,2 as an induced subgraph yet has at least c\binomn2 edges, then G has a complete subgraph on at least (c2)/(10)n vertices. In this paper we suggest a "higher-dimensional" analogue of the notion of an induced K2,2 which allows us to generalize their result to k-uniform hypergraphs. Our result also has an interesting consequence in discrete geometry. In particular, it implies that the fractional Helly theorem can be derived as a purely combinatorial consequence of the colorful Helly theorem.