1
$\begingroup$

We say that a hypergraph $H=(V,E)$ is a linear hypergraph if it has the following properties:

  • if $e_1\neq e_2\in E$ then $|e_1\cap e_2|\leq 1$, and
  • $\bigcup E = V$.

We say that $C\subseteq E$ is a covering if $\bigcup C = V$, and we set $$\text{mult}(C) = \{v\in V:|\{e\in C: v\in e\}| >1 \}.$$

Given a covering $C\subseteq E$, is there a covering $C_0\subseteq E$ such that the following statements hold?

  • $\text{mult}(C_0)\subseteq \text{mult}(C)$, and
  • for every covering $D\subseteq E$ with $\text{mult}(D) \subseteq \text{mult}(C_0)$ we have $\text{mult}(D)=\text{mult}(C_0)$.
$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .