Pairwise intersecting sets of fixed size

Question

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.

Answer 1

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.

Answer 2

Here's how to make the last part of gowers's proof precise (the idea is from Gábor Simonyi).

You have a complete graph of $M$ vertices covered by $t$ bipartite graphs such that each vertex is in at most $4k-2$ of these graphs. You want to prove that the $M \le 2^{4k-2}$. Now for each bipartite graph and each vertex not in it, you double the vertex and add one to each color class. You have doubled each vertex at least $t-4k+2$ times so you now have at least $2^{t-4k}$ vertexes. Every vertex is in every bipartite graph, and still every vertex is joined to every other one with an edge in at least one bipartite graph, so there can't be more than $2^tM$ vertexes, or else there would be two vertexes that was on the same class in each bipartite graph. Thus, $M \le 2^{4k-2}$.

Update: fixed typos in formulas.

Update: my numbers were still off, I marked the updates. The estimate we get is not $ M \le 2^{2k} $ but $ M \le 2^{4k-2} $ thus $ N \le 2k\cdot 2^{4k-2} $. The reason is that once we replace the cliques $ K_i $ with $ L_i, M_i $, each vertex $ x_j $ or $ y_j $ will be in at most $ 2k-1 $ cliques, so in the new complete graph every vertex is in at most $ 4k-2 $ bipartite graphs.

Answer 3

Two other users and myself independently came up with a flawed proof of your lemma using the Δ-System Lemma. While this is not a viable way to prove your result, it does give some intuitive picture of what such families C look like. Δ-systems were first studied by Erdős and Rado (Intersection theorems for systems of sets, I, II, III). A more recent paper on the topic is Deuber, Erdős, Gunderson, Kostochka, Meyer, Intersection statements for systems of sets, J. Combin. Theory Ser. A 79 (1997), 118--132. MR1449752

One way to emphasize the independence on the size of the family C is to state the lemma without the implicit assumption that C is finite. Indeed, an application of the Compactness Theorem shows that the existence of the N(k) in your Lemma 1 is equivalent to the fact that:

For every (possibly infinite) family C of k-element sets with pairwise nonempty intersection there is a finite set A such that any two elements of C intersect in A.

One deduces the existence of N(k) from this fact in the same way that one deduces the finite Ramsey Theorem from the infinite Ramsey Theorem. Proving the theorem in this way allows you to skip a few lines of proof by avoiding the emphasis that the size of A is independent of C. However, there is little gain in not pointing out the uniform bounds since that gives a (possibly crude) bound on N(k) that the compactness argument does not.

Answer 4

I found out that this is a known problem, and was solved in 1973. The Lovász: Combinatorical problems and exercises actually gives a solution in exercise 13.27. This gives asymptotically better estimates than anything we could derive here.

A generalization (where the sets are required to be s-wise intersecting instead of pairwise) can be found in N. Alon, Z. Füredi: On the Kernel of Intersecting Families, Graphs and Combinatorics 3, 91–94 (1987).

Answer 5

I'm not sure about a simpler proof, because I find your proof quite elegant. I think I can connect the statement to something that is (or was) well-studied. It seems we get an improvement on the bound, but it would be good if someone double-checked the argument.

Let N be the natural numbers. Recall that the Erdős-Rado theory in Ramsey theorem says that, if we color the edges of the complete graph on N by N colors, then we are guaranteed to find an infinite subset S of the vertices such that, restricted to S, the coloring is one of the following. (Here, i < j and k < l are natural numbers in S.)

1. Monochromatic: c(i,j) = c(k,l) for all i,j,k,l;
2. Right-colored: c(i,j) = c(k,l) iff j = l;
3. Left-colored: c(i,j) = c(k,l) iff i = k;
4. Rainbow: c(i,j) =/= c(k,l) for all (i,j)=/=(k,l).

Suppose for a moment that your family C of k-sets is countable, fix an enumeration C(1),C(2),... of it, and make its elements the vertices of a complete countable graph. Color the edge between C(i),C(j) with the set C(i)∩C(j). Use Erdős-Rado to get an infinite subfamily C'(1),C'(2),... where the coloring is one of the above. We consider the cases.

1. C' can't be a rainbow, since from each vertex C'(i) there emanate at most 2^k. Our coloring is "locally finite", if you will.
2. C' can't be left-colored either. Suppose it were; then C'(1) must have the same intersection I with all C'(i) for i>1. Thus I' = C'(2)∩C'(3) must include I, but be different from it, i.e. must be a proper superset of I. Then I' = C'(2)∩C'(i) for all i>2, and I'' = C'(3)∩C'(4) must include I' but be a proper superset. We keep going like this, obtaining a strictly increasing chain I,I',I'',... of intersections. But each has size at most k, a contradiction.
3. We run a similar argument to show that C' can't be right-colored. The observation is basically that the argument in item 2 runs into a contradiction in at most k steps, so instead of starting with C'(1) and going forwards, we start with C'(k+1) and go backwards.
4. The trickiest case is when C' is monochromatic, which as we saw is the only possibility. This means that C'(i)∩C'(j) is the same set I for all i=/=j. (Note that I has at most k-1 elements.) This doesn't solve the problem because there might be members of C that are left out of C', but, as we will see, monochromaticity puts a serious restiction on them.

First, note that every k-set B in C has to intersect I, otherwise B would have to intersect the infinite pairwise disjoint family C'(i)\I. Next we break C up into q = 2^k-1 equivalence classes, each labelled by a nonempty subset of I. We put each k-set B in the class labelled B∩I. We will denote members of a class labelled I' ⊆ I by I'(1),I'(2),...

For all disjoint I',I'' ⊆ I, if the classes labelled I',I'' are both nonempty, then they have at most k-1 elements each: for if I'(1),...,I'(k) were in class I' and I''(1) in class I'', then I''(1)\I would intersect each member of the pairwise disjoint family I'(1)\I,...,I'(k)\I; but I''(1)\I has at most k-1 elements.

Now we finally construct our desired set, A, as follows. For each pair of disjoint I',I'' ⊆ I such that the classes labelled I',I'' are nonempty, we grab I'(1),...,I'(k-1) and I''(1), and hold on to them. (There might not be that many I'(i); just grab all of them.) Lastly we grab some set that contains I, e.g. a member of C' from item 4.

Now, there are (3^k-2*2^k+1)/2 (unordered) pairs of disjoint nonempty I',I'' ⊆ I; for each of these we hold on to at most k sets. Thus their union, A, has at most k²(3^k-2*2^k+1)/2 elements, and has the property that any two members of the family C intersect at A. Clearly this holds for I'(i),I'(j) in the same class; and if we take I'(i),I''(j) in different classes, either I',I'' intersect, in which case so do I'(i),I''(j); or I',I'' are disjoint. In that case, since I'(i),I''(j) intersect in I'(i), and we made sure to include in A all the I'(1),...,I'(k-1), we're also in good shape. QED?

Assuming the above argument is correct at all, I think it's possible to refine the last bit, after we've constructed I, to maybe come closer to the lower bound that Gowers talks about.