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

You must log in to answer this question.

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