# Erdős-Ko-Rado sets of flags of finite sets

Klaus Metsch Justus-Liebig-Universität, Mathematisches Institut, Arndtstraße
2, D-35392 Gießen

###### Abstract

A flag of a finite set $S$ is a set $f$ of non-empty proper subsets of $S$
such that $A\subseteq B$ or $B\subseteq A$ for all $A,B\in f$. The set
$\\{|A|:A\in f\\}$ is called the type of $f$. Two flags $f$ and $f^{\prime}$
are in general position (with respect to $S$) when $A\cap B=\emptyset$ or
$A\cup B=S$ for all $A\in f$ and $B\in f^{\prime}$. We study sets of flags of
a fixed type $T$ that are mutually not in general position and are interested
in the largest cardinality of these sets. This is a generalization of the
classical Erdős-Ko-Rado problem. We will give some basic facts and determine
the largest cardinality in several non-trivial cases. For this we will define
graphs whose vertices are flags and the problem is to determine the
independence number of these graphs.

Keywords: Erdős-Ko-Rado sets, Kneser graphs, independence number

MSC (2020): 05C69, 05D05, 05C35

##  1 Introduction

For integers $n\geq 0$ we define $[n]:=\\{i\in\mathbb{Z}\mid 1\leq i\leq
n\\}$. Let $S$ be a non-empty finite set. We call two subsets of $S$ in
_general position_ (with respect to $S$) if their union is $S$ or their meet
is empty, which means that their intersection is as small as possible. A
_flag_ of $S$ is set $f$ of non-empty proper subsets of $S$ such that
$X\subseteq Y$ or $Y\subseteq X$ for all $X,Y\in f$. The set $\\{|X|:X\in
f\\}$ is the _type_ of $f$. Two flags $f$ and $f^{\prime}$ of $S$ are in
_general position_ , if $X$ and $X^{\prime}$ are in general position for all
$X\in f$ and all $X^{\prime}\in f^{\prime}$. For $T\subseteq[|S|-1]$ the graph
whose vertices are the flags of $S$ of type $T$ with two vertices being
adjacent when the corresponding flags are in general position will be denoted
by $\Gamma(S,T)$. If $S=[n]$, we use the notation $\Gamma(n,T)$. If $|T|=1$,
these graphs are called _Kneser graphs_.

The $q$-analogs of these graphs are obtained from vector spaces $F_{q}^{n}$ of
dimension $n\geq 2$ where $F_{q}$ is the Galois field of order $q$. A _flag_
of $F_{q}^{n}$ is a set $f$ of subspaces such that $X\subseteq Y$ or
$Y\subseteq X$ for all $X,Y\in f$, and the set $\\{\dim(X)\mid X\in f\\}$ is
the _type_ of $f$. Two flags $f$ and $f^{\prime}$ are in _general position_ ,
if $X+X^{\prime}=F_{q}^{n}$ or $X\cap X^{\prime}=\\{0\\}$ for all $X\in f$ and
$X^{\prime}\in f^{\prime}$. For $T\subseteq[n-1]$, the graph whose vertices
are the flags of type $T$ of $F_{q}^{n}$ with two vertices being adjacent when
the corresponding flags are in general position will be denoted by
$\Gamma_{q}(n,T)$.

In this paper we are interested in the independence number of the graphs
$\Gamma(n,T)$ for $\emptyset\not=T\subseteq[n-1]$. For $|T|=1$ the problem
reduces to the famous Erdős-Ko-Rado problem, which was solved in [2], but up
to my knowledge the problem was not considered for $|T|>1$. In the
$q$-analogue situation, the independence number of the graphs
$\Gamma_{q}(n,T)$ with $|T|=1$ was determined by Frankl and Wilson [3], see
also Hsieh [5] and Newman [6]. However, for the graphs $\Gamma_{q}(n,T)$ also
several results for $|T|>1$ are known, see [1].

For every non-empty subset $T$ of $[n-1]$ the graph $\Gamma(n,T)$ is regular
and non-empty, so its independence number is at most one half of the number of
its vertices with equality if and only if the graph is bipartite. This is
always the case when $T$ contains an element $i$ with $n-i\in T$. If
$\max{T}\leq\frac{n}{2}$ or $\min(T)\geq\frac{n}{2}$, then the independence
number can easily be derived form the above mentioned result of Erdős-Ko-Rado.
Section 2 is devoted to these facts as well as to several other basic facts.

There are pairs $(n,T)$ with $\emptyset\not=T\subseteq[n-1]$ for which it is
to be a non-trivial problem to determine the independence number of
$\Gamma(n,T)$. There are different techniques one might try, for example
techniques that have been successful in the case $|T|=1$. One of the
techniques is to apply the Hoffman bound, but for the cases I have tested,
this bound is too weak when $|T|>1$ (except in some easy cases that are
handled in Section 2 by different methods). One may consider the underlying
coherent configuration and try to obtain a bound by semidefinite programming.
But for the non-tivial cases I have tried this also does not give tight
bounds. Another well-known technique is the cycle method and in fact a variant
of this method will be used to show the first result of the paper. In order to
state it, we denote the set of vertices of a graph $\Gamma$ by $V\Gamma$.

######  Theorem 1.1.

For positive integers $b$ and $n$ and every non-empty subset $T$ of $[n]$ with
$\max(T)+3b\leq 2n<4b$, the independence number of the graph
$\Gamma(n,T\cup\\{b\\})$ is equal to
$\genfrac{(}{)}{0.0pt}{1}{n-1}{b}\cdot|V\Gamma(b,T)|$.

An independent set of this size of $\Gamma(n,T\cup\\{b\\})$ is given by all
flags of type $T\cup\\{b\\}$ whose sets of cardinality $b$ are contained in
$[n-1]$. We remark that for certain $T$, $b$ and $n$ there are non-equivalent
independent sets of the same size. In fact, in Section 3 we construct several
families of independent sets of $\Gamma(n,T)$ when $|T|=2$ and determine which
of these are the largest ones. We will see that there are either one, two or
three non-equivalent independents sets of maximal size among these examples.
In Section 4 we show that these examples are in fact largest independent sets
when $T=\\{a,b\\}$ with $b>\frac{n}{2}$ and $a+3b\leq 2n$. The above theorem
is a corollary of this result. In Section 5 we show in one other case, namely
$T=\\{1,n-2\\}$ that the examples are best possible, which results in the
following theorem.

######  Theorem 1.2.

For $n\geq 5$ the independence number of $\Gamma(n,\\{1,n-2\\})$ is
$\genfrac{(}{)}{0.0pt}{1}{n}{3}+2$ and there exist exactly three non-
equivalent independent sets of this cardinality.

The proof is by induction on $n$ but we prove the induction step $n-1\to n$
only for $n\geq 10$. The induction basis $5\leq n\leq 9$ is verified by
computer. In fact our result is more general, in that it proves an induction
step in a more general setting. However, the proof of the induction basis for
the other cases seems to be out of range for computers. Details are given in
Section 5.

The above theorems combined with the results presented in Section 2 determine
the independence number of all graphs $\Gamma(n,T)$ with $n\leq 6$. Several
open problems will be given in Section 6.

##  2 Basic observations

######  Notation.

  1. 1.

For every positive integer $n$ we denote by $\omega_{n}$ the permutation of
$[n-1]$ with $\omega_{n}(i)=n-i$ for all $i\in[n-1]$. For subsets $T$ of
$[n-1]$, we define $\omega_{n}(T)=\\{\omega_{n}(i)\mid i\in T\\}$.

  2. 2.

For every non-empty finite set $M$ and all sets $S\subseteq T\subseteq[|M|-1]$
we denote by $\operatorname{proj}^{M}_{T,S}$ the map from the set of all flags
of $M$ of type $T$ to the set of all flags of $M$ of type $S$ that maps each
flag $f$ of type $T$ to the flag $\\{A\in f:|A|\in S\\}$. If $M=[n]$, then we
write $\operatorname{proj}^{n}_{T,S}$.

  3. 3.

For each finite graph $\Gamma$ we denote its independence number by
$\alpha(\Gamma)$.

######  Lemma 2.1.

Let $n\geq 2$ be an integer and $\emptyset\not=T\subseteq[n-1]$. Then we have.

  1. (a)

The graph $\Gamma(n,T)$ is regular.

  2. (b)

$\Gamma(n,T)\cong\Gamma(n,\omega_{n}(T))$ _(duality)_.

  3. (c)

$\alpha(\Gamma(n,T))\leq\frac{1}{2}|V\Gamma(n,T)|$ with equality if and only
if $\Gamma(n,T)$ is bipartite.

  4. (d)

If there exist $i,j\in T$ with $i+j=n$, then $\Gamma(n,T)$ is bipartite and
$\alpha(\Gamma(n,T))=\frac{1}{2}|V\Gamma(n,T)|$.

###### Proof.

(a) Since the symmetric group on the set $[n]$ induces a vertex transitive
automorphism group of $\Gamma(n,T)$, this graph is regular.

(b) The map $f\mapsto\\{[n]\setminus A\mid A\in f\\}$ for every flag $f$ of
$[n]$ induces a bijective map $\iota$ from the vertex set of $\Gamma(n,T)$ to
the vertex set of $\Gamma(n,\omega_{n}(T))$. By the laws of DeMorgan two
subsets of $[n]$ are in general position if and only if their complements in
$[n]$ are in general position. Thus two flags of type $T$ are in general
position if and only if their images under $\iota$ are in general position.
Therefore $\iota$ is an isomorphism between the graphs.

(c) This is true for every finite regular non-empty graph.

(d) We remark that we allow that $i=j$. Every flag $f$ of type $\\{i,j\\}$ is
in general position to exactly one flag of type $\\{i,j\\}$, namely
$\\{[n]\setminus A\mid A\in f\\}$. If we take from every such pair one flag,
we obtain a set $X$ consisting of flags of type $\\{i,j\\}$ that are mutually
not in general position. The set consisting of all flags $f$ of type $T$ of
$[n]$ that satisfy $\operatorname{proj}^{n}_{T,\\{i,j\\}}(f)\in X$ has the
property that no two of its flags are in general position and moreover this
set contains $\frac{1}{2}|V\Gamma(n,T)|$ elements. By (c), the graph is
bipartite. ∎

######  Remark 2.2.

If there exists $i\in T$ with $j=n-i\in T$, then $\Gamma(n,T)$ is disconnected
and each component is a complete regular bipartite graph.

######  Lemma 2.3.

Let $S$ and $T$ be distinct non-empty subsets of $[n-1]$ with $S\subseteq T$.

  1. (a)

Let $f_{1}$ and $f_{2}$ be flags of $[n]$ of type $T$. If $f_{1}$ and $f_{2}$
are in general position, then so are $\operatorname{proj}^{n}_{T,S}(f_{1})$
and $\operatorname{proj}^{n}_{T,S}(f_{2})$. In other words,
$\operatorname{proj}^{n}_{T,S}$ is a graph homomorphism from $\Gamma(n,T)$
onto $\Gamma(n,S)$.

  2. (b)

We have

$\displaystyle\alpha(\Gamma(n,T))\geq\alpha(\Gamma(n,S))\cdot\frac{|V\Gamma(n,T))|}{|V\Gamma(n,S)|}.$
(1)

###### Proof.

(a) This follows immediately form the definition of general position.

(b) Let ${\cal F}$ be an independent set of $\Gamma(n,S)$ with $|{\cal
F}|=\alpha(\Gamma(n,S))$. By (a), the preimage $\bar{\cal F}$ of ${\cal F}$
under the map $\operatorname{proj}^{n}_{T,S}$ is an independent set of
$\Gamma(n,T)$. The fraction $v$ in (1) is the common number of preimages of
every vertex of $\Gamma(n,S)$ under the projection map
$\operatorname{proj}^{n}_{T,S}$. Hence $|\bar{\cal
F}|=v\cdot\alpha(\Gamma(n,S))$. ∎

######  Remark 2.4.

In general we do not have equality in (1). For example for $n=6$, $S=\\{4\\}$
and $T=\\{1,4\\}$ we have
$\alpha(\Gamma(n,S))=\genfrac{(}{)}{0.0pt}{1}{5}{4}=5$ and the fraction in (1)
is $4$ whereas we shall see in Theorem 5.10 that $\alpha(\Gamma(n,T))=22$.

Now we present a situation where (1) holds with equality.

######  Proposition 2.5.

Let $S$ and $T$ be distinct non-empty subsets of $[n-1]$ satisfying

$\displaystyle S\subseteq T,\ \min(S)+\max(S)\leq n\ \text{and}\
\max(T\setminus S)<\min(S).$

Then two flags of $\Gamma(n,T)$ are in general position if and only if their
images under $\operatorname{proj}^{n}_{T,S}$ are in general position. In
particular

$\displaystyle\alpha(\Gamma(n,T))=\alpha(\Gamma(n,S))\cdot|V\Gamma(\min
S,T\setminus S)|.$ (2)

###### Proof.

Let $f_{1}$ and $f_{2}$ be flags of $\Gamma(n,T)$ and $g_{1}$ and $g_{2}$
their images under $\operatorname{proj}^{n}_{T,S}$. If $f_{1}$ and $f_{2}$ are
in general position, then so are their images by the previous lemma. Now
assume that $g_{1}$ and $g_{2}$ are in general position. Let $A_{i},B_{i}\in
g_{i}$ with $|A_{i}|=\min(S)$ and $|B_{i}|=\max(S)=\max(T)$. Since
$\min(S)+\max(S)\leq n$ and since $g_{1}$ and $g_{2}$ are in general position
we have $A_{1}\cap B_{2}=\emptyset$. If $C_{1}\in f_{1}\setminus g_{1}$, then
$C_{1}\subseteq A_{1}$, so $C_{1}\cap B_{2}=\emptyset$ and hence $C_{1}\cap
C=\emptyset$ for all $C\in f_{2}$. Similarly $C_{2}\cap C=\emptyset$ for all
$C_{2}\in f_{2}\setminus g_{2}$ and all $C\in f_{1}$. Therefore $f_{1}$ and
$f_{2}$ are in general position.

Since $\max(T\setminus S)<\min(S)$, every vertex of $\Gamma(n,S)$ is the image
of exactly $v:=|V\Gamma(\min(S),T\setminus S)|$ vertices of $\Gamma(n,T)$
under the map $\operatorname{proj}^{n}_{T,S}$. Therefore the $\geq$-part in
(2) follows from the previous lemma. On the other hand, if ${\cal F}$ is an
independent set of $\Gamma(n,T)$, then the first statement of the present
lemma shows that $\operatorname{proj}^{n}_{T,S}({\cal F})$ is an independent
set of $\Gamma(n,S)$. Since $|{\cal F}|\leq
v\cdot|\operatorname{proj}^{n}_{T,S}({\cal F})|$, this proves the $\leq$-part
of (1). ∎

######  Remarks 2.6.

  1. 1.

The proof also shows that every largest independent set of $\Gamma(n,T)$ is
the preimage of a largest independent set of $\Gamma(n,S)$.

  2. 2.

Using Lemma 2.1 (b), the result of Proposition 2.5 can be dualized. Similarly,
the next result can be dualized to the situation when
$\min(T)\geq\frac{n}{2}$.

######  Corollary 2.7.

Consider $1<n\in\mathbb{Z}$ and $\emptyset\not=T\subseteq[n-1]$ with
$t:=\max(T)\leq\frac{1}{2}n$. Then
$\alpha(\Gamma(n,T))=\genfrac{(}{)}{0.0pt}{1}{n-1}{t-1}\cdot|V\Gamma(t,T\setminus\\{t\\})|$.

###### Proof.

This results is the classical result of Erdős-Ko-Rado [2] when $T=\\{t\\}$; in
this case $\Gamma(t,T\setminus\\{t\\})$ is the empty graph with one vertex.
Otherwise the corollary follows from the proposition using
$S=T\setminus\\{t\\}$ and again the Erdős-Ko-Rado result. ∎

######  Remark 2.8.

The results of 2.1, 2.5 and 2.7 cover quite some of the possible types. We
list the open cases for $2\leq n\leq 8$ up to duality. For $n\leq 4$, there is
no open case. For $n=5$ this is only $\\{1,3\\}$. For $n=6$, this is
$\\{1,4\\}$. For $n=7$, these are $\\{1,4\\}$, $\\{1,5\\}$, $\\{2,4\\}$,
$\\{1,2,4\\}$, $\\{1,3,5\\}$ and $\\{1,4,5\\}$. For $n=8$, these are
$\\{1,5\\}$, $\\{1,6\\}$, $\\{2,5\\}$, $\\{1,2,5\\}$, $\\{1,3,6\\}$ and
$\\{1,5,6\\}$. Some of these cases will be handled in Sections 4 and 5.

######  Remark 2.9.

The results in this section determine the independence number of $\Gamma(n,T)$
in all cases in which the independence number for the graphs $\Gamma_{q}(n,T)$
is known.

##  3 Examples

In this section we study examples of independent sets of the graphs
$\Gamma(n,\\{a,b\\})$ with $a<b$. Since the case
$\max\\{a,b\\}\leq\frac{n}{2}$ and the dual case
$\min\\{a,b\\}\geq\frac{n}{2}$ have been treated in Corollary 2.7, we assume
that $a<\frac{n}{2}<b$. The case $a+b=n$ has been treated in Lemma 2.1 (d), so
that we can assume $a+b\not=n$. In view of Lemma 2.1 (b) we will restrict
ourselves therefore to the situation when $a+b<n$. For simplicity a flag
$\\{A,B\\}$ of type $\\{a,b\\}$ will mostly be written as an ordered pair
$(A,B)$ with $|A|=a$ and $|B|=b$. Recall that $[0]=\emptyset$.

######  Example 3.1.

Let $n$, $a$ and $b$ be positive integers with $a<\frac{n}{2}<b$ and $a+b<n$.
For every integer $i$ with $0\leq i\leq 2b-n+1$ we denote by ${\cal
F}_{i}(n,a,b)$ the set of all vertices $(A,B)$ of $\Gamma(n,\\{a,b\\})$ that
fulfill at least one of the following conditions.

  * (I)

$[i]\subseteq B\subseteq[n-1]$,

  * (II)

$\min A\leq i$ and $[\min A]\subseteq B$.

For $i=2b-n+1$, let $\bar{\cal F}_{i}(n,a,b)$ be the set of all vertices
$(A,B)$ of $\Gamma(n,\\{a,b\\})$ that satisfy $[i]\subseteq B$ or (II); hence
${\cal F}_{i}(n,a,b)\subseteq\bar{\cal F}_{i}(n,a,b)$.

######  Lemma 3.2.

Let $n,a,b$ be positive integers with $a+b<n$ and $b>\frac{n}{2}$.

  1. (a)

For $0\leq i\leq 2b-n$ the set ${\cal F}_{i}(n,a,b)$ is a maximal independent
set of $\Gamma(n,\\{a,b\\})$.

  2. (b)

For $i=2b-n+1$, the set $\bar{\cal F}_{i}(n,a,b)$ is a maximal independent set
of $\Gamma(n,\\{a,b\\})$ and it is the only maximal independent that contains
${\cal F}_{i}(n,a,b)$. Moreover $|\bar{\cal F}_{i}\setminus{\cal
F}_{i}|+\genfrac{(}{)}{0.0pt}{1}{2s-2}{s-2}\genfrac{(}{)}{0.0pt}{1}{s-1}{a}$
where $s=n-b$.

###### Proof.

We put ${\cal F}_{i}={\cal F}_{i}(n,a,b)$. It is easy to see that all sets in
question are independent sets. To investigate maximality we consider the
situation that there exists an integer $i$ with $0\leq i\leq 2b-n+1$ and a
flag $(A,B)$ such that $(A,B)\notin{\cal F}_{i}(n,a,b)$ and ${\cal
F}_{i}\cup\\{(A,B)\\}$ is independent. We have to show that $i=2b-n+1$ and
$(A,B)\in\bar{\cal F}_{i}(n,a,b)$.

First we want to show that $[i]\subseteq B$. Assume the contrary. Then there
exists a positive integer $j\leq i$ with $[j-1]\subseteq B$ and $j\notin B$.
Since $(A,B)\notin{\cal F}_{i}$, then $\min(A)>j-1$ and hence $\min(A)\geq
j+1$. We have $|B\setminus[j-1]|\geq|B|-(i-1)=b+1-i\geq n-b$. Hence there
exists a subset $T$ of cardinality $n-b$ of $[n]$ with $A\subseteq T\subseteq
B\setminus[j-1]$. Put $B^{\prime}:=[n]\setminus T$. Then $B\cup
B^{\prime}=[n]$ and $|B^{\prime}\setminus B|=n-b\geq a$. Chose
$A^{\prime}\subseteq B^{\prime}\setminus B$ with $|A^{\prime}|=a$ and $j\in
A^{\prime}$. Then $(A,B)$ and $(A^{\prime},B^{\prime})$ are in general
position. Since $\min(A^{\prime})=j$ and $[j]\subseteq B^{\prime}$ we have
$(A^{\prime},B^{\prime})\in{\cal F}_{i}$. But ${\cal F}_{i}\cup\\{(A,B)\\}$ is
independent, contradiction.

Therefore $[i]\subseteq B$. Since $(A,B)\notin{\cal F}_{i}$, then $\min(A)>i$
and $n\in B$. We want to show that $i=2b+1-n$. Assume on the contrary that
$i\leq 2b-n$. Then $|B\setminus[i]|=b-i\geq n-b$. As $a<n-b$, we thus find a
subset $T$ of $B\setminus[i]$ with $A\cup\\{n\\}\subseteq T$ and $|T|=n-b$.
Put $B^{\prime}:=[n]\setminus T$. Then $B\cup B^{\prime}=[n]$ and
$|B^{\prime}\setminus B|=n-b\geq a$. Chose $A^{\prime}\subseteq
B^{\prime}\setminus B$ with $|A^{\prime}|=a$. Then $(A,B)$ and
$(A^{\prime},B^{\prime})$ are in general position. Since $[i]\subseteq
B^{\prime}\subseteq[n-1]$ we have $(A^{\prime},B^{\prime})\in{\cal F}_{i}$.
But ${\cal F}_{i}\cup\\{(A,B)\\}$ is independent, contradiction.

Hence $i=2b+1-n$. This proves (a). We have moreover shown that every flag
$(A,B)$ that is not in ${\cal F}_{i}$ and such that ${\cal
F}_{i}\cup\\{(A,B)\\}$ is independent satisfies $[i]\subseteq B$ and hence
$(A,B)\in\bar{\cal F}_{i}(n,a,b)$. This is the first part of (b). Since the
elements $(A,B)$ of $\bar{\cal F}_{i}(n,a,b)\setminus{\cal F}_{i}(n,a,b)$ are
the flags with $[i]\cup\\{n\\}\subseteq B$ and $\min(A)\geq i+1$, we see that
there exists
$\genfrac{(}{)}{0.0pt}{1}{n-i-1}{b-i-1}\cdot\genfrac{(}{)}{0.0pt}{1}{b-i}{a}$
such flags. ∎

######  Lemma 3.3.

Let $n,a,b$ be positive integers with $a+b<n$ and $b>\frac{n}{2}$. For $0\leq
i\leq 2b-n+1$, the cardinality of ${\cal F}_{i}(n,a,b)$ is

$\displaystyle\binom{n-1-i}{b-i}\binom{b-i}{a}+\binom{n-b+a-1}{a-1}\left(\binom{n}{b-a}-\binom{n-i}{b-a-i}\right).$

Moreover, with

$\displaystyle i_{0}:=b-1-\frac{(n-b)(n-b-1)}{a}$ (3)

we have the following. If $i_{0}<0$, then the largest cardinality occurs only
for $i=0$. If $i_{0}\geq 0$ is an integer, then the largest cardinality occurs
for $i\in\\{i_{0},i_{0}+1\\}$. If $i_{0}\geq 0$ but $i_{0}$ is not an integer,
then the largest cardinality occurs only for $i=\lceil i_{0}\rceil$.

###### Proof.

First notice that the condition $a+b<n$ implies that $i_{0}\leq 2b-n-1$. The
number of flags satisfying only the first condition of Example 3.1 is
$\genfrac{(}{)}{0.0pt}{1}{n-1-i}{b-i}\genfrac{(}{)}{0.0pt}{1}{b-i}{a}$. With
the notation $j:=\min(A)$ in the second condition of Example 3.1 we find

$\displaystyle|{\cal F}_{i}(n,a,b)|$
$\displaystyle=\binom{n-1-i}{b-i}\binom{b-i}{a}+\sum_{j=1}^{i}\binom{n-j}{a-1}\binom{n-a-j+1}{b-a-j+1}$
$\displaystyle=\binom{n-1-i}{b-i}\binom{b-i}{a}+\sum_{j=1}^{i}\binom{n-b+a-1}{n-b}\binom{n-j}{n-b+a-1}$
$\displaystyle=\binom{n-1-i}{b-i}\binom{b-i}{a}+\binom{n-b+a-1}{a-1}\left(\binom{n}{b-a}-\binom{n-i}{b-a-i}\right)$

This proves the formula for ${\cal F}_{i}(n,a,b)$. We also find

$\displaystyle|{\cal
F}_{i}(n,a,b)|=\binom{n-b+a-1}{a-1}\binom{n}{b-a}+\frac{((n-b)^{2}+a(i-b))(n-1-i)!}{(n-b+a)a!(n-b)!(b-i-a)!}.$
(4)

Using this, an easy calculation shows that $|{\cal F}_{i+1}|\geq|{\cal
F}_{i}|$ if and only if $i\leq i_{0}$ and that $|{\cal F}_{i+1}|=|{\cal
F}_{i}|$ if and only if $i=i_{0}$. This implies the second statement of the
lemma. ∎

Definition. We call two independent sets of a graph _equivalent_ , if the are
in the same orbit under the automorphism group of the graph.

######  Proposition 3.4.

With $a,b,n$ and $i_{0}$ as in Lemma 3.3 we have the following.

  1. (a)

If $i_{0}$ is an integer, then ${\cal F}_{i_{0}}(n,a,b)$ and ${\cal
F}_{i_{0}+1}(n,a,b)$ are non-equivalent independent sets of
$\Gamma(n,\\{a,b\\})$.

  2. (b)

If $a+b=n-1$, then $i_{0}=2b-n-1$ and the sets ${\cal F}_{i_{0}}(n,a,b)$,
${\cal F}_{i_{0}+1}(n,a,b)$ and $\bar{\cal F}_{i_{0}+2}(n,a,b)$ are non-
equivalent independent set of $\Gamma(n,\\{a,n-a-1\\})$ of size
$\genfrac{(}{)}{0.0pt}{1}{n}{2a+1}\genfrac{(}{)}{0.0pt}{1}{2a}{a-1}+\genfrac{(}{)}{0.0pt}{1}{2a}{a}$.

###### Proof.

Put ${\cal F}_{i}={\cal F}_{i}(n,a,b)$ for $i\in\\{i_{0},i_{0}+1\\}$ and
${\cal F}_{i}=\bar{\cal F}_{i}(n,a,b)$ for $i=i_{0}+2$.

(a) Part 1. Consider $i\in\\{i_{0},i_{0}+1\\}$ and a vertex $(A,B)$ that does
not lie in ${\cal F}_{i}$. In this part we determine the number of neighbors
of $(A,B)$ in ${\cal F}_{i}$ or a lower bound for this number.

Case 1. $[i]\subseteq B$.

As $(A,B)\notin{\cal F}_{i}(n,a,b)$, it follows that $\min(A)\geq i+1$ and
$n\in B$. With

$\displaystyle
z_{1}(i):=\genfrac{(}{)}{0.0pt}{1}{n-i-1}{n-b}\genfrac{(}{)}{0.0pt}{1}{b-i}{a}\
\text{and}\
z_{2}(i):=\genfrac{(}{)}{0.0pt}{1}{n-i-1}{n-b}\genfrac{(}{)}{0.0pt}{1}{b-i-1}{a}$

there exist exactly $z_{1}(i)$ such vertices $(A,B)$ and exactly $z_{2}(i)$
have $n\notin A$. The neighbors of $(A,B)$ in ${\cal F}_{i}$ are the vertices
$(A^{\prime},B^{\prime})$ satisfying $[i]\subseteq B^{\prime}\subseteq[n-1]$
with $|B\cap B^{\prime}|=2b-n$ and $B^{\prime}\cap A=\emptyset$ and
$A^{\prime}\subseteq B^{\prime}\setminus B$. It follows the that number of
neighbors of $(A,B)$ in ${\cal F}_{i}$ is

$\displaystyle m_{1}(i):=\binom{b-i-a-1}{n-b-a-1}\binom{n-b}{a},\ \ \text{if
$n\notin A$},$ (5) $\displaystyle
m_{2}(i)=\binom{b-i-a}{n-b-a}\binom{n-b}{a},\ \ \text{if $n\in A$}.$ (6)

Case 2. $[i]\not\subseteq B$.

Then $[j-1]\subseteq B$ and $j\notin B$ for some integer $j\in[i]$. As
$(A,B)\notin{\cal F}_{i}(n,a,b)$, then $A\subseteq B\setminus[j-1]$. Therefore
$|B\setminus(A\cup[j-1])|=b-a+1-j$. Therefore the number of neighbors
$(A^{\prime},B^{\prime})$ of $(A,B)$ in ${\cal F}_{i}(n,a,b)$ that satisfy
$[j]\subseteq B^{\prime}$ and $j=\min A^{\prime}$ is

$\displaystyle m(j):=\binom{b-a+1-j}{n-b-a}\binom{n-b-1}{a-1}.$

If $n\in B$, then $(A,B)$ has neighbors $(A^{\prime},B^{\prime})$ in ${\cal
F}_{i}$ that satisfy $[i]\subset B^{\prime}\subseteq[n-1]$ and
$\min(A^{\prime})>i$. Hence the number of neighbors of $(A,B)$ in ${\cal
F}_{i}(n,a,b)$ is at least $m_{3}(i):=m(i)$ and equality occurs if and only if
$j=i$ and $n\notin B$. The number of such vertices $(A,B)$ is

$\displaystyle z_{3}(i):=\binom{n-i-1}{n-b-2}\binom{b+1-i}{a}.$

Part 2. Now we use this information to show that ${\cal F}_{i_{0}}$ and ${\cal
F}_{i_{0}+1}$ are not equivalent. Recall the definition of $i_{0}$ in (3) and
that $a+b\leq n-1$. This implies that $m_{2}(i_{0})>m_{1}(i_{0})$ and
$m_{3}(i_{0})>m_{1}(i_{0})$. Hence, every vertex outside ${\cal F}_{i_{0}}$
has at least $m_{1}(i_{0})$ neighbors in ${\cal F}_{i_{0}}$ and there are
exactly $z_{2}(i_{0})$ vertices with $m_{1}(i_{0})$ neighbors in ${\cal
F}_{i_{0}}$.

We have seen that there are vertices outside ${\cal F}_{i_{0}+1}$ with
$m_{1}(i_{0}+1)$ neighbors in ${\cal F}_{i_{0}+1}$. If $a+b<n-1$, then
$m_{1}(i_{0})>m_{1}(i_{0}+1)$ and hence $F_{i_{0}}$ and $F_{i_{0}+1}$ are not
equivalent.

Now consider the case $a+b=n-1$. Then $i_{0}=2b-n-1$ and
$m_{1}(i_{0})=m_{1}(i_{0}+1)=m_{2}(i_{0}+1)$. Also, using $a+b=n-1$, we see
that $m_{3}(i_{0}+1)\geq m_{1}(i_{0}+1)$ with equality if and only if $a=1$.
If $a>1$, it follows that $z_{1}(i_{0}+1)$ vertices have exactly
$m_{1}(i_{0})$ neighbors in $F_{i_{0}+1}$. Since
$z_{1}(i_{0}+1)<z_{2}(i_{0})$, it follows in this case that $F_{i_{0}}$ and
$F_{i_{0}+1}$ are not equivalent. Finally consider the case $a=1$ and $b=n-2$.
Then $i_{0}=n-5$ and $m_{1}(i_{0})=m_{k}(i_{0}+1)$ for $k=1,2,3$. Also, there
are exactly $z_{1}(i_{0}+1)+z_{3}(i_{0}+1)=6+3=9$ vertices with $m_{1}(i_{0})$
neighbors in $F_{i_{0}+1}$ and $z_{2}(i_{0})=12$ vertices with $m_{1}(i_{0})$
neighbors in $F_{i_{0}}$. Thus, also in this situation, the two independent
sets are not equivalent.

(b) Put ${\cal F}_{i_{0}+2}=\bar{\cal F}_{i_{0}+2}(n,a,b)$. In this part we
have $a+b=n-1$, which implies that $i_{0}=2b-n-1=b-a-2\geq 0$,
$m_{1}(i_{0}+1)=m_{2}(i_{0}+1)=a+1$ and $m_{3}(i_{0}+1)=2a$. From the proof of
(a) we know the following:

  * •

The vertices of $M_{1}:=\\{(A,B)\mid[i_{0}+1]\cup\\{n\\}\subseteq B,\
\min(A)\geq i_{0}+2\\}$ have $a+1$ neighbors in ${\cal F}_{i_{0}+1}$ and
$|M_{1}|=z_{1}(i_{0}+1)$.

  * •

The vertices of $M_{2}:=\\{(A,B)\mid[i_{0}]\subseteq B,\ i_{0}+1,n\notin B,\
\min(A)>i_{0}+1\\}$ have $2a$ neighbors in ${\cal F}_{i_{0}+1}$ and
$|M_{2}|=z_{3}(i_{0}+1)$.

  * •

Every other vertex outside ${\cal F}_{i_{0}+1}$ has more than $2a$ neighbors
in ${\cal F}_{i_{0}+1}$.

In a similar way one sees the following.

  * •

The vertices of $M^{\prime}_{1}:=\\{(A,B)\mid[i_{0}+1]\subseteq B,\
i_{0}+2\notin B,\ \min(A)>i_{0}+2\\}$ have $a+1$ neighbors in ${\cal
F}_{i_{0}+2}$ and $|M^{\prime}_{1}|=z_{1}(i_{0}+1)$.

  * •

The vertices of $M^{\prime}_{2}:=\\{(A,B)\mid[i_{0}]\subseteq B,\
i_{0}+1\notin B,\ \min(A)=i_{0}+2\\}$ have $2a$ neighbors in ${\cal
F}_{i_{0}+2}$ and $|M^{\prime}_{2}|=z_{3}(i_{0}+1)$.

  * •

Every other vertex outside ${\cal F}_{i_{0}+2}$ has more than $2a$ neighbors
in ${\cal F}_{i_{0}+2}$.

Hence the number of vertices with $a+1$ neighbors in ${\cal F}_{i_{0}+1}$ is
equal to the number of vertices with $a+1$ neighbors in ${\cal F}_{i_{0}+2}$.
We have seen in the proof of (a) that this number is different from the number
of vertices that have $a+1$ neighbors in ${\cal F}_{i_{0}}$. Thus ${\cal
F}_{i_{0}}$ and ${\cal F}_{i_{0}+2}$ are not equivalent. In order to see that
${\cal F}_{i_{0}+1}$ and ${\cal F}_{i_{0}+2}$ are not equivalent, we consider
two cases. We remark that this case is slightly more complicated, since for
each $j$, the number of vertices with exactly $j$ neighbors in ${\cal
F}_{i_{0}+1}$ is equal to the number of vertices with exactly $j$ neighbors in
${\cal F}_{i_{0}+2}$.

Case 1. $a\geq 2$, that is $a+1<2a$.

Then the set of vertices with $2a$ neighbors in ${\cal F}_{i_{0}+1}$ or ${\cal
F}_{i_{0}+2}$ is $M_{2}$ respectively $M^{\prime}_{2}$. The elements of ${\cal
F}_{i_{0}+1}$ that have at least one neighbor in $M_{1}$ are
$(A^{\prime},B^{\prime})$ with $[i]\cup\\{n\\}\subseteq B^{\prime}$ and
$\min(A^{\prime})=i$. Depending on $n\in A^{\prime}$ or $n\notin A^{\prime}$,
the number of neighbors of $(A^{\prime},B^{\prime})$ in $M_{1}$ is different.
The elements of $\bar{\cal F}_{i_{0}+2}$ that have a neighbor in
$M^{\prime}_{2}$ are $(A^{\prime},B^{\prime})$ with $\min A^{\prime}=i-1,\
[i-1]\subseteq B^{\prime},\ i\notin B^{\prime}$. By symmetry all these
vertices have the same number of neighbors in $M_{2}$. This implies that
${\cal F}_{i_{0}+1}$ and ${\cal F}_{i_{0}+2}$ are not equivalent.

Case 2. $a=1$, so $a+1=2a$.

Then $M_{1}\cup M_{2}$ consists of the vertices with $2a=a+1$ neighbors in
${\cal F}_{i_{0}+1}$, and $M^{\prime}_{1}\cup M^{\prime}_{2}$ consists of the
vertices with $2a=a+1$ neighbors in ${\cal F}_{i_{0}+2}$.

We have $|M_{1}|=6$ and $|M_{2}|=3$ where $M_{1}$ consists of $(A,B)$ with
$A=\\{c\\}$, $B=[n-4]\cup\\{c,n\\}$, or $A=\\{n\\}$, $B=[n-4]\cup\\{c,n\\}$,
and $M_{2}$ consists of the vertices $(A,B)$ with $A=\\{c\\}$ and
$B=[n]\setminus\\{n-4,n\\}$, where $n-3\leq c\leq n-1$. We see that the first
three vertices of $M_{1}$ have no neighbor in $M_{1}\cup M_{2}$.

The set $M^{\prime}_{1}$ consists of the six vertices $B=[n-4]\cup G$ and
$A=\\{c\\}\subseteq G$ where $G$ is $2$-subset of $\\{n-2,n-1,n\\}$, and
$M_{2}$ consists of the three vertices with $B=[n-5]\cup G$ where
$G=\\{n-2,n-2,n-1\\}$ and $A=\\{c\\}$ with $c\in G$. Hence every vertex of
$M^{\prime}_{1}\cup M^{\prime}_{2}$ has at least one neighbor in
$M^{\prime}_{1}\cup M^{\prime}_{2}$.

We have shown that graphs induced on $M_{1}\cup M_{2}$ and on
$M^{\prime}_{1}\cup M^{\prime}_{2}$ are not isomorphic, and this implies that
the sets ${\cal F}_{i_{0}+1}$ and ${\cal F}_{i0+2}$ are not equivalent. ∎

Notation. For positive integers $n,a,b$ with $a+b<n$ and $a<\frac{n}{2}<b$ we
denote by $f(n,a,b)$ the largest cardinality of the independent sets that have
been constructed in Examples 3.1, that is

$\displaystyle f(n,a,b)$ $\displaystyle=\max\\{|{\cal F}_{j}(n,a,b)|:0\leq
j\leq 2b-n+1\\}$
$\displaystyle=\binom{n-1-i}{b-i}\binom{b-i}{a}+\binom{n-b+a-1}{a-1}\left(\binom{n}{b-a}-\binom{n-i}{b-a-i}\right)$

where

$\displaystyle i:=\max\\{0,\left\lceil
b-1-\frac{(n-b)(n-b-1)}{a}\right\rceil\\}.$ (7)

##  4 The cycle method

In this section we consider the graphs $\Gamma(n,\\{a,b\\})$ with
$a<\frac{n}{2}<b$ and $a+3b\leq 2n$. The number $i_{0}$ defined in (3) is
negative and hence $i$ defined in (7) is zero, so the results in Section 3
show that ${\cal F}_{0}(n,a,b)$ is an independent set with

$\displaystyle|{\cal
F}_{0}(n,a,b)|=f(n,a,b)=\genfrac{(}{)}{0.0pt}{1}{n-1}{b}\genfrac{(}{)}{0.0pt}{1}{b}{a}.$

We now show that there is in fact no larger independent set.

######  Theorem 4.1.

For positive integers $a$, $b$ and $n$ with $n<2b$ and $a+3b\leq 2n$ we have

$\alpha(\Gamma(n,\\{a,b\\})=\genfrac{(}{)}{0.0pt}{1}{n-1}{b}\genfrac{(}{)}{0.0pt}{1}{b}{a}.$

###### Proof.

The above example shows that the independence number can not be smaller. To
show that equality holds, we consider $M:=\\{0,1,\dots,n-1\\}$ and an
independent set ${\cal F}$ of flags of $M$ of type $\\{a,b\\}$. Put $s:=2b-n$
and notice that $a<2s+a\leq b$. Let $X$ be the set consisting of all pairs
$(f,c)$ with vertices $f=\\{A,B\\}\in{\cal F}$ and $n$-cycles
$c=(m_{0},\dots,m_{n-1})$ of the elements of $M$ such that there exists an
index $i$ with $B=\\{m_{i+j}\mid 1\leq j\leq b\\}$ and $A=\\{m_{i+s+j}\mid
1\leq j\leq a\\}$, where indices are modulo $n$.

Each $f\in{\cal F}$ occurs in precisely $a!(b-a)!(n-b)!$ pairs of $X$.
Therefore we have $|X|=|{\cal F}|a!(b-a)!(n-b)!$.

Now consider an $n$-cycle $c=(m_{0},\dots,m_{n-1})$ and let $t$ be the number
of pairs of $X$ in which $c$ occurs. Let these pairs be $(f_{i},c)$, $1\leq
i\leq t$, where $f_{i}=\\{A_{i},B_{i}\\}$ with $|A_{i}|=a<b=|B_{i}|$. We want
to show that $t\leq n-b$. For this we may assume that $t\geq 1$. Consider
$1\leq i,j\leq t$. As $f_{i}$ and $f_{j}$ are vertices that are not connected
by an edge we have $|B_{i}\cap B_{j}|>2b-n$ or $A_{i}\cap B_{j}\not=\emptyset$
or $A_{j}\cap B_{i}\not=\emptyset$. Since $b\geq 2s+a$ and
$(f_{i},c),(f_{j},c)\in X$, we see that each of $A_{i}\cap
B_{j}\not=\emptyset$ and $A_{j}\cap B_{i}\not=\emptyset$ implies that
$|B_{i}\cap B_{j}|\geq s+1>2b-n$. Hence $|B_{i}\cap B_{j}|>2b-n$ in any case.
Thus any two of the sets $\bar{B}_{i}:=[n]\setminus B_{i}$ have non-empty
intersection. As in the classical proof of Katona, see Lemma 2.14.1 in [4], it
follows that $t\leq n-b$. As there are $(n-1)!$ $n$-cycles, it follows that
$|X|\leq(n-1)!\cdot(n-b)$.

Comparing the lower and upper bound for $|X|$ implies the desired result. ∎

Using Proposition 2.5, we find the following corollary, which is Theorem 1.1
from the introduction in a slightly different formulation.

######  Corollary 4.2.

Let $a$, $b$ and $n$ be positive integers with $n<2b$ and $a+3b\leq 2n$. Then
for every subset $T$ of $[a-1]$ with we have

$\displaystyle\alpha(\Gamma(n,T\cup\\{a,b\\})=\genfrac{(}{)}{0.0pt}{1}{n-1}{b}\genfrac{(}{)}{0.0pt}{1}{b}{a}\cdot|V\Gamma(a,T)|.$

######  Remarks 4.3.

  1. 1.

The set ${\cal F}_{0}(n,a,b)$ is in general not the only largest independent
set of $\Gamma(n,\\{a,b\\})$. For example for $n=7$ and type $\\{2,4\\}$ there
are 14 non equivalent independence sets of size $90$ as can be verified by
computer and ${\cal F}_{0}(7,2,4)$, ${\cal F}_{1}(7,2,4)$ and $\bar{\cal
F}_{2}(7,2,4)$ are among these.

  2. 2.

For $(n,a,b)=(9,1,6)$ the condition $a+3b\leq 2n$ is not fulfilled, but it can
be verified by computer that
$\alpha(\Gamma(n,\\{a,b\\})=\genfrac{(}{)}{0.0pt}{1}{n-1}{b}\genfrac{(}{)}{0.0pt}{1}{b}{a}$.

##  5 The chromatic number of $\Gamma(n,\\{1,n-2\\})$

In this section we classify the largest independent sets of
$\Gamma(n,\\{1,n-2\\})$ for $n\geq 5$ using induction on $n$. The induction
step can be proved without significantly larger effort for more general
graphs. We formulate this in Proposition 5.2, which is the main result of this
section.

Recall that we have defined $f(n,a,b)$ for positive integers $n,a,b$ with
$n>a+b$ and $a<\frac{n}{2}<b$ in the end of Section 3 and that $f(n,a,b)$ is
the cardinality of the largest independent sets of $\Gamma(n,\\{a,b\\})$ that
were constructed in Example 3.1.

######  Lemma 5.1.

For integers $n,a,b$ with $n\geq a+b+1$ and $a<\frac{n}{2}<b$ we have

$\displaystyle f(n,a,b)$
$\displaystyle=f(n-1,a,b-1)+\binom{n-1}{b-1}\binom{b-1}{a-1}$

and with $i$ as in (7) we have

$\displaystyle n\cdot
f(n-1,a,b-1)-(b-a)f(n,a,b)=\frac{[(n-b)^{2}+a(i-b)](n-1-i)!}{a!(n-b)!(b-i-a)!}$

###### Proof.

This follows from straightforward calculations. For the second equation, one
may apply (4) using that $f(n,a,b)=|{\cal F}_{i}(n,a,b)|$ and
$f(n-1,a,b-1)=|{\cal F}_{i-1}(n-1,a,b-1)|$. ∎

Let $a$, $b$ and $n$ be positive integers with $n\geq a+b+1$ and
$a<\frac{n}{2}<b$. Let $M$ be a set with $n$ elements. In this section an
independent set ${\cal F}$ of $\Gamma(M,\\{a,b\\})$ will be called an
independent set of _standard type_ if $|{\cal F}|=f(n,a,b)$ and if there
exists a graph isomorphism $\mu$ of $\Gamma(M,\\{a,b\\})$ onto
$\Gamma(n,\\{a,b\\})$ such that $\mu({\cal F})$ is equal to one of the
independent sets of $\Gamma(n,\\{a,b\\})$ that were constructed in Example
3.1.

######  Proposition 5.2.

Let $a,b,n\geq 1$ be integers with $n\geq a+b+1$ and $a<\frac{n}{2}<b$. Define
$i$ as in (7) and assume that

$\displaystyle n\geq\frac{[(n-b)^{2}+a(i-b)](n-1-i)!}{a!(n-b)!(b-i-a)!}+3a+1.$
(8)

Assume furthermore that $f(n-1,a,b-1)$ is the independence number of
$\Gamma(n-1,\\{a,b-1\\})$ and that every independent set of
$\Gamma(n-1,\\{a,b-1\\})$ is of standard type. Then $f(n,a,b)$ is the
independence number of $\Gamma(n,\\{a,b\\})$ and every independent set of
$\Gamma(n,\\{a,b\\})$ is of standard type.

For the proof of the proposition we define $M:=[n]$ and consider an
independent set ${\cal F}$ of $\Gamma(M,\\{a,b\\})$ with $|{\cal
F}|=f(n,a,b)$. Recall that the vertices of $\Gamma(n,\\{a,b\\})$ are flags of
type $\\{a,b\\}$, which we denote as ordered pairs $(A,B)$ where $A\subseteq
B\subseteq M$, $a=|A|$ and $b=|B|$. In order to prove the proposition, we have
to show that ${\cal F}$ is of standard type. This will be done in several
lemmas in which we use for $c\in M$ the notation

${\cal F}_{c}:=\\{(A,B)\in{\cal F}\mid c\in B\setminus A\\}$

and

$\hat{\cal F}_{c}:=\\{(A,B\setminus\\{c\\})\mid(A,B)\in{\cal F}_{c}\\}.$

######  Lemma 5.3.

If the set $S$ has cardinality $n-1$, then the graph $\Gamma(S,\\{a,b-1\\})$
has independence number $f(n-1,a,b-1)$ and its largest independent set are of
standard type.

###### Proof.

This follows from that the hypotheses of Proposition 5.2 since
$\Gamma(S,\\{a,b-1\\})$ and $\Gamma(n-1,\\{a,b-1\\})$ are isomorphic graphs. ∎

######  Lemma 5.4.

For every element $c\in M$, the set $\hat{\cal F}_{c}$ is an independent set
of the graph $\Gamma(M\setminus\\{c\\},\\{a,b-1\\})$ with $|{\cal F}_{c}|\leq
f(n-1,a,b-1)$.

###### Proof.

Since ${\cal F}$ is an independent of $\Gamma(M,\\{a,b\\})$, then ${\cal
F}_{c}$ is an independent set of $\Gamma(M\setminus\\{c\\},\\{a,b-1\\})$.
Apply Lemma 5.3. ∎

######  Lemma 5.5.

We have

$\displaystyle\sum_{c\in M}\left(f(n-1,a,b-1)-|{\cal
F}_{c}|\right)=\frac{[(n-b)^{2}+a(i-b)](n-1-i)!}{a!(n-b)!(b-i-a)!}.$ (9)

###### Proof.

Every element of ${\cal F}$ is a member of ${\cal F}_{c}$ for $b-a$ elements
$c$ of $M$. Therefore $|{\cal F}|(b-a)=\sum_{c\in M}|{\cal F}_{c}|$. Since
$|{\cal F}|=f(n,a,b)$, the claim follows from Lemma 5.1. ∎

######  Lemma 5.6.

If there exists an element $x\in M$ such that $x\in B$ for all elements
$(A,B)$ of ${\cal F}$, then ${\cal F}$ is of standard type.

###### Proof.

Lemma 5.4 gives $|{\cal F}_{x}|\leq f(n-1,a,b-1)$. Since $x\in B$ for all
$(A,B)\in{\cal F}$, then each element $(A,B)$ of ${\cal F}\setminus{\cal
F}_{x}$ satisfies $x\in A$. This implies that $|{\cal F}\setminus{\cal
F}_{x}|\leq{n-1\choose b-1}\genfrac{(}{)}{0.0pt}{1}{b-1}{a-1}$. Hence

$\displaystyle|{\cal F}|$ $\displaystyle=|{\cal F}_{x}|+|{\cal
F}\setminus{\cal F}_{x}|\leq f(n-1,a,b-1)+{n-1\choose
b-1}\binom{b-1}{a-1}=f(n,a,b)$

where we have used Lemma 5.1 in the last step. Since $|{\cal F}|=f(n,a,b)$, it
follows that $|{\cal F}_{x}|=f(n-1,a,b-1)$ and that ${\cal F}\setminus{\cal
F}_{x}$ consists of all flags $(A,B)$ of $M$ of type $\\{a,b\\}$ with $x\in
A$. Since $|{\cal F}_{x}|=|\hat{\cal F}_{x}|$, Lemma 5.3 shows that the
independent set $\hat{\cal F}_{x}$ of $\Gamma(M\setminus\\{x\\},\\{a,b-1\\})$
is of standard type. From the construction in Example 3.1 it follows that
${\cal F}$ is of standard type. ∎

######  Lemma 5.7.

Suppose that $c$ is an element of $M$ with $|{\cal F}_{c}|=f(n-1,a,b-1)$.

  1. (a)

There exists a unique index $\hat{c}\not=c$ such that $\hat{c}\in B$ for all
$(A,B)\in{\cal F}_{c}$.

  2. (b)

Every vertex $(A,B)$ of $\Gamma(M,\\{a,b\\})$ with $\hat{c}\in A$ and $c\in
B\setminus A$ lies in ${\cal F}_{c}$.

  3. (c)

If $(A,B)\in{\cal F}$, then $\hat{c}\in B$ or $c\in A$.

###### Proof.

Since $|\hat{\cal F}_{c}|=|{\cal F}_{c}|=f(n-1,a,b-1)$, Lemma 5.3 shows that
$\hat{\cal F}_{c}$ is an independent set of
$\Gamma_{c}:=\Gamma(M\setminus\\{c\\},\\{a,b-1\\})$ of standard type.
Inspection of the independent sets of standard type shows that there exists a
unique element $\hat{c}\in M\setminus\\{c\\}$ such that $\hat{c}\in
B^{\prime}$ for every element $(A,B^{\prime})$ of $\hat{\cal F}_{c}$. This
proves (a). The inspection also shows that $(A,B^{\prime})\in{\cal F}_{c}$ for
every vertex $(A,B^{\prime})$ of $\Gamma_{c}$ with $\hat{c}\in A$. This proves
(b).

We prove (c) indirectly. Assume that ${\cal F}$ contains a vertex $(A,B)$ with
$\hat{c}\notin B$ and $c\notin A$. Then (a) shows that $(A,B)\notin{\cal
F}_{c}$. Since $c\notin A$, this implies that $c\notin B$. Hence $B\subseteq
M\setminus\\{c,\hat{c}\\}$. Choose a set $T$ with $A\subseteq T\subseteq B$
and $|T|=n-b$ and put $B_{0}:=M\setminus T$. Then $|B_{0}|=b$ and
$|B_{0}\setminus B|=|B\setminus B_{0}|=|T|=n-b=a+1$. Also $c,\hat{c}\in
B_{0}$. Since $n-b\geq a+1$, there exists a set $A_{0}\subseteq B_{0}$ of
cardinality $a$ satisfying $\hat{c}\in A_{0}$ and $c\notin A_{0}$. From (b) we
see that $(A_{0},B_{0})\in{\cal F}$. We have $B\cup B_{0}=M$ as well as $A\cap
B_{0}=A_{0}\cap B=\emptyset$. Hence $(A_{0},B_{0})$ and $(A,B)$ are adjacent
vertices. As both vertices lie in ${\cal F}$ and since ${\cal F}$ is an
independent set, this is the desired contradiction. ∎

Notation. For every $c\in M$ with $|{\cal F}_{c}|=f(n-1,a,b-1)$ we denote by
$\hat{c}$ the element provided by the previous lemma.

######  Lemma 5.8.

Let $C$ be the set of all elements $c\in M$ with $|{\cal
F}_{c}|=f(n-1,a,b-1)$.

  1. (a)

If there exist $d\in M$ and $T\subseteq C$ with $|T|>a$ and $\hat{c}=d$ for
all $c\in T$, then $d\in B$ for all $(A,B)\in{\cal F}$.

  2. (b)

If $c_{1},c_{2}\in C$, then $\hat{c}_{1}=\hat{c}_{2}$ or $\hat{c}_{1}=c_{2}$
or $\hat{c}_{2}=c_{1}$.

###### Proof.

(a) Assume on the contrary that ${\cal F}$ contains an element $(A,B)$ with
$d\not\in B$. Then Lemma 5.7 (c) shows $T\subseteq A$. As $|T|>a$, this is
impossible.

(b) Assume on the contrary that $c_{1},\hat{c}_{1},c_{2},\hat{c}_{2}$ are four
distinct elements. Since $n-b\geq a+1\geq 2$ we see that $M$ has subsets
$B_{1}$ and $B_{2}$ of cardinality $b$ with $c_{1},\hat{c}_{1}\in
B_{1}\setminus B_{2}$ and $c_{1},\hat{c}_{2}\in B_{2}\setminus B_{1}$ and
$B_{1}\cup B_{2}=M$. Then $|B_{1}\setminus B_{2}|=n-b\geq a+1$ and hence there
exists a set $A_{1}\subseteq B_{1}\setminus B_{2}$ with $|A|=a$ and
$\hat{c}_{1}\in A_{1}$ and $c_{1}\notin A_{1}$. The same argument shows that
there exists $A_{2}\subseteq B_{2}$ with $|A_{2}|=a$ and $\hat{c}_{2}\in
A_{2}$ and $c_{2}\notin A_{2}$. Lemma 5.7 (b) shows that
$(A_{1},B_{1}),(A_{2},B_{2})\in{\cal F}$. But these two vertices are adjacent,
contradiction. ∎

######  Lemma 5.9.

Suppose that there exists a set $T\subseteq M$ with $|T|=3a+1$ and $|{\cal
F}_{c}|=f(n-1,a,b-1)$ for all $c\in T$. Then there exists an element $x\in M$
with $x\in B$ for all $(A,B)\in{\cal F}$.

###### Proof.

This follows from Lemma 5.8, if there are $a+1$ elements $c\in T$ with the
same $\hat{c}$. We may thus assume that this does not occur. As $|T|>3a$, this
implies that there exits $c_{1},c_{2},c_{3},c_{4}\in T$ such that
$\hat{c}_{1},\hat{c}_{2},\hat{c}_{3},\hat{c}_{4}$ are pairwise distinct. Lemma
5.8 (b) shows that we may assume that $\hat{c}_{2}=c_{1}$. Since
$\hat{c}_{3}\not=\hat{c}_{4}$, we may also assume that
$\hat{c}_{3}\not=c_{2}$. Then $c_{2},c_{3},\hat{c}_{2},\hat{c}_{3}$ are
mutually distinct. Lemma 5.8 (b) gives a contradiction. ∎

Proof of Proposition 5.2. Using (8) we see from Lemma 5.4 and 5.5 that $|{\cal
F}_{c}|=f(n-1,a,b-1)$ for at least $3a+1$ elements $c$ of $M$. Then Lemma 5.9
shows that there exists an element $x\in M$ with $x\in B$ for all
$(A,B)\in{\cal F}$. Lemma 5.6 now proves the proposition.

REMARK. The proposition may be used as an induction step $n-1\to n$ to
determine the independence number of $\Gamma(n,a,n-s)$ for given $a$ and $s$
(with $\frac{n}{2}>s\geq a+1\geq 2$) when $n$ satisfies (8) for $a$ and
$b=n-s$, that is for

$\displaystyle n\geq\frac{[s^{2}-a(1+x)](s+x)!}{a!s!(1+x-a)!}+3a+1.$ (10)

where $x=\lfloor(s(s-1)/a\rfloor$. For $a=1$ and $s=2$, this is $n\geq 10$,
and so the induction basis requires to show that the largest independent sets
of $\Gamma(9,\\{1,7\\})$ are of standard type. This can be done by computer.
For all other values of $a$ and $s$, the integer $n$ must already be so large
that I did not succeed to verify that induction hypothesis by computer. For
example for $a=2$ and $s=3$, we already need $n\geq 37$, so the induction
hypothesis requires to show that the independence number of
$\Gamma(36,\\{1,33\\})$, which is a graph with 235620 vertices, is 58947. So
we obtain a theorem only in the case when $a=1$ and $s=2$, that is $b=n-2$.

######  Theorem 5.10.

For all integers $n\geq 5$ the graph $\Gamma(n,\\{1,n-2\\})$ has independence
number $\genfrac{(}{)}{0.0pt}{1}{n}{3}+2$ and every independent set of
$\Gamma(n,\\{1,n-2\\})$ of cardinality $\genfrac{(}{)}{0.0pt}{1}{n}{3}+2$ is
equivalent to ${\cal F}_{n-5}(n,1,n-2)$ or ${\cal F}_{n-4}(n,1,n-2)$ or
$\bar{\cal F}_{n-3}(n,1,n-2)$ as defined in Example 3.1.

###### Proof.

Using induction on $n$ and Proposition 5.2, we only have to verify that the
statement is true for $n\in\\{5,6,7,8,9\\}$. This can easily be done by
computer for example using the package grape in GAP. ∎

##  6 Open problems

A natural question is probably if not to determine the independence number of
all graphs $\Gamma(n,M)$ to do this for the case $|M|=2$. The only open case
here for $n\leq 8$ is $n=8$ and $M=\\{2,5\\}$. We give some information on
this case and some more special problems below.

######  Lemma 6.1.

If $\alpha$ is the chromatic number of $\Gamma(8,\\{2,5\\})$, then
$230\leq\alpha\leq 240$.

###### Proof.

The set ${\cal F}_{1}(8,2,5)$ is an independent set of $\Gamma(8,\\{2,5\\})$
with $230$ elements. This gives the lower bound. For the upper bound we use
that $\Gamma(7,\\{2,4\\})$ has independence number 90 by Theorem 4.1. Suppose
${\cal F}$ is an independent set of $\Gamma(8,\\{2,5\\})$. For each $c\in[8]$,
let ${\cal F}_{c}$ be the set of elements $(A,B)$ of ${\cal F}$ with $c\in
B\setminus A$. As in the proof of Lemma 5.5 we see that $\sum_{i=1}^{8}|{\cal
F}_{c}|=(5-2)\cdot|{\cal F}|$. Each set ${\cal F}_{c}$ is an independent set
of the graph $\Gamma([8]\setminus\\{c\\},\\{2,5\\})$ and hence has at most
$90$ elements. It follows that $3|{\cal F}|\leq 8\cdot 90$, so $|{\cal F}|\leq
240$. ∎

Remark. The smallest eigenvalue of the adjacency matrix $A$ of
$\Gamma(8,\\{2,5\\})$ is $-\frac{3}{2}(1+\sqrt{17})$, so the Hoffman bound
gives $\alpha\leq 257$ for the independence number. If one considers the
coherent configuration corresponding to $\Gamma(8,\\{2,5\\})$, then one can
apply semidefinite programming, but in this case it gives nothing better than
the Hoffman bound. It can be checked that $A$ has the same number of positive
and negative eigenvalues, so the inertia bound applied to $A$ does not give a
better bound, but I did not check other matrices. Finally, since the
independence number is larger than $560/3$, also the clique-coclique bound
does not help to find a better bound for $\alpha$

Problem 1: Determine the chromatic number of $\Gamma(8,T)$ in the cases that
$T$ is one of the sets $\\{2,5\\}$, $\\{1,3,5\\}$ and $\\{1,4,5\\}$. These are
all open problems for $n=8$ up to duality.

Problem 2: Determine the chromatic number of $\Gamma(9,T)$ for $T=\\{1,6\\}$
and for $T=\\{2,6\\}$. These are the only open cases for $n=9$ and $|T|=2$.

Problem 3: It can be checked by computer that every independent set of
$\Gamma(7,\\{1,4\\})$ is equivalent to ${\cal F}_{0}(7,\\{1,4\\})$. Find an
computer-free argument for this fact.

Problem 4: Are there constructions of independent sets of
$\Gamma(n,\\{a,b\\})$ with $a+b<n$ and $a<\frac{n}{2}<b$ that are larger than
the ones constructed in Examples 3.1.

## References

  * [1] J. De Beule, S. Mattheus, and K. Metsch.  An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings.  arXiv:2007.01104v1, 2020.
  * [2] P. Erdős, Chao Ko, and R. Rado.  Intersection theorems for systems of finite sets.  Quart. J. Math. Oxford Ser. (2), 12:313–320, 1961.
  * [3] P. Frankl and R. M. Wilson.  The Erdős-Ko-Rado theorem for vector spaces.  J. Combin. Theory Ser. A, 43(2):228–236, 1986.
  * [4] Chris Godsil and Karen Meagher.  Erdős-Ko-Rado theorems: algebraic approaches, volume 149 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2016.
  * [5] W. N. Hsieh.  Intersection theorems for systems of finite vector spaces.  Discrete Math., 12:1–16, 1975.
  * [6] P. Newman.  Independent sets and eigenvalues.  PhD thesis, University of Waterloo, Waterloo, 2004.