Return to Answer

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. This theorem is a special case of a result of E. W. Miller, On a property of families of sets, Comptes Rendus Varsovie,30 (1937), pp. 31–38; see also P. Erdős and A. Hajnal, On a property of families of sets, Acta Mathematica Hungarica 12 (1961), 87–123.

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.

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

Remark. This argument is my attempt to adapt an idea from an old paper of Erdős, Hajnal, and Rothschild that I don't have access to at the moment. If I remember right, they proved (among other things) that a $3$-uniform linear hypergraph of order $\aleph_1$ has chromatic number at most $\aleph_0$.

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. This theorem is a special case of a result of E. W. Miller, On a property of families of sets, Comptes Rendus Varsovie,30 (1937), pp. 31–38; see also P. Erdős and A. Hajnal, On a property of families of sets, Acta Mathematica Hungarica 12 (1961), 87–123.

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.

Remark. This argument is my attempt to adapt an idea from an old paper of Erdős, Hajnal, and Rothschild that I don't have access to at the moment. If I remember right, they proved (among other things) that a $3$-uniform linear hypergraph of order $\aleph_1$ has chromatic number at most $\aleph_0$.

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

Remark. This argument is my attempt to adapt an idea from an old paper of Erdős, Hajnal, and Rothschild that I don't have access to at the moment. If I remember right, they proved (among other things) that a $3$-uniform linear hypergraph of order $\aleph_1$ has chromatic number at most $\aleph_0$.