Large Cliques in Hypergraphs with Forbidden Substructures
- PDF / 368,635 Bytes
- 11 Pages / 442.205 x 665.008 pts Page_size
- 60 Downloads / 173 Views
Bolyai Society – Springer-Verlag
Combinatorica 11pp. DOI: 10.1007/s00493-019-4169-y
LARGE CLIQUES IN HYPERGRAPHS WITH FORBIDDEN SUBSTRUCTURES ANDREAS F. HOLMSEN Received March 12, 2019 Revised August 10, 2019 A result due to Gy´ arf´ as, Hubenko, and Solymosi (answering a question of Erd˝ os) states that if a graph G on n vertices does not contain K2,2 as an induced subgraph yet has at c2 n vertices. In this paper least c n2 edges, then G has a complete subgraph on at least 10 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.
1. Introduction Among the classical problems in extremal graph theory are the Tur´ an type extremal problems. They ask for the maximum number of edges ex(n, H) in a graph on n vertices provided it does not contain some fixed graph H as a subgraph. In the case when H = Km , the complete graph on m vertices, the answer is given by Tur´an’s theorem [22], which also characterizes the extremal graphs which obtain the maximum ex(n, Km ) for all n and m. More generally, if the chromatic number χ(H) ≥ 3, we have ex(n, H) = 1 1 − χ(H)−1 n2 + o(n2 ). This is the fundamental Erd˝os–Stone–Simonovits theorem [7,8]. While their result also holds for bipartite H, it only tells us that ex(n, H) = o(n2 ), which is less satisfactory since stronger estimates Mathematics Subject Classification (2010): 05C35, 05C65, 52A35 Supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF2016R1D1A1B03930998).
2
ANDREAS F. HOLMSEN
exist. For instance, the K˝ov´ari–S´os–Tur´ an theorem [19] states that for the 1 complete bipartite graph Ks,t we have ex(n, Ks,t ) < cs,t n2− s . There are many long-standing unsolved questions in this area and we refer the reader to the extensive survey [10] for more information and further references. Recently, Loh, Tait, Timmons, and Zhou [20] introduced a new and natural line of investigations related to the Tur´an type problems. For a pair of graphs H and F , they proposed the problem of determining the maximum number of edges in a graph on n vertices, subject to the condition that we simultaneously forbid H as a subgraph and F as an induced subgraph. One of their main results [20, Theorem 1.1] addresses the case when H = Kr and F = Ks,t , where they obtain the same asymptotic upper bound as in the K˝ ov´ ari–S´os–Tur´an theorem (with a different constant, now depending on r, s, and t). The case s = t = 2 is interesting in its own right, and is closely related to the following result due to Gy´ arf´as, Hubenko, and Solymosi [11]. Theorem (Gy´ arf´ as–Hubenko–Solymosi). Let G be a graph on n ver tices and at least c n2 edges. If G does not contain K2,2 as an induced c2 n. subgraph, then ω(
Data Loading...
