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