Hypergraphs with zero chromatic threshold

DOI10.1007/S00373-015-1667-6MaRDI QIDQ2631069zbMATH OpenOpenAlexFDO

Authors József Balogh, John Lenz

Publication date 28 July 2016

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.7363

zbMATH Keywords

\(r\)-uniform hypergraphchromatic threshold

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

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 $$ has bounded chromatic number. The study of chromatic thresholds of various graphs has a long history, beginning with the early work of ErdH{o}s-Simonovits. One interesting question, first proposed by L{}uczak-Thomass'{e} and then solved by Allen-B"{o}ttcher-Griffiths-Kohayakawa-Morris, is the characterization of graphs having zero chromatic threshold, in particular the fact that there are graphs with non-zero Tur'{a}n density that have zero chromatic threshold. In this paper, 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 special product of the Bollob'as-ErdH{o}s graph defined earlier by the authors.

Recommendations

• On the Chromatic Thresholds of Hypergraphs
• The chromatic thresholds of graphs
• Chromatic thresholds in dense random graphs
• Chromatic thresholds in sparse random graphs
• Constructions of sparse uniform hypergraphs with high chromatic number

Cites work

• Dense graphs with small clique number
• On a Ramsey-Turán type problem
• On a valence problem in extremal graph theory
• On the chromatic number of pentagon-free graphs of large minimum degree
• On the chromatic number of triangle-free graphs of large minimum degree
• On the Chromatic Thresholds of Hypergraphs
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the Ramsey-Turán numbers of graphs and hypergraphs
• On the structure of triangle-free graphs of large minimum degree
• Some exact Ramsey-Turán numbers
• The chromatic thresholds of graphs

Cited in

(3)

• Threshold hypergraphs
• The chromatic thresholds of graphs
• On the Chromatic Thresholds of Hypergraphs

This page was built for publication: Hypergraphs with zero chromatic threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631069)