2
$\begingroup$

I was wondering whether there is a generalization of Martin Sleziak's excellent answer to this question:

Suppose that $S$ is an infinite set, and let ${\cal L}$ be a collection of subsets of $S$ such that for all $L_1\neq L_2\in {\cal L}$ the intersection $L_1\cap L_2$ contains at most one element. Is there $M\subseteq S$ such that

  1. $M$ intersects all the elements of ${\cal L}$, but
  2. for all $m\in M$, the set $M\setminus\{m\}$ no longer intersects all the elements of $\cal L$

?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ What if $S$ is the non-negative integers, $\mathcal{L} = \{\ \{0, n\}: n > 0\ \}$, and $M = \{0\}$. I suspect I don't fully understand the question. $\endgroup$
    – yberman
    Commented Aug 31, 2017 at 7:25
  • $\begingroup$ @YBerman Thanks for your comment & example. In your example, the set $M=\{0\}$ has the desired properties. The question is whether for all infinite sets $S$ and collections ${\cal L}$ of subsets meeting the desired properties, such a set $M$ exists. $\endgroup$
    – Dominic van der Zypen
    Commented Aug 31, 2017 at 8:28
  • $\begingroup$ This is the dual of your earlier question: if ${\cal H}$ is a set of (nonempty) subsets of $S$, then for $x\in S$ define ${\cal H}_x=\{H\in{\cal H}:x\in H\}$. Notice that if $H\cap H'|\leq 1$ for $H\neq H'\in{\cal H}$, then $|{\cal H}_x\cap {\cal H}_y|\leq 1$ for $x\neq y$, and a minimal covering set (in one sens) of ${\cal H}$ is a minimal covering set (in the other sense) of the other. I have some thoughts on this, will send you an email. $\endgroup$
    – Péter Komjáth
    Commented Aug 31, 2017 at 8:30

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .