3
$\begingroup$

We say that a hypergraph $H=(V,E)$ is connected if the following condition holds:

for all $S\subseteq V$ with $\emptyset\neq S \neq V$ there is $e\in E$ that meets both $S$ and $V\setminus S$, i.e. $$S\cap e \neq \emptyset \neq (V\setminus S)\cap e.$$

Given $H=(V,E)$ connected, is there $E_0\subseteq E$ with the following properties?

  1. $(V,E_0)$ is connected, and
  2. whenever $E'\subseteq E_0$ with $E'\neq E_0$ then $(V,E')$ is no longer connected.
Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Let $V=E=\omega$. Connected subgraphs are precisely those which contain as edges $n$ for arbitrarily large $n$. Clearly there is no minimal such subgraph.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you clarify on the edges? Is there only one edge, or every edge is an element of $ω$? $\endgroup$
    – LeechLattice
    Commented Sep 18, 2019 at 11:29
  • 3
    $\begingroup$ @Bullet51 $E=\omega=\{0,1,2,3,\dots\}=\{\{\},\{0\},\{0,1\},\dots\}$. That is, edges are the (proper) initial segments of $\omega$. Perhaps I went a little too far trying to make my answer as concise as possible :P $\endgroup$
    – Wojowu
    Commented Sep 18, 2019 at 11:32

You must log in to answer this question.

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