This article is cited in 5 papers

Combinatorial Extremum Problems for $2$-Colorings of Hypergraphs

A. P. Rozovskaya

M. V. Lomonosov Moscow State University

Abstract: We consider a generalization of the Erdős–Hajnal classical combinatorial problem. Let $k$ be a positive integer. It is required to find the value of $m_k(n)$ equal to the minimum number of edges of an $n$-uniform hypergraph that does not admit $2$-colorings of the set of its vertices such that each edge of the hypergraph contains exactly $k$ vertices of each color. In the present paper, we obtain a new asymptotic lower bound for $m_k(n)$, which improves the preceding results in a wide range of values of the parameter $k$. We also consider some other generalizations of this problem.

Keywords: $n$-uniform hypergraph, $2$-coloring, asymptotic lower bound.

UDC: 519.112.7+519.179.1

Received: 09.12.2009
Revised: 23.02.2011

DOI: 10.4213/mzm8604

 English version: Mathematical Notes, 2011, 90:4, 571–583

Bibliographic databases:

• 
• 
•