TY - JOUR

T1 - A note on panchromatic colorings

AU - Cherkashin, Danila

PY - 2018/3/1

Y1 - 2018/3/1

N2 - 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 [Formula presented] then all bounds have a type [Formula presented], 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 [Formula presented].

AB - 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 [Formula presented] then all bounds have a type [Formula presented], 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 [Formula presented].

KW - Hypergraph colorings

KW - Panchromatic colorings

KW - EDGES

KW - UNIFORM HYPERGRAPHS

UR - http://www.scopus.com/inward/record.url?scp=85035814485&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2017.10.030

DO - 10.1016/j.disc.2017.10.030

M3 - Article

AN - SCOPUS:85035814485

VL - 341

SP - 652

EP - 657

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 3

ER -