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

  • $\begingroup$ 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 $\endgroup$
    – bof
    Jun 17, 2020 at 1:47

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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