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$?


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.