# Chromatic number of regular linear hypergraphs on $\omega$

For any cardinal $$\alpha \in \omega\cup \{\omega\}$$, let $$[\omega]^\alpha$$ denote the collection of subsets of $$\omega$$ having cardinality $$\alpha$$.

A linear hypergraph $$H=(V,E)$$ is a hypergraph such that whenever $$e\neq e_1\in E$$ we have $$|e\cap e_1|\leq 1$$.

A coloring of a hypergraph $$H=(V,E)$$ is a map $$c:V \to \alpha$$, where $$\alpha \neq \varnothing$$ is a cardinal, such that for all $$e\in E$$ with $$|e|>1$$ we have that the restriction $$c{\restriction}_e$$ is non-constant. We denote by $$\chi(H)$$ the smallest cardinal such that there is a coloring from $$V$$ to that cardinal.

If $$\alpha \in (\omega\cup\{\omega\})\setminus \{0,1,2\}$$, is there a linear hypergraph $$H = (\omega, E)$$ with $$E\subseteq [\omega]^\alpha$$ and $$\chi(H)=\aleph_0$$?

• What does "regular" mean in your question title? if you're referring to the fact that all edges are the same size, I think those are usually called "uniform" hypergraphs; "regular" usually refers to vertex degrees. – bof just now
– bof
Jun 17, 2020 at 1:47

For $$\alpha=\omega$$ the answer is no. If $$H=(\omega,E)$$ is a linear hypergraph, then $$E$$ is countable; if $$H=(\omega,E)$$ is any hypergraph with $$E\subseteq[\omega]^\omega$$ and $$E$$ countable, then $$\chi(H)\le2$$.
For $$3\le\alpha\lt\omega$$ the answer is yes. It will be convenient to define the hypergraph on a countable vertex set $$V\ne\omega$$. Let $$H=(V,E)$$ where $$V=[\omega]^{\alpha-1}$$ and $$E=\{[A]^{\alpha-1}:A\in[\omega]^\alpha\}\subseteq[V]^\alpha$$. Then $$H$$ is a linear hypergraph, and $$\chi(G)=\aleph_0$$ because $$\omega\to(\alpha)^{\alpha-1}_n\ (n\lt\omega)$$ by the finite Ramsey theorem.
P.S. $$\omega\to (m)^r_n$$ is Rado's "arrow notation" for "partition relations"; it means that, for any $$n$$-coloring of the $$r$$-element subsets of $$\omega$$, there is an $$m$$-element subset of $$\omega$$ whose $$r$$-element subsets all have the same color.