-2
$\begingroup$

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.)

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What if $H$ is a graph which is the union of infinitely many vertex-disjoint triangles? $\endgroup$
    – bof
    Commented Dec 1, 2017 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
    Commented Dec 1, 2017 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
    Commented Dec 1, 2017 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
    Commented Dec 1, 2017 at 9:27

1 Answer 1

Reset to default
2
$\begingroup$

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)

Improve this answer
$\endgroup$

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