4
$\begingroup$

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

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .