A hypergraph $H= (V,E)$ is said to be bipartite if there is $S\subseteq V$ such that for all $e\in E$ with $|e|>1$ we have $$S\cap e\neq \emptyset\neq (e\setminus S).$$ A hypergraph is said to be linear if distinct edges intersect in at most $1$ element, and we say the hypergraph is $\aleph_0$-uniform if every edge contains countably infinite elements.

If $n\geq k$ are positive integers, we denote by $n_k$ the smallest integer $n$ such that there is a $k$-uniform, linear hypergraph $(\{1,\ldots,n\}, E)$ that is not bipartite.

Question. Suppose that $\kappa\geq\aleph_0$ is a cardinal such that there is a linear, $\aleph_0$-uniform, non-bipartite hypergraph $H=(\kappa, E)$. Do we necessarily have $\kappa\geq 2^{\aleph_0}$?


1 Answer 1


Every $\aleph_0$-uniform linear hypergraph is bipartite. More generally:

Theorem. If $H=(V,E)$ is an $\aleph_0$-uniform hypergraph, and if there is a number $n\lt\aleph_0$ such that $|\{e\in E:S\subseteq e\}|\le\aleph_0$ for every $n$-element set $S\subseteq V$, then $\chi(H)\le2$.

The proof is by induction on $|V|$. If $|V|\le\aleph_0$ then $|E|\le\aleph_0$; plainly an $\aleph_0$-uniform hypergraph with at most $\aleph_0$ edges is $2$-colorable. For the induction step we assume that $|V|=\kappa\gt\aleph_0$ and that the theorem holds for hypergraphs with $\lt\kappa$ vertices.

We may assume that $V=\kappa$. For each ordinal $\alpha\in\kappa$ let $V_\alpha$ be the smallest set such that $\alpha\subseteq V_\alpha$ and $\forall e\in E\ (|e\cap V_\alpha|\ge n\implies e\subseteq V_\alpha)$. Then $|V_\alpha|\le|\alpha|+\aleph_0\lt\kappa$ for each $\alpha\in\kappa$, and $V_\beta\subseteq V_\alpha$ if $\beta\le\alpha$, and $V_\alpha=\bigcup_{\beta\lt\alpha}V_\beta$ if $\alpha$ is a limit ordinal. Let $H_\alpha=(V_\alpha,E_\alpha)$ where $E_\alpha=\{e\in E:e\subseteq V_\alpha\}$. Note that $E_\alpha=\bigcup_{\beta\lt\alpha}E_\beta$ if $\alpha$ is a limit ordinal, and $E=\bigcup_{\alpha\lt\kappa}E_\alpha$.

By transfinite recursion we define functions $f_\alpha:V_\alpha\to\{0,1\}$ so that $f_\alpha$ is a proper $2$-coloring of $H_\alpha$ and $f_\beta\subseteq f_\alpha$ whenever $\beta\le\alpha$. To extend $f_\alpha$ to $f_{\alpha+1}$ observe that, if $e\in E_{\alpha+1}\setminus E_\alpha$, then $|e\cap V_\alpha|\lt n$, so $|e\cap(V_{\alpha+1}\setminus V_\alpha)|=\aleph_0$. Since $|V_{\alpha+1}\setminus V_\alpha|\lt\kappa$, the inductive hypothesis will do the job. Finally, $\bigcup_{\alpha\in\kappa}f_\alpha$ is a proper $2$-coloring of $H$.

P.S. A more general version of this theorem was proved by E. W. Miller, On a property of families of sets, Comptes Rendus Varsovie 30 (1937), 31–38; see also P. Erdős and A. Hajnal, On a property of families of sets, Acta Mathematica Hungarica 12 (1961), 87–123.


Your Answer

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

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