# Unavoidable finite set for infinite k-intersecting family?

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?

• What does the notation $A \subset n$ mean? – Joseph O'Rourke Oct 4 '16 at 11:49
• $A$ is a subset of ${0,...n-1}$. – Alon Navon Oct 4 '16 at 11:50
• Can't we just choose some element of $F$ in place of $B$? It meets every element in $F$ and has just $k$ elements... – Ilya Bogdanov Oct 4 '16 at 13:43
• @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$. – Alon Navon Oct 4 '16 at 14:14
• Add one extra element... Btw, why doesn't your construction provide an element of $F$? – 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$.