1
$\begingroup$

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$.
  3. $B \notin F$.

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.

$\endgroup$
5
  • $\begingroup$ What does the notation $A \subset n$ mean? $\endgroup$ Commented Oct 4, 2016 at 11:49
  • 1
    $\begingroup$ $A$ is a subset of ${0,...n-1}$. $\endgroup$
    – Alon Navon
    Commented Oct 4, 2016 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$ Commented Oct 4, 2016 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
    Commented Oct 4, 2016 at 14:14
  • $\begingroup$ Add one extra element... Btw, why doesn't your construction provide an element of $F$? $\endgroup$ Commented Oct 4, 2016 at 14:53

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .