Large cliques or cocliques in hypergraphs with forbidden order-size pairs
OPEN ACCESS
Loading...
Author / Producer
Date
2024-05
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
The well-known Erdős-Hajnal conjecture states that for any graph F, there exists ϵ > 0 such that every n-vertex graph G that contains no induced copy of F has a homogeneous set of size at least nϵ. We consider a variant of the Erdős-Hajnal problem for hypergraphs where we forbid a family of hypergraphs described by their orders and sizes. For graphs, we observe that if we forbid induced subgraphs on m vertices and f edges for any positive m and 0 ≤ f ≤ (m2), then we obtain large homogeneous sets. For triple systems, in the first nontrivial case m=4, for every S ⊆ {0,1,2,3,4}, we give bounds on the minimum size of a homogeneous set in a triple system where the number of edges spanned by every four vertices is not in S. In most cases the bounds are essentially tight. We also determine, for all S, whether the growth rate is polynomial or polylogarithmic. Some open problems remain.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
33 (3)
Pages / Article No.
286 - 299
Publisher
Cambridge University Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Erdős-Hajnal conjecture; Homogeneous sets in hypergraphs
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin