Let $H=(V,E)$ be a hypergraph such that $|V|$ is infinite, and the following statements hold:

  1. if $a\neq b\in E$ then $|a\cap b|\leq 1$, and
  2. every vertex $v\in V$ is contained in at least $2$ members of $E$.

Is there $P\subseteq E$ such that the members of $P$ are pairwise disjoint, and $\bigcup P = V$? (This would amount to a kind of matching in hypergraphs.)


closed as off-topic by Ben Barber, Jan-Christoph Schlage-Puchta, RP_, Chris Godsil, David Handelman Dec 6 '17 at 3:08

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Ben Barber, Jan-Christoph Schlage-Puchta, RP_, David Handelman
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What if $H$ is a graph which is the union of infinitely many vertex-disjoint triangles? $\endgroup$ – bof Dec 1 '17 at 6:58
  • $\begingroup$ In that case, each $v\in V$ is contained only in one member of $E$, or do I misunderstand something? $\endgroup$ – Dominic van der Zypen Dec 1 '17 at 7:14
  • 1
    $\begingroup$ No doubt I misunderstand something. My $H$ is the union of infinitely many vertex-disjoint copies of the graph $K_3.$ Each vertex is in two edges, each edge contains two vertices, and two distinct edges have at most one vertex in common. $\endgroup$ – bof Dec 1 '17 at 9:22
  • $\begingroup$ The edges don't have to be finite sets, do they? In the first example I thought of, the vertices are the points of the real projective plane, the points are the lines; two edges intersect in exactly one vertex, each vertex belongs to continuum many edges. $\endgroup$ – bof Dec 1 '17 at 9:27

Consider the following (connected) hypergraph: A counter example

i.e. $V = \{v,w,x\}\cup\{1,2,3,\dots\}, E = \{\color{blue}{\{v,x\}}, \color{red}{\{v,w\}}, \color{orange}{\{w,x,1\}}\}\cup\{\{1,2\}, \{2,3\}, \dots\}$

To cover the vertex $v$ you need to include the blue or the red edge in $P$. But then you can't also include the yellow edge. Thus either $x$ or $w$ won't be covered.

Edit: With bof's new comment I just realized that my graph is basically the same idea as bof's first example. So if they are misunderstanding something I'm almost certainly making the same mistake (so this "answer" should probably be just a comment)


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