CaltechAUTHORS
  A Caltech Library Service

Erdős-Hajnal-type theorems in hypergraphs

Conlon, David and Fox, Jacob and Sudakov, Benny (2012) Erdős-Hajnal-type theorems in hypergraphs. Journal of Combinatorial Theory, Series B, 102 (5). pp. 1142-1154. ISSN 0095-8956. doi:10.1016/j.jctb.2012.05.005. https://resolver.caltech.edu/CaltechAUTHORS:20190812-162957444

[img] PDF - Submitted Version
See Usage Policy.

206kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190812-162957444

Abstract

The Erdős–Hajnal conjecture states that if a graph on n vertices is H-free, that is, it does not contain an induced copy of a given graph H, then it must contain either a clique or an independent set of size n^δ(H), where δ(H) > 0 depends only on the graph H. Except for a few special cases, this conjecture remains wide open. However, it is known that an H-free graph must contain a complete or empty bipartite graph with parts of polynomial size. We prove an analogue of this result for 3-uniform hypergraphs, showing that if a 3-uniform hypergraph on n vertices is ℋ-free, for any given ℋ, then it must contain a complete or empty tripartite subgraph with parts of order c(log n)^½ + δ(ℋ), where δ(ℋ) > 0 depends only on ℋ. This improves on the bound of c(log n)^½, which holds in all 3-uniform hypergraphs, and, up to the value of the constant δ(ℋ), is best possible. We also prove that, for k ≥ 4, no analogue of the standard Erdős–Hajnal conjecture can hold in k-uniform hypergraphs. That is, there are k-uniform hypergraphs ℋ and sequences of ℋ-free hypergraphs which do not contain cliques or independent sets of size appreciably larger than one would normally expect.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1016/j.jctb.2012.05.005DOIArticle
https://www.sciencedirect.com/science/article/pii/S0095895612000469PublisherArticle
https://arxiv.org/abs/1104.5544arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Alternate Title:Erdos-Hajnal-type theorems in hypergraphs
Additional Information:© 2012 Elsevier. Under an Elsevier user license. Received 28 April 2011; available online 18 June 2012. Conlon research supported by a Royal Society University Research Fellowship. Fox research supported by a Simons Fellowship and NSF grant DMS-1069197. Sudakov research supported in part by NSF grant DMS-1101185 and by a USA–Israeli BSF grant. Credit and thanks are due to Vojta Rödl and Mathias Schacht, who brought the question regarding tripartite subgraphs of ℋ-free hypergraphs to our attention.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
Simons FoundationUNSPECIFIED
NSFDMS-1069197
NSFDMS-1101185
Binational Science Foundation (USA-Israel)UNSPECIFIED
Subject Keywords:Ramsey theory; Erdős–Hajnal conjecture; Hypergraphs
Issue or Number:5
DOI:10.1016/j.jctb.2012.05.005
Record Number:CaltechAUTHORS:20190812-162957444
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190812-162957444
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97810
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:13 Aug 2019 17:49
Last Modified:16 Nov 2021 17:34

Repository Staff Only: item control page