pith. sign in

arxiv: 1705.03797 · v1 · pith:XRYGAIDVnew · submitted 2017-05-10 · 🧮 math.CO

A note on panchromatic colorings

classification 🧮 math.CO
keywords fracpanchromaticboundboundscoloringedgeseveryhypergraph
0
0 comments X
read the original 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 \leq c \frac{n}{\ln n}$ then all bounds have a type $A_1(n, \ln n, r)(\frac{r}{r-1})^n \leq p(n, r) \leq A_2(n, r, \ln r) (\frac{r}{r-1})^n$, where $A_1$, $A_2$ are some algebraic fractions. The main result is a new lower bound on $p(n,r)$ when $r$ is at least $c \sqrt 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 $(\frac{r}{r-1} + o(1))^n$ edges for $r = o(\sqrt{\frac{n}{\ln n}})$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.