CaltechAUTHORS
  A Caltech Library Service

Large almost monochromatic subsets in hypergraphs

Conlon, David and Fox, Jacob and Sudakov, Benny (2011) Large almost monochromatic subsets in hypergraphs. Israel Journal of Mathematics, 181 (1). pp. 423-432. ISSN 0021-2172. https://resolver.caltech.edu/CaltechAUTHORS:20190812-162958677

[img] PDF - Submitted Version
See Usage Policy.

126Kb

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

Abstract

We show that for all ℓ and ε > 0 there is a constant c = c(ℓ, ε) > 0 such that every ℓ-coloring of the triples of an N-element set contains a subset S of size c√(log N) such that at least 1 − ε fraction of the triples of S have the same color. This result is tight up to the constant c and answers an open question of Erdős and Hajnal from 1989 on discrepancy in hypergraphs. For ℓ ≥ 4 colors, it is known that there is an ℓ-coloring of the triples of an N-element set whose largest monochromatic subset has cardinality only Θ(log log N). Thus, our result demonstrates that the maximum almost monochromatic subset that an ℓ-coloring of the triples must contain is much larger than the corresponding monochromatic subset. This is in striking contrast with graphs, where these two quantities have the same order of magnitude. To prove our result, we obtain a new upper bound on the ℓ-color Ramsey numbers of complete multipartite 3-uniform hypergraphs, which answers another open question of Erdős and Hajnal.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/s11856-011-0016-6DOIArticle
https://rdcu.be/bOK8ZPublisherFree ReadCube access
https://arxiv.org/abs/0901.3912arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information:© Hebrew University Magnes Press 2011. Received 22 January 2009; first online 25 February 2011. Conlon research supported by a research fellowship at St John’s College. Fox research supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship. Sudakov research supported in part by NSF CAREER award DMS-0812005 and by USA-Israeli BSF grant.
Funders:
Funding AgencyGrant Number
St. John's College, CambridgeUNSPECIFIED
NSFUNSPECIFIED
Princeton UniversityUNSPECIFIED
NSFDMS-0812005
Binational Science Foundation (USA-Israel)UNSPECIFIED
Subject Keywords:Bipartite Graph; Complete Graph; Complete Bipartite Graph; Pigeonhole Principle; Ramsey Number
Issue or Number:1
Record Number:CaltechAUTHORS:20190812-162958677
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190812-162958677
Official Citation:Conlon, D., Fox, J. & Sudakov, B. Isr. J. Math. (2011) 181: 423. https://doi.org/10.1007/s11856-011-0016-6
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:97820
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:13 Aug 2019 22:21
Last Modified:03 Oct 2019 21:35

Repository Staff Only: item control page