2
$\begingroup$

Starting point. For every simple, undirected graph $G=(V,E)$ there is $E_0\subseteq E$ such that $(V,E_0)$ is minimally connected: the spanning tree. The goal of this question is to find out whether the same thing holds for "graph-like" hypergraphs.

Formulation for hypergraphs. We call a hypergraph $H=(V,E)$ with $V\neq \emptyset$ connected if for all non-empty $X\subseteq V$ with $X\neq V$ there is $e\in E$ with $$e\cap X \neq \emptyset \neq e \cap (V\setminus X).$$

(Trivially, for every connected hypergraph, we have $\bigcup E = V$.)

We say that $H=(V,E)$ is linear if the cardinality of the intersection of any two distinct edges is at most $1$.

Question. If $H =(V,E)$ is a linear connected hypergraph, is there $E_0\subseteq E$ with the following properties?

  1. $(V, E_0)$ is connected, and
  2. whenever $e_0\in E_0$, the hypergraph $\big(V, (E_0\setminus\{e_0\})\big)$ is no longer connected.

Note. There is an easy example showing that if we consider all connected hypergraphs, the answer is negative.

$\endgroup$
2
  • 1
    $\begingroup$ Do you allow infinite edges? $\endgroup$ Commented Jun 7 at 13:26
  • $\begingroup$ Yes, no restriction on the edges $\endgroup$ Commented Jun 7 at 19:24

1 Answer 1

3
$\begingroup$

Counterexample. Let $\mathbb N=\{1,2,3,\dots\}$. For $n\in\mathbb N$ let $[n]=\{1,2,\dots,n\}$. Let $V=\mathbb N\times\mathbb N$. For $n\in\mathbb N$ let $e_n=\{n\}\times\mathbb N$ and $f_n=[n]\times\{n\}$. Let $E=\{e_n:n\in\mathbb N\}\cup\{f_n:2\le n\in\mathbb N\}$. Then $G=(V,E)$ is a connected linear hypergraph. For $E_0\subseteq E$ the spanning subhypergraph $G_0=(V,E_0)$ is connected if and only if $E_0$ contains all the edges $e_n$ and infinitely many of the edges $f_n$.

Another counterexample, this one with finite edges. Let $G=(V,E)$ where $V=\mathbb N\times\mathbb N$ as before, but $E=\{e_{m,n}:m,n\in\mathbb N\}\cup\{f_m:m\in\mathbb N\}$ where $e_{m,n}=\{m\}\times\{2n-1,2n,2n+1\}$ and $f_m=[m]\times\{2m-1\}$.

$\endgroup$

You must log in to answer this question.

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