Erdős-Hajnal problem for H-free hypergraphs

DOI10.1007/S00373-023-02737-6MaRDI QIDQ6144501zbMATH OpenOpenAlexFDO

Authors Danila Cherkashin, Alexey Gordeev, Georgii Strukov

Publication date 29 January 2024

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

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

zbMATH Keywords

Ramsey theoryhypergraph colorings\(H\)-free graphsTurán numbers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Abstract: This paper deals with the minimum number $m_H(r)$ of edges in an $H$-free graph with the chromatic number more than $r$. We show how bounds on Ramsey and Tur'an numbers imply bounds on $m_H(r)$.

Recommendations

• On the Erdős-Hajnal problem for 3-uniform hypergraphs
• Lower bounds for the number of edges in hypergraphs of certain classes
• On the Erdős-Hajnal problem for 3-graphs
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• Improvement of the lower bound in the Erdös-Hajnal combinatorial problem

Cites work

• Coloring \(H\)-free hypergraphs
• Extremal problems in hypergraph colourings
• Greedy colorings of uniform hypergraphs
• Hypergraph Ramsey numbers
• Hypergraph Ramsey numbers: triangles versus cliques
• Independent sets in hypergraphs with a forbidden link
• On the Erdős-Hajnal problem for 3-graphs
• On the chromatic number of set systems
• Regular behavior of the maximal hypergraph chromatic number
• Trees in greedy colorings of hypergraphs

This page was built for publication: Erdős-Hajnal problem for \(H\)-free hypergraphs

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