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.

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

1 Answer 1

Reset to default
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\}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.