Large cliques in hypergraphs with forbidden substructures

DOI10.1007/S00493-019-4169-YMaRDI QIDQ2226629zbMATH OpenOpenAlexFDO

Authors Andreas Holmsen

Publication date 8 February 2021

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.00245

zbMATH Keywords

chromatic numberextremal graph theoryforbidden induced subgraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Helly-type theorems and geometric transversal theory (52A35)

Abstract: 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 $K_{2,2}$ as an induced subgraph yet has at least $$ edges, then $G$ has a complete subgraph on at least $frac{c}^{2}10n$ vertices. In this paper we suggest a "higher-dimensional" analogue of the notion of an induced $K_{2,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.

Review text

A previous result from \textit{A. Gyárfás} et al. [Combinatorica 22, No. 2, 269--274 (2002; Zbl 0996.05094)] established a bound on the number of vertices in a complete subgraph that exists in a graph that does not contain a given induced subgraph with specified number of edges. The author suggests a new proof of this result that can be extended to \(k\)-uniform hypergraphs. The applications of the result related to the colorful and fractional versions of Helly's theorem are presented.

Recommendations

• Number of cliques in graphs with a forbidden subdivision
• Large cliques in graphs with high chromatic number
• The number of graphs with large forbidden subgraphs
• Large cliques in \(C_4\)-free graphs
• The maximum number of cliques in hypergraphs without large matchings
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs
• The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs
• On cliques and Lagrangians of hypergraphs
• scientific article; zbMATH DE number 15666

Cites work

• A generalization of Caratheodory's theorem
• A note on the colorful fractional Helly theorem
• A Problem of Geometry in R n
• A topological colorful Helly theorem
• A Turan type problem for interval graphs
• An upper-bound theorem for families of convex sets
• Cliques in \(C_4\)-free graphs of large minimum degree
• Helly’s theorem: New variations and applications
• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Induced Turán numbers
• Intersection patterns of convex sets
• Large cliques in \(C_4\)-free graphs
• On a problem of K. Zarankiewicz
• On the structure of linear graphs
• The colorful Helly theorem and colorful resolutions of ideals
• The history of degenerate (bipartite) extremal graph problems
• Transversal numbers for hypergraphs arising in geometry

Cited in

(18)

• The large cliques in the graph of quadratic forms
• On a bound in extremal combinatorics
• Radon numbers and the fractional Helly theorem
• Quantitative combinatorial geometry for concave functions
• Graphs with no induced \(K_{2,t}\)
• Quantitative fractional Helly and \((p,q)\)-theorems
• Radon numbers grow linearly
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• RELATIVE LERAY NUMBERS VIA SPECTRAL SEQUENCES
• Fractional Helly theorem for Cartesian products of convex sets
• Quantitative Helly-type theorems via hypergraph chains
• Discrete geometry. Abstracts from the workshop held January 21--26, 2024
• Orientation of convex sets
• An ( _0, k + 2)-theorem for k-transversals
• Beyond chromatic threshold via (p,q)-theorem, and blow-up phenomenon
• Clique covers of complete graphs and piercing multitrack intervals
• Bollobás-Erdős-Tuza conjecture for graphs with no induced \(K_{s , t}\)
• The quantitative fractional Helly theorem

This page was built for publication: Large cliques in hypergraphs with forbidden substructures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2226629)