Hypergraphs such that all finite subhypergraphs are bipartite

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?

1 Answer

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.

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