A note on panchromatic colorings |
| |
Authors: | Danila Cherkashin |
| |
Affiliation: | Saint Petersburg State University, Faculty of Mathematics and Mechanics, Russian Federation;Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Network Applications, Russian Federation;St. Petersburg Department of V. A. Steklov Institute of Mathematics of the Russian Academy of Sciences, Russian Federation |
| |
Abstract: | This paper studies the quantity , that is the minimal number of edges of an -uniform hypergraph without panchromatic coloring (it means that every edge meets every color) in colors. If then all bounds have a type , where , are some algebraic fractions. The main result is a new lower bound on when is at least ; we improve an upper bound on if .Also we show that has upper and lower bounds depending only on when the ratio is small, which cannot be reached by the previous probabilistic machinery.Finally we construct an explicit example of a hypergraph without panchromatic coloring and with edges for . |
| |
Keywords: | Hypergraph colorings Panchromatic colorings |
本文献已被 ScienceDirect 等数据库收录! |
|