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
    May 29, 2022 at 19:21
  • 1
    $\begingroup$ @DominicvanderZypen Please feel free to use anything in this answer without acknowledgment. $\endgroup$
    – bof
    May 29, 2022 at 19:26
  • $\begingroup$ Surprisingly, an even simpler construction was used for a counterexample for a conjecture by Aharoni. $\endgroup$ May 29, 2022 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.