Large Cliques in Hypergraphs with Forbidden Substructures

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 K 2,2 as an induced subgraph yet has at least $$c\left(\begin{array}{c}n\\ 2\end{array}\right)$$ c ( n 2 ) edges, then G has a complete subgraph on at least $$\frac{c^2}{10}n$$ c 2 10 n 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 .

• Publication year

  2019

• Venue

  Comb.

• Publication date

  2019-03-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00493-019-4169-yarXiv 1903.00245
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Algebraic topology

  2020cited by this paper
• Algebraic and Geometric Methods in Discrete Mathematics

  2017cited by this paper
• Induced Turán Numbers

  2016cited by this paper
• A note on the colorful fractional Helly theorem

  2015cited by this paper
• Helly's Theorem: New Variations and Applications

  2015cited by this paper
• Cliques in $$C_4$$C4-free graphs of large minimum degree

  2015cited by this paper
• The History of Degenerate (Bipartite) Extremal Graph Problems

  2013cited by this paper
• The colorful Helly theorem and colorful resolutions of ideals

  2008cited by this paper
• A topological colorful Helly theorem

  2005cited by this paper
• Large Cliques in -Free Graphs

  2002cited by this paper
• Large Cliques in -Free Graphs

  2002cited by this paper
• Transversal numbers for hypergraphs arising in geometry

  2002cited by this paper
• Lectures on discrete geometry

  2002cited by this paper
• AN EXTREMAL PROBLEM IN GRAPH THEORY

  2001cited by this paper
• Helly, Radon, and Carathéodory Type Theorems

  1993cited by this paper
• An Upper-Bound theorem for families of convex sets

  1985cited by this paper
• Intersection patterns of convex sets

  1984cited by this paper
• A generalization of carathéodory's theorem

  1982cited by this paper
• A problem of geometry in ⁿ

  1979cited by this paper
• A Problem of Geometry in R n

  1979cited by this paper
• A Turán type problem for interval graphs

  1979cited by this paper
• On an extremal problem in graph theory

  1970cited by this paper
• A LIMIT THEOREM IN GRAPH THEORY

  1966cited by this paper
• On a problem of K. Zarankiewicz

  1954cited by this paper
• On the structure of linear graphs

  1946cited by this paper
• Über Mengen konvexer Körper mit gemeinschaftlichen Punkte.

  year unknowncited by this paper

• Helly-type problems from a topological perspective

  2026cites this paper
• Intersection patterns of set systems on manifolds with slowly growing homological shatter functions

  2026cites this paper
• Colorful Helly via induced matchings

  2025influential citation
• Large cliques in graphs with forbidden semi-induced structures

  2025influential citation
• Bollobás‐Erdős‐Tuza Conjecture for Graphs With No Induced K s , t

  2025cites this paper
• Motif Counting in Complex Networks: A Comprehensive Survey

  2025cites this paper
• Beyond chromatic threshold via the $(p,q)$-theorem, and a sharp blow-up phenomenon

  2024cites this paper
• The Quantitative Fractional Helly theorem

  2024cites this paper
• Bollob\'{a}s-Erd\H{o}s-Tuza conjecture for graphs with no induced $K_{s,t}$

  2024influential citation
• Beyond Chromatic Threshold via (p, q)-Theorem, and Blow-Up Phenomenon

  2024cites this paper
• Clique Covers of Complete Graphs and Piercing Multitrack Intervals

  2024cites this paper
• Helly type problems in convexity spaces

  2024influential citation
• Clique density vs blowups

  2024cites this paper
• A fractional Helly theorem for set systems with slowly growing homological shatter function

  2024influential citation
• A note on infinite versions of $(p,q)$-theorems

  2024cites this paper
• An (ℵ0, k + 2)-theorem for k-transversals

  2023cites this paper
• Quantitative Helly-type Theorems via Hypergraph Chains

  2023influential citation
• Colorful Helly Theorem for Piercing Boxes with Two Points

  2022cites this paper
• Orientation of Convex Sets

  2022cites this paper
• Stronger bounds for weak epsilon-nets in higher dimensions

  2021cites this paper
• Fractional Helly Theorem for Cartesian Products of Convex Sets

  2021cites this paper
• Quantitative Fractional Helly and $(p,q)$-Theorems

  2020influential citation
• Helly and Tverberg Type Theorems; Mass Partitions and Rado’s Central Type Theorems in Geometry, Combinatorics and Topology IV

  2020cites this paper
• RELATIVE LERAY NUMBERS VIA SPECTRAL SEQUENCES

  2020cites this paper
• Radon numbers and the fractional Helly theorem

  2019cites this paper
• Graphs with no Induced $K_{2, t}$

  2019cites this paper
• Radon Numbers Grow Linearly

  2019cites this paper
• Quantitative combinatorial geometry for concave functions

  2019cites this paper