FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2009, VOLUME 15, NUMBER 7, PAGES 141-163

On balanced colorings of hypergraphs

A. P. Rozovskaya
M. V. Titova
D. A. Shabanov

Abstract

View as HTML     View as gif image

The paper deals with an extremal problem concerning hypergraph colorings. Let $k$ be an integer. The problem is to find the value $m$_k(n) equal to the minimum number of edges in an $n$-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains $k$ vertices of each color. In this paper, we obtain the exact values of $m$₂(5) and $m$₂(4), and the upper bounds for $m$₃(7) and $m$₄(9).

Location: http://mech.math.msu.su/~fpm/eng/k09/k097/k09707h.htm
Last modified: April 18, 2010