2
$\begingroup$

Let $\omega$ denote the first infinite ordinal (also known as the set of natural numbers). We call a set $E\subseteq {\cal P}(\omega)$ a deck if for all $n\in \omega$, the set $E$ contains exactly one member of cardinality $n$. (More formally, $E$ is a deck if for all $n\in \omega$ we have $|\{e\in E: |e| = n\}| = 1$.)

If $H=(V,E)$ is a hypergraph and $k\neq\emptyset$ is a cardinal, we say that a map $c:V\to\kappa$ is a coloring if for any $e\in E$ with $|e|>1$ we have that the restriction $c|_e:e\to\kappa$ is not constant. The smallest cardinal $\kappa> 0$ such that there is a coloring $c:V\to \kappa$ is said to be the chromatic number $\chi(H)$ of $H$.

Question. Given $k\in\omega\setminus\{0\}$, is there a deck $E\subseteq{\mathcal P}(\omega)$ such that for $H=(\omega, E)$ we have $\chi(H) = k$?

$\endgroup$
1
  • 1
    $\begingroup$ I'm not sure about the tagging. The "combinatorics" here is not all that "infinite" if we recall that a hypergraph (with finite edges) is $k$-colorable for a fixed (finite) $k$ if and only if every finite subhypergraph is $k$-colorable. $\endgroup$
    – bof
    Commented Jul 23, 2023 at 7:13

1 Answer 1

3
$\begingroup$

The answer is plainly negative for $k=1$ and positive for $k=2$. The answer is negative for $k\gt2$ because $(\omega,E)$ is $2$-colorable whenever the edge-set $E$ is a "deck," i.e., contains just one edge of size $n$ for each integer $n\ge2$. To see this consider a random $2$-coloring of $\omega$; the probability that it fails to be a proper coloring of $(\omega,E)$ is strictly less than $\sum_{n=1}^\infty2^{-n}=1$. Alternatively, color the vertices recursively, First spoil the edge of size $2$ by coloring one vertex red and one vertex blue. Next spoil the edge of size $3$ by coloring at most one more vertex in each color. When we come to coloring the edge of size $n$, we will already have colored at most $n-1$ vertices in each color, so we can continue the process.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .