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$_{2}(5) and
$m$_{2}(4), and the
upper bounds for $m$_{3}(7) and
$m$_{4}(9).

Location: http://mech.math.msu.su/~fpm/eng/k09/k097/k09707h.htm

Last modified: April 18, 2010