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$ Jan 27, 2023 at 11:06
  • $\begingroup$ Thanks - will correct $\endgroup$ 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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