The Erdős-Ko-Rado theorem talks about how large an intersecting set system (a set of pairwise intersecting sets) can be if the size of the base set is fixed. I'm interested about intersecting set systems where the base set is not fixed, but the size of the sets is bounded. I can prove the following lemma (see proof below).


**Lemma 1.** For every natural number $k$ there is a natural number $N(k)$ such that for every set $C$ each of whose elements are sets of size at most $k$, if every two element of $C$ has a common member, then there is a kernel $A$ which is a set of size at most $N$ so that every two element of $C$ also has a common member that's in $A$. 


I'd like to know if this lemma is known in some literature, and whether you can give me a simpler proof for it than mine. 


I'd also like to know what bound you can give on $N(k)$. An exact bound is probably hard and not too interesting, but I'd like to get the order of magnitude, say whether you can make $N(k)$ a polynomial of $k$. My proof only gives $N(k) = 2^{O(k^2)}$, so anything with a smaller order of magnitude would be nice. (I know that $N(k)$ has to be $\Omega(k^2)$. You can show this by chosing a prime $q$ between $k/2-1$ and $k-1$ and then letting $C$ be the set of lines of a finite projective plane of order $q$.)


There's also a strengthening of the lemma, which follows easily from my proof and can be useful.


**Lemma 2.** For every natural number $k$ there is a natural number $N^{\ast}(k)$ such that for every set $C$ each of whose elements are sets of size at most $k$, if every two element of $C$ has a common member, then there is a kernel $A$ which is a set of size at most $N^{\ast}$ so that if $Y \in C$ and $X$ is a set that intersects every element of $C$ *and $X$ has at most $k$ elements* then $X \cap Y \cap A$ is nonempty.


**Update:** the original phrasing of lemma 2 was wrong, I added the condition that $|X|\le k$.


I'm asking the same questions as above for this stronger version, and also whether it follows easily from the first lemma. 


**Proof** of lemma 1. 


Fix $k$. We will use induction on $p$ to show the existence of a set $A\_p$ such that the size of $A\_p$ is bounded by a constant natural number depending only on $k$ and $p$ (but not $C$), and that for every $X \in C$ either $p \le |X \cap A\_p|$ or the intersection $X \cap Y \cap A\_p$ is non-empty for every $Y\in C$. This is enough because $A = A\_{p+1}$ satisfies the conditions of the lemma (in fact even $A = A\_p$ would work). The case of $p = 0$ is trivial, because $A\_0$ can be the empty set.


Now suppose we have found $A\_p$ and we want to construct $A\_{p+1}$. Now sort the elements of $C$ in equivalence classes such that two element is equivalent if their intersection with $A\_p$ is equal. There are at most as many such classes as subsets of $A\_p$ (or even subsets with at most $k$ elements), which is a constant bound because the size of $A\_p$ is bounded by a constant. Now chose a single element from each equivalence class and let $B$ be the set of these elements. Let $A\_{p+1} := A\_p \cup \bigcup\_{Y\in B} Y$. 


Thus all we have to prove is that for every $X \in C$ either $X \cap A\_{p+1}$ has at least $p+1$ elements or it intersects every element of $C$. From the induction hypothesis we know that $X \cap A\_p$ either has at least $p$ elements or intersects with every element of $C$. If it's the latter, we're done, because $X \cap A\_{p+1}$ is a superset of $X \cap A\_p$, so let's now assume the former: $X \cap A\_p$ has at least $p$ elements. Now if $X \cap A\_{p+1}$ intersects all elements of $C$ then we're done, so we can also assume that there is a $Z \in C$ such that $X \cap A\_{p+1} \cap Z$ is empty. Now consider the class of $Z$ in the equivalence we defined above, that is, all sets $Y$ for which $Y \cap A\_p = Z \cap A\_p$, and let $Y$ be the representant element we chose from this class for the construction. This means that $Y \in B$ thus $Y \subset A\_{p+1}$. Now $X$ and $Y$ has a common element, say $x$. Now it's not possible that $x \in A\_p$, because by our second assumption $X \cap Y \cap A\_p = X \cap Z \cap A\_p \subset X \cap Z \cap A\_{p+1}$ is empty. But then $X \cap A\_{p+1}$ has the at least $p$ elements of $X \cap A\_p$ from our first assumption (because $A\_p \subset A\_{p+1}$), and the extra element $x$ which is not in $X \cap A\_p$, so it has at least $p + 1$ elements, which completes our proof.



Pairwise intersecting sets of fixed size
This isn't an answer but simply a way of thinking about the question that I quite like. (Later: see below for an attempted proof.)


Let's regard each set in our collection as a vertex of a graph, and let's join two vertices if and only if the corresponding sets intersect. That doesn't sound very interesting, since we are hypothesizing that every pair of sets intersects. But that's fine -- we get the complete graph. The interest comes in what we can say about how the graph is built up. For each point x in the ground set, we can define a clique in the graph: its vertices are all sets from our collection that contain x. This gives us a system of cliques whose union is the whole graph. What else do we know about these cliques? We know that each vertex is contained in exactly k of them. And what do we want to prove? That we can choose N(k) of our cliques that cover the complete graph.


It feels more natural to relax the problem and just insist that each vertex is contained in *at most* k of the cliques. 


In the reverse direction, if we have a bunch of cliques that cover the complete graph, we can associate with each vertex the set of cliques that contain that vertex, and the condition that the sets intersect is precisely the condition that the cliques cover all the edges of the graph. So it's a trivial reformulation, but I find it a helpful alternative picture of what is going on.


Added later: here is an attempt to improve the bound to $k^{Ck}$. I think it works but have not 100% checked.


Take a minimal subcollection S of the cliques that covers the complete graph, and suppose that S contains $N$ cliques.


Because S is minimal, for each clique in S there is some edge contained in just that clique and no other clique from S. Since each vertex is in at most k cliques, no vertex is contained in more than k of these edges. So we can find a collection of at least N/k disjoint edges, each of which is contained in just one clique from S. Let M be the number of edges in this set.


At this point I'm going to be very sketchy. I want to prove that M is at most $k^{Ck}$ by showing that if it's bigger than that, then I'm going to have to have a vertex that's contained in more than k cliques. 


Let the M disjoint edges be called $x\_1y\_1,...,x\_My\_M$, and let $K\_i$ be the clique that contains $x\_i$ and $y\_i$. Let's from two cliques $L\_i$ and $M\_i$ from $K\_i$, one obtained by removing $x\_i$ and one by removing $y\_i$. Then between them $L\_i$ and $M\_i$ cover all the edges that $K\_i$ covers, apart from the edge $x\_iy\_i$. So we'll be done if we can show that some vertex has to be contained in more than 2k of the cliques $L\_i$ and $M\_i$, together with other cliques that don't contain any of the edges $x\_iy\_i$.


So our assumption now is that we have a bunch of cliques, and for each i no clique contains both $x\_i$ and $y\_i$, and yet all other pairs $x\_iy\_j$ or $y\_ix\_j$ are joined in at least one of the cliques. We want to show that some vertex is contained in at least 2k cliques.


In particular for each i and j (not equal) we must have a clique that joins $x\_i$ to $y\_j$ or $y\_i$ to $x\_j$ (since in fact we must do both). But no clique ever contains both $x\_i$ and $y\_i$ or both $x\_j$ and $y\_j$. 


Given any clique $K$ from the new collection, the set of pairs ij such that $K$ joins $x\_i$ to $y\_j$ or $y\_i$ to $x\_j$ is a bipartite graph. (Its vertex sets are the set of i such that $K$ contains $x\_i$ and the set of i such that $K$ contains $y\_i$.) So we would like to cover a complete graph with M vertices with bipartite graphs, in such a way that no vertex is contained in more than 2k of those bipartite graphs.


An averaging argument (this is the sketchy bit) should show that we can discount bipartite graphs with a vertex set that is smaller than cM/k, since they do not contribute enough to the average degree. But if we just use bipartite graphs with vertex sets of size at least cM/k, then we can use the following standard argument. Let $X\_1$ be one of the vertex sets of the first bipartite graph. Then none of the edges inside $X\_1$ are covered. So by induction we know that the number of vertices in $X\_1$ is at most M(k-1) (where the M that we are trying to bound is M(k)). But it's also at least cM(k)/k, so we get a bound of $(k/c)^k$ for M.


Added yet later: I think I may be able to use similar ideas to prove a lower bound. Take $2^k$ pairs $x\_sy\_s$, where each s is a vertex of the discrete k-dimensional cube. For each i between 1 and k form a clique by joining every $x\_s$ such that $s\_i=0$ to every $y\_s$ such that $s\_i=1$, and also the other way round. Then for every s not equal to t we cover both the edges $x\_sy\_t$ and $x\_ty\_s$. Also, we never cover the edge $x\_sy\_s$, and the number of cliques is 2k. One more thing ... each vertex is contained in precisely 2k cliques so far. We now add in all the cliques of size 2 with vertex sets $x\_s,y\_s$. So now each vertex is in precisely 2k+1 cliques. So we have a minimal system of at least $2^k$ cliques, with each vertex in 2k+1 of them. Thus, the bound for the original problem (if my reasoning is correct) is at least exponential.


