Graph Colorings – Chromatic Number of Duals of Uniform Hypergraphs with Large Edges

graph-coloringshypergraphinfinite-combinatoricsset-theory

Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say that $H$ is $\kappa$uniform if $|e|=\kappa$ for all $e\in E$.

If $X$ is a non-empty set, then a map $c:V\to X$ is said to be a colouring if for every edge $e\in E$ with $|e|\geq 2$ the restriction $c\restriction_e: e\to X$ is not constant. The smallest cardinal $\kappa$ for which there is a colouring $c:V \to \kappa$ is said to be the chromatic number of $H$ and is denoted by $\chi(H)$.

The dual of the hypergraph $H=(V,E)$ is $H^\partial = (E, E_V)$ where $$E_V = \big\{S\subseteq E: \text{there is }v_0\in V \text{ such that } S = \{e\in E: v_0\in e\}\big\}.$$

Question. Given cardinals $\alpha, \beta \geq 2$, is there an $\alpha$-uniform hypergraph $H=(V,E)$ with $\chi(H) = \beta$ and $\chi(H^\partial) = 2$?

Best Answer

Theorem. For any cardinals $\alpha,\beta\ge2$ there is an $\alpha$-uniform hypergraph $H$ with $\chi(H)=\beta$ and $\chi(H^\partial)=2$.

Proof. Let $V=\bigcup_{\xi\in\beta}V_\xi$ where the sets $V_\xi$ are pairwise disjoint and $|V_\xi|\gt\alpha\beta$. Let $E=\{e\in[V]^\alpha:|\{\xi\in\beta:e\cap V_\xi\ne\varnothing\}|\ge2\}$.

Plainly $H=(V,E)$ is an $\alpha$-uniform hypergraph and $\chi(H)=\beta$. To see that $\chi(H^\partial)=2$ color each vertex red or blue so that each set $V_\xi$ contains at least $\alpha$ vertices of each color. Then each vertex of $H$ is contained in both a monochromatic edge and a bichromatic edge, whence $\chi(H^\partial)=2$.

Related Question