FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2013, VOLUME 18, NUMBER 3, PAGES 77-115

**Colorings of partial Steiner systems and their applications**

A. B. Kupavskii

D. A. Shabanov

Abstract

View as HTML
View as gif image

This paper deals with extremal problems concerning colorings of
partial Steiner systems.
We establish a new sufficient condition for $r$-colorability of
a hypergraph from some class of such systems in terms of maximum
vertex degree.
Moreover, as a corollary we obtain a new lower bound for the
threshold probability for $r$-colorability of
a random hypergraph in a binomial model.

Location: http://mech.math.msu.su/~fpm/eng/k13/k133/k13307h.htm

Last modified: March 4, 2014