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).
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?
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.
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.
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.