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:23456789101112
111 11 11 11 11 1
21 34 56 78 910 11
1 23 68 1012 1416 1820 22
3 14 1015 2128 3645 55
1 3 612 3045 6384 108135 165
2 3 615 3045 6384 108135 165
1 2 3 1230 6090 126168 216270 330
4 1 515 3556 84120 165
1 4 10 2260 140224 336480 660
2 4 12 4590 210336 504720 990
1 2 4 30 90180 420672 10081440 1980
3 4 8 3070 140224 336480 660
1 3 4 30 90210 420672 10081440 1980
2 3 4 30 90210 420672 10081440 1980
1 2 3 4 60 180420 8401344 20162880 3960
5 16 2156 126210 330
1 5 1537 105280 6301050 1650
2 5 22105 230 !560 12602100 3300
1 2 5 60210 4201120 25204200 6600
3 5 3090 280560 12602100 3300
1 3 5 90270 8401680 37806300 9900
2 3 5 90315 8401680 37806300 9900
1 2 3 5 180630 16803360 756012600 19800
4 5 1045 140315 6301050 1650
1 4 5 60180 5601260 25204200 6600
2 4 5 90315 8401890 37806300 9900
1 2 4 5 180630 16803780 756012600 19800
3 4 5 60210 5601260 25204200 6600
1 3 4 5 180630 16803780 756012600 19800
2 3 4 5 180630 16803780 756012600 19800
1 2 3 4 5 3601260 33607560 1512025200 39600
6 1 728 84210 462
1 6 21 58168 5041260 2772
2 6 37 210  12603150 6930
1 2 6 105 420  25206300 13860
3 6 60 210840  4200 9240
1 3 6 210  2520 504012600 27720
2 3 6 180 8402520 504012600 27720
1 2 3 6 420 16805040 1008025200 55440
4 6 45 210560 15753150 6930
1 4 6 210 840  630012600 27720
2 4 6 270 1260  945018900 41580
1 2 4 6 630 2520  1890037800 83160
3 4 6 210 8402520 630012600 27720
1 3 4 6 630 25207560 1890037800 83160
2 3 4 6 630 25207560 1890037800 83160
1 2 3 4 6 1260 504015120 3780075600 166320
5 6 12 63224 6301386 2772
1 5 6 105 315  31506930 13860
2 5 6 210 840  630013860 27720
1 2 5 6 420 1680  1260027720 55440
3 5 6 180 8402520 630013860 27720
1 3 5 6 630 25207560 1890041580 83160
2 3 5 6 630 25207560 1890041580 83160
1 2 3 5 6 1260 504015120 3780083160 166320
4 5 6 90 4201260 31506930 13860
1 4 5 6 420 16805040 1260027720 55440
2 4 5 6 630 25207560 1890041580 83160
1 2 4 5 6 1260 504015120 3780083160 166320
3 4 5 6 420 16805040 1260027720 55440
1 3 4 5 6 1260 504015120 3780083160 166320
2 3 4 5 6 1260 504015120 3780083160 166320
1 2 3 4 5 6 2520 1008030240 75600166320 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.