0
$\begingroup$

The starting point of this question is the following true statement for graphs:

A simple, undirected graph $G = (V,E)$ is bipartite if and only if for all $E_0\subseteq E$ the graph $(V, E_0)$ is bipartite.

Note that any graph is bipartite if it does not have any odd cycles. Using this, it is not hard to prove the above statement.

A hypergraph $H=(V,E)$ is bipartite if there is $D\subseteq V$ such that whenever $e\in E$ and $|e|> 1$, we have that $D$ intersects $e$, and also $V\setminus D$ intersects $e$.

One might hope that if $H = (V, E)$ is a hypergraph such that for all finite $E_0\subseteq E$ the hypergraph $(V, E_0)$ is bipartite, we get that $H$ itself is bipartite. But if $[\omega]^\omega$ is the collection of infinite subsets of $\omega$, then the hypergraph $(\omega, [\omega]^\omega)$ shows that is not true.

Question. Let $H = (V, E)$ be a hypergraph such that there is $n\in \omega$ with $|e|\leq n$ for all $e\in E$ and such that for all finite $E_0\subseteq E$ the hypergraph $(V, E_0)$ is bipartite. Does it necessarily follow that $H$ itself is bipartite?

$\endgroup$

1 Answer 1

1
$\begingroup$

Even if all edges are finite (not necessarily of uniformly bounded size), this is correct. It follows from the compactness argument: the set $2^V$ of all maps $V\to \{0,1\}$ is a Tychonoff compact set, for each $e$ the set $F(e)$ of all functions which are constant on $e$ is open. So, if such sets cover $2^V$, then finitely many of them cover $2^V$. In other words, if the hypergraph is not bipartite, a certain finite subhypergraph is not bipartite.

$\endgroup$
2
  • $\begingroup$ I love this link to topology, thanks Fedor! Amazing how quickly you came up with this argument. $\endgroup$ Commented May 31, 2022 at 14:02
  • 1
    $\begingroup$ shorturl.at/oFHU0 so you see it is a standard argument in such questions $\endgroup$ Commented May 31, 2022 at 14:59

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.