Proposition to be easily understood

Question

I try to understand a proposition on this. I restate the proposition below :

Is there other way to prove this proposition to be easily understood ? or is there another example for this proposition ?

Answer 1

For a fixed $c≥2$, consider the hypergraph $H=([3c−3],(\binom{[3c−3]}{2c−2}))$, this implies the hypergraph is $(c−1)$-intersecting and all its edges have size $2c−2$.

The vertices of $H$ are $\{1, \ldots, 3c-3\}$, and the hyperedges are the subsets of size $2c-2$. By the Pigeonhole Principle, two distinct hyperedges must share at least $c-1$ common vertices. So $H$ is $(c-1)$-intersecting.

Now $\chi(c-1, c)$ is the minimum number such that for any $(c-1)$-intersecting hypergraph, each hyperedge $e$ covers its vertices with at least $\min\{c, |e|\}$ distinct colors.

The proof in the paper is a proof by contradiction. Suppose for a contradiction that we can color $H$ with fewer than $2c-1$ colors (so at most $2c-2$ colors). The goal is to exhibit a hyperedge with fewer than $c$ colors.

So suppose we color $H$ with $2c-2$ colors. Dividing up the vertices as evenly as possible, each color class contains at least : $$\lfloor \frac{3c-3}{2c-2} \rfloor = 1$$

Vertices. But we have leftover vertices. So the most common $c-1$ colors actually cover:

$$(c-1) \lceil \frac{3c-3}{2c-2} \rceil = 2(c-1)$$

Vertices. These vertices form a single hyperedge $e$, which belongs to $H$ (since $H$ contains all $\binom{[3c-3]}{2c-2}$ hyperedges of size $2c-2$). Note that $e$ only covers its vertices with $c-1$ colors by construction. However, $\chi(c-1, c)$ requires each hyperedge have at least $c$ distinct colors, a contradiction.