Suppose we have a family $F$ such that:

  1. For each $A \in F$ we have $|A| = k$ and $A \subset n$.
  2. For each $A,B \in F$ we have $A \cap B \neq \emptyset$.

It is easy to show that there exists a nonempty set $B \subset n$ such that:

  1. For each $A \in F$ we have $B \cap A \neq \emptyset$.
  2. $|B| \le k^2$.

Proof: Say $|F| = m$. Define $d(x) = |\{A \in F| x \in A\}|$. Define $D(A) = \sum_{x \in A}d(x)$. In order to have condition (2) for all $A \in F$ we must have $D(A) \ge m$. Thus $A$ must contain at least one element $x$ such that $d(x) \ge m/k$. But there are at most $k^2$ such elements, because $D(\bigcup F) = \sum_{x < n} d(x) = km$. Hence we can take $B=\{a \in n| d(a) \ge m/k \}$.

Question: The above result gives an upper limit on the size of $B$ that is not dependent on $n$. Is this still true for $A \subset \omega$ and $F$ infinite?

The same question was asked in https://math.stackexchange.com/questions/1948282/unavoidable-finite-set-for-infinite-intersecting-family, but got no reply.

  • $\begingroup$ What does the notation $A \subset n$ mean? $\endgroup$ – Joseph O'Rourke Oct 4 '16 at 11:49
  • 1
    $\begingroup$ $A$ is a subset of ${0,...n-1}$. $\endgroup$ – Alon Navon Oct 4 '16 at 11:50
  • 2
    $\begingroup$ Can't we just choose some element of $F$ in place of $B$? It meets every element in $F$ and has just $k$ elements... $\endgroup$ – Ilya Bogdanov Oct 4 '16 at 13:43
  • $\begingroup$ @IlyaBogdanov You're right. I should have explicitly written that we want a "new set", i.e one that doesn't already belong to $F$. $\endgroup$ – Alon Navon Oct 4 '16 at 14:14
  • $\begingroup$ Add one extra element... Btw, why doesn't your construction provide an element of $F$? $\endgroup$ – Ilya Bogdanov Oct 4 '16 at 14:53

Certainly. Just "pass to the limit". One possible way to do it (in the old fashioned "given $\varepsilon>0$, find $\delta>0$ style"; I will leave recasting it into a slick compactness argument to you) is to consider all finite subsets $F'$ of $F$ and the corresponding $B(F')$. Now choose a set $B$ of largest cardinality (possibly $0$) such that for every finite $F''$ there is $F'\supset F''$ with $B\subset B(F')$. Clearly, $|B|\le k^2$. Also I claim that each set $A\in F$ has at least one element in $B$. Suppose it is not the case for some $A$. Note that in the definition of $B$ we can restrict our attention to finite $F''\ni A$. If for each $x\in A$ we can find $F''_x\ni A$ such that the conditions $F'\supset F''_x, B\subset B(F'), x\in B(F')$ are incompatible, then for $F''=\cup_{x\in A}F''_x$ the conditions $F'\supset F'', B\subset B(F')$ are incompatible, which contradicts the main property of $B$. Otherwise, we can find an $x\in A$ that we can add to $B$, which contradicts the maximality of $B$.

| cite | improve this answer | |

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.