2
$\begingroup$

Let $X$ be a set and $\mathcal{F}$ be a finite family of subsets of $X$. We call a set $T\subseteq X$ a tranversal set for $\mathcal{F}$ if it intersects every set in $\mathcal{F}$.

Suppose that $X=\mathbb{R}$ and $\mathcal{F}$ is a finite family of intervals such that any two intersect. Then it is easy to prove that $\mathcal{F}$ admits a transversal set with only one element, namely $\cap\mathcal{F}\neq \emptyset$.

Suppose that every set in $\mathcal{F}$ is union of at most $n$ points and intervals in $\mathbb{R}$, and again that every two sets in $\mathcal{F}$ intersect. Is there a simple combinatorial argument to show whether $\mathcal{F}$ admits a finite transversal set of a certain cardinality?

My guess here being that one such family might always admit a transversal set of cardinality $n$.

$\endgroup$
2
  • 1
    $\begingroup$ 1). "an intervals" --> "and intervals". 2). is it "[at most $n$ points] and intervals" or "at most $n$ [points and intervals]"? $\endgroup$ Jul 16, 2019 at 21:36
  • $\begingroup$ @mathworker21 1)Sure 2) $n$ [points and intervals] $\endgroup$
    – Anguepa
    Jul 19, 2019 at 8:33

1 Answer 1

2
+50
$\begingroup$

There is the following counterexample to your guess. Given a number $n$ let $\mathcal F$ be a family of all unions of at most $n$ closed intervals with endpoints of the from $p/q$ where $p\le q\le 4n(2n-1)$ be non-negative integers (and $q>0$) and of total length $1/2$. Connectedness of $[0,1]$ easily implies that each two members of $\mathcal F$ intersects. On the other hand, let $T$ be any $2n-2$-point subset of a segment $[0,1]$. Then $T$ splits $[0,1]$ into at most $2n-1$ open intervals, so the total length of $n$ longest of them is al least $\tfrac{n}{2n-1}$. It is easy to show that the union of these intervals contains a member of $\mathcal F$ disjoint from $T$.

$\endgroup$
4
  • $\begingroup$ I don't get it. You found a bad $T$. How does this show there is no good $T$? $\endgroup$ Jul 17, 2019 at 11:34
  • 1
    $\begingroup$ @mathworker21 I showed that there is no good $T$ of size $2n-2$. $\endgroup$ Jul 17, 2019 at 15:50
  • 1
    $\begingroup$ I'm assuming $I=[0,1]$ in your reply? $\endgroup$
    – Anguepa
    Jul 24, 2019 at 9:54
  • $\begingroup$ @Anguepa Thanks. Corrected. $\endgroup$ Jul 24, 2019 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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