Hypergraphs with Zero Chromatic Threshold

József Balogh, John Lenz

Research output: Contribution to journalArticlepeer-review

Abstract

Let F be an r-uniform hypergraph. The chromatic threshold of the family of F-free, r-uniform hypergraphs is the infimum of all non-negative reals c such that the subfamily of F-free, r-uniform hypergraphs H with minimum degree at least c(|V(H)|r-1) has bounded chromatic number. The study of chromatic thresholds of various graphs has a long history, beginning with the early work of Erdős and Simonovits. One interesting problem, first proposed by Łuczak and Thomassé and then solved by Allen, Böttcher, Griffiths, Kohayakawa and Morris, is the characterization of graphs having zero chromatic threshold, in particular the fact that there are graphs with non-zero Turán density that have zero chromatic threshold. Here, we make progress on this problem for r-uniform hypergraphs, showing that a large class of hypergraphs have zero chromatic threshold in addition to exhibiting a family of constructions showing another large class of hypergraphs have non-zero chromatic threshold. Our construction is based on a particular product of the Bollobás–Erdős graphs defined earlier by the authors.

Original languageEnglish (US)
Pages (from-to)1249-1262
Number of pages14
JournalGraphs and Combinatorics
Volume32
Issue number4
DOIs
StatePublished - Jul 1 2016

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Hypergraphs with Zero Chromatic Threshold'. Together they form a unique fingerprint.

Cite this