2
$\begingroup$

Motivation. My sons participated in a large football tournament recently; everyone wanted to be in a team with everyone else at least once. Tricky!

Formulation of the question. For any positive integer $k\in\mathbb{N}$, let $\ \binom {\mathbb N} k\ $ denote the collection of $k$-element subsets of $\mathbb{N}.\ $ Let ${\cal I}$ be the collection of subsets of $\mathbb{N}$ that are both infinite and co-infinite (the complement is infinite).

Fix an integer $k\geq 2$. Is there a finite family $\ {\cal S}\subseteq {\cal I}\ $ such that for every $\ F\in\binom {\mathbb N} k\ $ there is $T\in{\cal S}\ $ with $F\subseteq T$ or $F\subseteq (\mathbb{N}\setminus T)$?   If yes, what is the smallest size such a family ${\cal S}$ can have, in terms of $k$?


Note. I originally posted this question for $k=2$ and arbitrary subsets of $\mathbb{N}$, not just infinite/co-infinite ones. Zach Teitler quickly gave an elegant solution and suggested this generalization. First it seemed $k=2$ was solved, but it turns out $k=2$ is still unresolved.

$\endgroup$
13
  • 1
    $\begingroup$ I think $S=\{\{1\},\{2\},\{3\}\}$ works. $\endgroup$ Nov 20 at 13:28
  • 1
    $\begingroup$ Right @ZachTeitler - sorry. Can it be done with sets that are infinite and co-infinite? Will change the question accordingly $\endgroup$ Nov 20 at 13:30
  • 2
    $\begingroup$ Size $|S|=2$ is clearly impossible. How about $|S|=3$ like this: let each $S_i$, $i=1,2,3$, be the set of integers congruent to $0$ or $i$ modulo $4$. $\endgroup$ Nov 20 at 13:36
  • 1
    $\begingroup$ This is a fun question. How far can we generalize, eg, to $k$-team games? $\endgroup$ Nov 20 at 13:40
  • 2
    $\begingroup$ @WlodAA: see meta.mathoverflow.net/questions/5508/… for a fix. $\endgroup$ Nov 20 at 20:51

1 Answer 1

4
$\begingroup$

For $k\ge2$, if we partition $\mathbb N$ into $k+1$ infinite sets $S_0,S_1,\dots,S_k$, then each $S_i$ is coinfinite, and every $k$-element subset of $\mathbb N$ is contained in the complement of some $S_i$.

This is best possible: for $k\ge2$, given $k$ nonempty proper subsets of $\mathbb N$, there is a $k$-element set which meets all of those sets and their complements. The proof is by induction.

For $k=2$, suppose $S_1$ and $S_2$ are nonempty proper subsets of $\mathbb N$. If neither is contained in the other, choose $x_1\in S_1\setminus S_2$ and $x_2\in S_2\setminus S_1$; if one is contained in the other, say $S_1\subseteq S_2$, choose $x_1\in S_1$ and $x_2\in\mathbb N\setminus S_2$. In either case the set $\{x_1,x_2\}$ meets each of the sets $S_1,S_2,\mathbb N\setminus S_1,\mathbb N\setminus S_2$.

For the induction step, let $S_1,\dots,S_k,S_{k+1}$ be nonempty proper subsets of $\mathbb N$, and let $F=\{x_1,\dots,x_k\}$ be a $k$-element set which meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k$. Choose $x_{k+1}\in\mathbb N$ so that $x_{k+1}\in S_{k+1}\iff x_1\notin S_{k+1}$. Then the set $F\cup\{x_{k+1}\}$ has at most $k+1$ elements and meets $S_i$ and $\mathbb N\setminus S_i$ for $1\le i\le k+1$.

$\endgroup$
1
  • $\begingroup$ @SamHopkins I think the "cofinite" bit is a little bug that crept in -- but the elegance of this archetypical bof-solution lies in the following bit (I think): if $F$ has $n$ elements and $S_0,\ldots S_n$ are $n+1$ sets partitioning $\mathbb{N}$, then $F$ cannot intersect all of the $S_i$. So suppose it doesn't intersect $S_j$. Then $F\subseteq (\mathbb{N}\setminus S_j)$. (Apologies for this laudatory speech on bof, but I have seen a lot of answers by him, many of them so simple and to the point like a simple and elegant chess move that still most chess players don't find.) $\endgroup$ Nov 20 at 20:55

Your Answer

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

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