A note on panchromatic colorings

2017/05/10 by Cherkashin, Danila
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1705.03797

Abstract

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 ≤ c (n)/(ln n) then all bounds have a type A₁(n, ln n, r)((r)/(r-1))ⁿ ≤ p(n, r) ≤ A₂(n, r, ln r) ((r)/(r-1))ⁿ, where A₁, A₂ are some algebraic fractions. The main result is a new lower bound on p(n,r) when r is at least c √ n; we improve an upper bound on p(n,r) if n = o(r^3/2). Also we show that p(n,r) has upper and lower bounds depend only on n/r when the ratio n/r is small, which can not be reached by the previous probabilistic machinery. Finally we construct an explicit example of a hypergraph without panchromatic coloring and with ((r)/(r-1) + o(1))ⁿ edges for r = o(√((n)/(ln n))).

Related

• A note on random greedy coloring of uniform hypergraphs
• Regular behaviour of the maximal hypergraph chromatic number
• Coloring H-free Hypergraphs
• On some generalizations of the property B-problem of an n-uniform hypergraph
• A new randomized algorithm for the Erdos--Hajnal problem