A note on panchromatic colorings

Discrete Mathematics. 2018. Vol. 341. No. 3. P. 652–657.

Cherkashin Danila

This paper studies the quantity p(n,r), that is the minimal number of edges of an n-uniform hypergraph without panchromatic coloring (it means that every edge meets every color) in r colors. If r≤cnlnn then all bounds have a type A1(n,lnn,r)(rr−1)n≤p(n,r)≤A2(n,r,lnr)(rr−1)n, where A1, A2 are some algebraic fractions. The main result is a new lower bound on p(n,r) when r is at least cn; we improve an upper bound on p(n,r) if n=o(r3∕2).

 

Also we show that p(n,r) has upper and lower bounds depending only on n∕r when the ratio n∕r 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 

(rr−1+o(1))n edges for r=o(nlnn).

 

 

 

 

Keywords: vertex coloring, гиперграф, Uniform Hypergraphs, panchromatic coloring, вершинная раскраска, панхроматическая раскраска