3 fix phrasing of lemma 2

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.

2 edited tags
1

Pairwise intersecting sets of fixed size

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$ then $X \cap Y \cap A$ is nonempty.

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.