# Erdős-Ko-Rado / Kneser - type problems

The Erdős-Ko-Rado theorem says that a collection of pairwise intersecting k-subsets of an n-set, where n ≥ 2k, has size at most (n–1 choose k–1) (for k > 0; the case k=0 is left to the reader). Equality holds when one takes all k-sets on a fixed point, and if n = 2k also if one takes all k-sets missing a fixed point, or indeed any collection of k-sets that contains precisely one of every complementary pair.

The Kneser graph K(n,k) is the graph on the k-subsets of an n-set, adjacent when they are disjoint. Thus, e.g., the Petersen graph is K(5,2). Now a way of stating the Erdős-Ko-Rado theorem is that the maximum size of a coclique (independent set) in K(n,k) is (n–1 choose k–1).

## Vector space analogue

Instead of sets, one can use vector spaces over GF(q). Let the q-Kneser graph qK(n,k) be the graph on the k-subspaces of an n-space, adjacent when they meet trivially (i.e., have only 0 in common). Then the Frankl-Wilson theorem says that the maximum size of a coclique in qK(n,k) is the q-binomial coefficient [n–1 choose k–1]q. Equality holds when one takes all k-spaces on a fixed 1-space and if n = 2k also if one takes all k-spaces in a fixed hyperplane.

## Point-hyperplane flags

Now consider the Kneser graph defined on the (point,hyperplane) flags in a projective space PG(n–1,q), adjacent when they are as far from each other as possible. That is, (P,H) ~ (P',H') when P ⊈ H' and P' ⊈ H. (A flag is a collection of subspaces, totally ordered by inclusion. So, here the flags are pairs (P,H) with P ⊆ H.)
Blokhuis-Brouwer-Güven showed that the maximum size of a coclique in this case is 1 + 2q + 3q2 + ... + (n–1)qn–2. The unique example reaching this bound is found by taking a maximal flag (U1,...,Un–1) (consisting of a point, a line, a plane, ..., a hyperplane, totally ordered by inclusion) and then all pairs (P,H) such that there is an i for which P ⊆ Ui ⊆ H.

## Thin analogue

Go back to the "thin" case, the case "q=1", the case of sets instead of vector spaces. The thin analogue of the previous is the graph on pairs (P,H) where P is a 1-set and H an (n–1)-set in an n-set, adjacent when far apart. It is easiest to indicate an (n–1)-set by giving the missing point, so the equivalent question is how many ordered pairs (p,h) of distinct elements we can find in an n-set under the condition that if we take both (p,h) and (p',h') then not (p=h' and p'=h). Clearly the answer is n(n–1)/2, and that is indeed what one gets from the above formula for q=1.

## More general flags of sets

The above was about the problem n:1,n–1, that is about collections of flags (a flag is a collection of subsets, totally ordered by inclusion) consisting of a 1-set and an (n–1)-set, all inside an n-set.

More generally one can look at the problem n:w1,...,wr which is about flags each consisting of a w1-subset, a ..., and a wr-subset of a fixed n-set, where the question is to find the maximum size of a collection of such flags, mutually not far (cf. below). This problem has a flavour very different from the foregoing ones. Earlier it was easy to conjecture the right answer, and difficult to prove that that indeed is the answer. Here the problem is so general, that the first unsolved problem is to conjecture what the answer should be. Also conjectured answers for subcases are of interest.

A table with answers for small cases:

 Color scheme bipartite complement Erdős-Ko-Rado irrelevant part weights 1,n–2 #(2m+1:i,m+1), #(2m:1,m+1)

 n: 2 3 4 5 6 7 8 9 10 11 12 1 1 1 1 1 1 1 1 1 1 1 1 2 1 3 4 5 6 7 8 9 10 11 1 2 3 6 8 10 12 14 16 18 20 22 3 1 4 10 15 21 28 36 45 55 1 3 6 12 30 45 63 84 108 135 165 2 3 6 15 30 45 63 84 108 135 165 1 2 3 12 30 60 90 126 168 216 270 330 4 1 5 15 35 56 84 120 165 1 4 10 22 60 140 224 336 480 660 2 4 12 45 90 210 336 504 720 990 1 2 4 30 90 180 420 672 1008 1440 1980 3 4 8 30 70 140 224 336 480 660 1 3 4 30 90 210 420 672 1008 1440 1980 2 3 4 30 90 210 420 672 1008 1440 1980 1 2 3 4 60 180 420 840 1344 2016 2880 3960 5 1 6 21 56 126 210 330 1 5 15 37 105 280 630 1050 1650 2 5 22 105 230 ! 560 1260 2100 3300 1 2 5 60 210 420 1120 2520 4200 6600 3 5 30 90 280 560 1260 2100 3300 1 3 5 90 270 840 1680 3780 6300 9900 2 3 5 90 315 840 1680 3780 6300 9900 1 2 3 5 180 630 1680 3360 7560 12600 19800 4 5 10 45 140 315 630 1050 1650 1 4 5 60 180 560 1260 2520 4200 6600 2 4 5 90 315 840 1890 3780 6300 9900 1 2 4 5 180 630 1680 3780 7560 12600 19800 3 4 5 60 210 560 1260 2520 4200 6600 1 3 4 5 180 630 1680 3780 7560 12600 19800 2 3 4 5 180 630 1680 3780 7560 12600 19800 1 2 3 4 5 360 1260 3360 7560 15120 25200 39600 6 1 7 28 84 210 462 1 6 21 58 168 504 1260 2772 2 6 37 210 1260 3150 6930 1 2 6 105 420 2520 6300 13860 3 6 60 210 840 4200 9240 1 3 6 210 2520 5040 12600 27720 2 3 6 180 840 2520 5040 12600 27720 1 2 3 6 420 1680 5040 10080 25200 55440 4 6 45 210 560 1575 3150 6930 1 4 6 210 840 6300 12600 27720 2 4 6 270 1260 9450 18900 41580 1 2 4 6 630 2520 18900 37800 83160 3 4 6 210 840 2520 6300 12600 27720 1 3 4 6 630 2520 7560 18900 37800 83160 2 3 4 6 630 2520 7560 18900 37800 83160 1 2 3 4 6 1260 5040 15120 37800 75600 166320 5 6 12 63 224 630 1386 2772 1 5 6 105 315 3150 6930 13860 2 5 6 210 840 6300 13860 27720 1 2 5 6 420 1680 12600 27720 55440 3 5 6 180 840 2520 6300 13860 27720 1 3 5 6 630 2520 7560 18900 41580 83160 2 3 5 6 630 2520 7560 18900 41580 83160 1 2 3 5 6 1260 5040 15120 37800 83160 166320 4 5 6 90 420 1260 3150 6930 13860 1 4 5 6 420 1680 5040 12600 27720 55440 2 4 5 6 630 2520 7560 18900 41580 83160 1 2 4 5 6 1260 5040 15120 37800 83160 166320 3 4 5 6 420 1680 5040 12600 27720 55440 1 3 4 5 6 1260 5040 15120 37800 83160 166320 2 3 4 5 6 1260 5040 15120 37800 83160 166320 1 2 3 4 5 6 2520 10080 30240 75600 166320 332640

Complements: n:w1,...,wr is isomorphic to n:n–wr,...,n–w1.

Erdős-Ko-Rado: n:w with n ≥ 2w has max size (n–1 choose w–1).

Permutations: n:1,2,...,n–1 has max size n!/2. More generally, if w is symmetric (wi = wr+1–i for all i) then the Kneser graph has valency 1 and max size is half the total number of objects. More generally, if there is an i with wi = wr+1–i (the middle node or a pair of symmetric nodes), then the Kneser graph is bipartite, and again the max coclique size is half the total number of vertices.

Irrelevant parts: if n ≥ wi+wr then in flags that are far apart the wi-sets of one are disjoint from all sets in the other, and therefore also the wj-sets with j < i. Now wi–1 just contributes a factor (wi choose wi–1).

The use of these rules is shown with colors in the table. Some more information is given in the examples below. The fields with white background are unknown or require other methods. One fairly successful method is the fractional covering method.

Desired: expression as sum over the Weyl group W.

Of course one can ask many other questions about these graphs. An easy one: when are they connected? and more generally: how many connected components are there?

## Far

What is far? In the set case for n:w1,...,wr two flags (A1,...,Ar) and (B1,...,Br), where |Ai| = |Bi| = wi, are far when |Ai ∩ Bj| ≤ max(0,wi+wj–n) for every pair i,j. That is, when all intersections are as small as is possible inside an n-set. (This can also be expressed as: either Ai and Bj are disjoint, or their complements are disjoint.)

The condition for vector spaces is just like this, but with dimension instead of size of the intersections.

The general case is that of a Coxeter group or group of Lie type. Relations between flags are parametrised by double cosets XwX with w ∈ W and X a parabolic subgroup of W. Two flags are far when this double coset contains w0, the longest element of W.

## Folding

The collection of cocliques in the Kneser graph is invariant under foldings. Let us describe the thin case.

Let N be the underlying set {1,2,...,n}. The simple folding j ↦ i on N is the idempotent map φ defined on N (and then on subsets of N, flags on N, collections of flags of N) by φ(j) = i and φ(x) = x for x ≠ j.

This map induces a folding (idempotent map with preimages of size at most 2) on the power set of N, also denoted φ, via

φ(A) = { x | x ∈ A and φ(x) ∈ A } ∪ { φ(x) | x ∈ A and φ(x) ∉ A }.
This map preserves cardinalities and inclusion. Therefore, it maps flags to flags, and also as a map on flags it is idempotent with preimages of size at most 2.

This map again induces a cardinality-preserving map on the collection of all cocliques, via

φ(C) = { F | F ∈ C and φ(F) ∈ C } ∪ { φ(F) | F ∈ C and φ(F) ∉ C }.

If C is a coclique in the Kneser graph, then φ(C) is a coclique, too. Indeed, if φ(C) contains flags that are far and C does not, then there are flags F,F' ∈ C with φ(F),F' ∈ φ(C) where φ(F),F' are far. (Because on the level of sets φ can only decrease distances and increase intersection sizes). But F' ∈ φ(C) means that C already contains φ(F'). For each A ∈ F and B ∈ F' such that A and B are not far we see that φ(A) and B are far, so φ has diminished the intersection, and both A and B do contain j but not i. But then also A and φ(B) are far. It follows that F and φ(F') are far, but both are in C, contradiction.

Now we can apply foldings and shift a coclique to a lexicographically minimal form: if there exists a coclique C of a certain size, then there also exists a coclique of this same size that is invariant for all foldings j ↦ i where i < j.

## Examples

Proposition #(n:1,n–2) = 2 + (n choose 3) for n ≥ 4.

Proof: For n=4 this is a bipartite case. For n > 4 we show #(n:1,n–2) = (n–1 choose 2) + #(n–1:1,n–3) and then the result follows by induction.

First of all, #(n:1,n–2) ≥ (n–1 choose 2) + #(n–1:1,n–3), since one can take any (n–1:1,n–3) example, shift it by 1 so as to use the digits 2..n instead of 1..(n–1), add the element 1 to the (n–3)-set in all of its flags and add as new flags all (n–1 choose 2) flags containing {1}. This is a coclique of the required size.

Conversely, let C be a coclique of maximal size closed for all foldings j ↦ i where i < j.

If C contains all (n–1 choose 2) flags containing {1}, then every other flag in C must have a 1 in its (n–2)-set (otherwise we can find two adjacent flags in C), and C arises as sketched and has the claimed size.

If C does not contain all flags containing {1}, then (1,145..n) is missing. Simplify notation and write the complement of the (n–2)-set, so that (1,145..n) is now called (1;23). (When we write (a;bc) then it is understood that a,b,c are distinct.) Pick C of maximum size, and given that size with maximum number of flags containing {1}.

If (h;1i) ∈ C then also (1;jn) ∈ C, since we can shift (h;1i) down to (1;jn).

Suppose (1;ab) ∉ C. Since C is maximal, we cannot add (1;ab) and it must conflict with at least two flags (a;1i) or (b;1i) in C. But then (1;jn) ∈ C for all j (1 < j < n), and in particular a,b < n. Since no two flags in C are far, and we can take j=a or j=b, we must have i=n, and we see that (1;ab) ∉ C implies that (a;1n), (b;1n) ∈ C.

On the other hand, (a;1n) ∈ C implies (1;ac) ∉ C for all c ≠ 1,a,n. It follows that if (1;ab) ∉ C for some a,b, then (1;ab) ∉ C for all a,b with 1 < a,b < n. That is (n–2 choose 2) missing elements. The possibly conflicting elements that are present are of the form (a;1n), and there are at most n–2 of those. Since n > 4 we can remove all flags (a;1n) and add all flags (1;ab) without decreasing the size of C. Contradiction. QED

Conjecture #(n:2,n–3) = 6 + 4(n choose 5) for n ≥ 6.

Conjecture #(n:3,n–4) = 20 + 15(n choose 7) for n ≥ 8.

Conjecture #(n:i,n–1–i) = (2i choose i) + (2i choose i–1)(n choose 2i+1) for n ≥ 2(i+1).

Using fractional covering one finds

Proposition #(2m+1:i,m+1) = mv/(2m+1) where v is the total number of vertices, and 1 ≤ i ≤ m–1.

Proposition #(2m:1,m+1) = (m–1)v/2m.