1
$\begingroup$

Let $H=(V,E)$ be a hypergraph such that $\emptyset\notin E$. We say that $C\subseteq V$ is a (vertex) cover if for all $e \in E$ we have $C\cap e\neq \emptyset$. The minimum size that a cover can have is denoted by $\nu(H)$.

A set $M\subseteq E$ is said to be a matching if $M$ consists of pairwise disjoint members of $E$. Clearly, for any matching $M\subseteq E$ we have $|M|\leq \nu(H)$. We say that $H$ is balanced if there is a matching $M$ with $|M| = \nu(H)$.

Question. Let $H=(V,E)$ be a hypergraph such that for all finite $E_0\subseteq E$ the hypergraph $(V, E_0)$ is balanced. Does this imply that $H$ itself is balanced?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

If infinite edges are allowed, there are trivial counterexamples. Let $H=(V,E)$ where $V$ is an infinite set and $E$ is the set of all cofinite subsets of $V$; then $\nu(H)=\aleph_0$ while $\nu((V,E_0))=1$ for any nonempty finite subset $E_0$ of $E$.

If the edges of the hypergraph $H=(V,E)$ are nonempty finite sets, then the answer to your question is yes. Let $M\subseteq E$ be a maximal matching, so that $\bigcup M$ is a vertex cover and $|M|\le\nu(H)\le|\bigcup M|$. If $M$ is infinite then $\nu(H)=|M|$ and we're done, so suppose $M$ is finite. Then $\nu(H)$ is finite, and a simple compactness argument shows that there must be a finite set $E_0\subseteq E$ with $\nu((V,E_0))=\nu(H)$. Since $(V,E_0)$ is balanced, there is a matching $M_0\subseteq E_0$ with $|M_0|=\nu(H)$.

$\endgroup$
3
  • 1
    $\begingroup$ @DominicvanderZypen What construction answers what question? I find it hard to believe that anything in this simple answer of mine answers a question of Aharoni. $\endgroup$
    – bof
    Commented May 29, 2022 at 19:21
  • 1
    $\begingroup$ @DominicvanderZypen Please feel free to use anything in this answer without acknowledgment. $\endgroup$
    – bof
    Commented May 29, 2022 at 19:26
  • $\begingroup$ Surprisingly, an even simpler construction was used for a counterexample for a conjecture by Aharoni. $\endgroup$ Commented May 29, 2022 at 20:51

You must log in to answer this question.

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