0
$\begingroup$

Let $H=(V,E)$ be a hypergraph. We say that $C\subseteq V$ is a choice set if $|C\cap e| = 1$ for all $e\in E$.

Question. Let $H=(V,E)$ be a hypergraph with $e$ finite for all $e\in E$, and suppose that for all finite sets $E_0\subseteq E$ the hypergraph $(V, E_0)$ has a choice set. Does $H$ itself necessarily have a choice set?

Improve this question
$\endgroup$
5
  • $\begingroup$ Right, Fedor, thanks for your answer. Is it still the same if all the members of $E$ are finite? I will modify the question accordingly. - I was hoping some compactness argument would work, but I didn't manage it. If you write down the compactness argument in an answer (or provide another answer), I'll be more than happy to accept $\endgroup$
    – Dominic van der Zypen
    Commented Jun 7, 2022 at 8:08
  • 2
    $\begingroup$ @FedorPetrov How is the hypergraph consisting of all infionite subsets of a countably infinite set a counterexample to the original question? If $E_0=\{e_1,e_2,e_1\cup e_2\}$ where $e_1\cap e_2=\varnothing$, then $E_0$ has no choice set. What am I missing? $\endgroup$
    – bof
    Commented Jun 7, 2022 at 9:03
  • 1
    $\begingroup$ Ooops. I was thinking on perfect matching instead, sorry $\endgroup$
    – Fedor Petrov
    Commented Jun 7, 2022 at 9:20
  • 2
    $\begingroup$ For a counterexample with infinite edges, consider a maximal almost disjoint family of infinite subsets of $\mathbb N$ which contains an infinite collection of pairwise disjoint sets. Alternatively, consider the lines of the real projective plane. $\endgroup$
    – bof
    Commented Jun 7, 2022 at 9:21
  • 2
    $\begingroup$ Lines on the usual (affine) real plane also work. Or a rational plane, if you prefer countably many vertices and edges. $\endgroup$
    – Fedor Petrov
    Commented Jun 7, 2022 at 9:25

1 Answer 1

Reset to default
3
$\begingroup$

For finite edges this follows indeed from compactness. Consider the Cartesian product $K=\prod e$ of all edges in Tychonoff topology. This $K$ may be understood as the set of simultaneous choices $v_e\in e$ for all edges $e$. For every pair $e\ne f$ of edges consider the open set $U(e,f)\subset K$ determined as follows: a vertex chosen in $e$ belongs to $f$. If these open sets do not cover $K$, then a choice set exists. If they do cover $K$, then finitely many of them cover $K$, that means that the choice set does not exist for finitely many edges.

Improve this answer
$\endgroup$

You must log in to answer this question.

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