On some generalizations of the property B-problem of an n-uniform hypergraph

2019/03/27 by Demidovich, Yury
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1903.11708

Abstract

The extremal problem of hypergraph colorings related to Erdős--Hajnal property B-problem is considered. Let k be a natural number. The problem is to find the value of m_k(n) equal to the minimal number of edges in an n-uniform hypergraph not admitting 2-colorings of the vertex set such that every edge of the hypergraph contains at least k vertices of each color. In this paper we obtain new lower bounds for m_k(n).

Related

• Improved Lower Bounds for Property B
• On the Erd\H os--Hajnal problem in the case of 3-graphs
• A new randomized algorithm for the Erdos--Hajnal problem
• Coloring H-free Hypergraphs
• On small n-uniform hypergraphs with positive discrepancy