On the Erd\H os--Hajnal problem in the case of 3-graphs

2019/05/07 by Danila Cherkashin, Cherkashin, Danila
Mathematics · Engineering · #Limits and Structures in Graph Theory #graph theory and CDMA systems #Finite Group Theory Research

paper · pdf · doi:10.48550/arxiv.1905.02893

Abstract

Let m(n,r) denote the minimal number of edges in an n-uniform hypergraph which is not r-colorable. For the broad history of the problem see [RaiSh]. It is known that for a fixed n the sequence (m(n,r))/(rⁿ) has a limit. The only trivial case is n=2 in which m(2,r) = \binomr+12. In this note we focus on the case n=3. First, we compare the existing methods in this case and then improve the lower bound.

Related

• A new randomized algorithm for the Erdos--Hajnal problem
• Erd\H os--Hajnal problem for H-free hypergraphs
• On some generalizations of the property B-problem of an n-uniform hypergraph
• On a problem of Brown, Erdős and Sós
• Regular behaviour of the maximal hypergraph chromatic number