Skip to main content
Mentioned counterexample (\omega, [\omega]^\omega)
Source Link

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.

Now, aA 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. IfLet $H = (V, E)$ isbe 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. Does it necessarily follow that $H$ itself is 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.

Now, 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$.

Question. If $H = (V, E)$ is a hypergraph 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?

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?

Source Link

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.

Now, 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$.

Question. If $H = (V, E)$ is a hypergraph 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?