1
$\begingroup$

We say that a hypergraph $H=(V,E)$ has property ${\bf B}$ if there is $S\subseteq V$ such that for all $e\in E$ with $|e|\geq 2$ we have $$(e\cap S) \neq \emptyset \neq (e\cap (V\setminus S)).$$

If $k\in \omega$, a hypergraph $H=(V,E)$ is $k$-uniform if all elements of $E$ have cardinaliy $k$.

Suppose the hypergraph $(\omega,E)$ is $k$-uniform for some $k\geq 4$, and we have that $$2\cdot |e_0\cap e_1| < k$$ whenever $e_0\neq e_1\in E$. Does this necessarily imply that $(\omega,E)$ has property ${\bf B}$?

$\endgroup$
2
  • 2
    $\begingroup$ "$k$-uniform", not "$k$-regular". $k$-regularity is the dual property that every vertex lies in $k$ edges. $\endgroup$ Commented Jan 27, 2023 at 11:06
  • $\begingroup$ Thanks - will correct $\endgroup$ Commented Jan 27, 2023 at 13:22

1 Answer 1

2
$\begingroup$

There are counterexamples for every integer $k\ge3$.

In fact, if $2\le k\lt\omega$, there is a $k$-uniform hypergraph $H=(V,E)$ such that $|V|=\aleph_0$, $\{e_1,e_2\}\in\binom E2\implies|e_1\cap e_2|\le1$, and $H$ has chromatic number $\chi(H)=\aleph_0$.

Namely, let $V=\binom{\mathbb N}{k-1}$ and $E=\{\binom X{k-1}:X\in\binom{\mathbb N}k\}$.

It follows from Ramsey's theorem that $\chi(H)\gt n$ for each $n\lt\omega$; the other properties are obvious. Moreover, $H$ has a finite subhypergraph $H_n$ with $\chi(H_n)\gt n$.

$\endgroup$

You must log in to answer this question.

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