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$

?

$\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
    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$ 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$ Aug 31, 2017 at 8:30

0

Your Answer

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

Browse other questions tagged or ask your own question.