Distance Regular Graphs

and Unimodality

John S. Caughman, IV and Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027

1. Distance regular graphs

2. Association schemes

Distance Regular Graphs

3. Terwilliger algebras Let Γ = (X, R) be a graph with vertices X and edges R (relations). Let ∂ be Γ’s distance function and define the sphere of radius i about x ∈ X to be

Γ_{i}(x) = {y ∈ X : ∂(x, y) = i}.

Γ is a distance regular graph or drg if, given x, y with ∂(x, y) = h, the cardinality

p_{ij}^{h} := |Γ_{i}(x) ∩ Γ_{j}(y)|

depends only on i, j and h and not on the particular x, y chosen. Thus the valency

k_{i} := |Γ_{i}(x)| = p_{ii}^{0}

does not depend on x. (So Γ is regular of degree k := k_{1}.)

A sequence of real numbers is unimodal if for some index m

a_{0} ≤ a_{1} ≤ … ≤ a_{m} ≥ a_{m+1} ≥ …

Theorem 1 Let Γ be a drg of diameter D. Then the sequence

k_{0}, k_{1}, …, k_{D}

is unimodal.

For example, the D-cube is a drg with k_{i} = \binom{D}{i} and

\binom{D}{0} ≤ \binom{D}{1} ≤ … ≤ \binom{D}{⌊D/2⌋} ≥ … ≥ \binom{D}{D}.

The ith distance matrix, A_{i}, has rows and columns indexed by X and

(A_{i})_{xy} = \{ \begin{matrix}1 & if ∂(x, y) = i, \\ 0 & else. \end{matrix}

So A := A_{1} is the usual adjacency matrix. Let J be the |X| × |X| matrix of all 1’s. Then the matrices A_{0}, …, A_{D} are non-zero 0,1-matrices satisfying

1. A_{0} = I,

2. ∑_{i} A_{i} = J,

3. A_{i}^{t} = A_{i} for 0 ≤ i ≤ D,

4. A_{i}A_{j} = ∑_{h} p_{ij}^{h}A_{h} for 0 ≤ i, j ≤ D,

5. A_{i} is a polynomial of degree i in A for 0 ≤ i ≤ D.

Association Schemes

An association scheme is Y = (X, {A_{0}, …, A_{D}}) such that the A_{i} are nonzero 0,1-matrices whose rows and columns are indexed by X such that

(1) A_{0} = I,

(2) ∑_{i} A_{i} = J,

(3) A_{i}^{t} = A_{i} for all i,

(4) A_{i}A_{j} = ∑_{h} p_{ij}^{h}A_{h} for scalars p_{ij}^{h}.

Association scheme Y is P -polynomial if there is an indexing of the A_{i} such that

A_{i} is a polynomial of degree i in A for 0 ≤ i ≤ D.

Theorem 2 Y is P -polynomial if and only if it arises from a drg.

The Bose-Mesner algebra of Y is the vector space

M = span {A_{0}, …, A_{D}}.

Note that M is an algebra by (4) and that the set {A_{0}, …, A_{D}} is independent and so a basis by (2).

(3) and (4) show that the A_{i} are symmetric and commute and so simultaneously diagonalisable. Let E_{1}, …, E_{D} be the orthogonal projections onto the common eigenspaces. They’re a basis for M and

(1’) E_{0} = \frac{1}{|X|}J,

(2’) ∑_{i} E_{i} = I,

(3’) E_{i}^{t} = E_{i} for all i,

(4’) E_{i}∘E_{j} = ∑_{h} q_{ij}^{h}E_{h} for scalars q_{ij}^{h} where ∘ is Schur product (entry-wise).

Note that A_{i} ∘ A_{j} = δ_{ij}A_{i} and E_{i}E_{j} = δ_{ij}E_{i}.

Y is Q-polynomial if for some indexing of the E_{i} we have E_{i} is a Schur polynomial of degree i in E_{1}, ∀i. The multiplicities of Y are m_{i} := rk E_{i}.

Conjecture 3 (Bannai and Ito) If Y is a Q-poly-nomial scheme then the sequence

m_{0}, m_{1}, …, m_{D}

is unimodal.

Theorem 4 (C & S) If Y is a Q-polynomial scheme which is also dual-thin then

m_{i} ≤ m_{i+1} and m_{i} ≤ m_{D−i} for i < D/2.

Terwilliger Algebras

Element x ∈ X has ith dual idempotent the diagonal matrix E_{i}^{∗} = E_{i}^{∗}(x) such that

(E_{i}^{∗})_{yy} = (A_{i})_{xy} for y ∈ X.

(1*) E_{0}^{∗} has 1 in the xx position and 0 elsewhere,

(2*) ∑_{i} E_{i}^{∗} = I,

(3*) (E_{i}^{∗})^{t} = E_{i}^{∗} for all i,

(4*) E_{i}^{∗}E_{j}^{∗} = E_{i}^{∗} ∘ E_{j}^{∗} = δ_{ij}E_{i}^{∗}.

Note also that rk E_{i}^{∗} = k_{i}.

The Terwilliger algebra, T (x) is the one generated by the E_{i} and E_{j}^{∗}. It is a finite dimensional, semisimple ℂ-algebra, not commutative in general. Let W be an irreducible T (x)-module in the decomposition of the standard module for T (x). Then

W = ⊕_{i}E_{i}W.

Call W dual thin if for all i:

dim (E_{i}W) ≤ 1.

Finally Y is dual thin if every such T (x)-module is dual thin for all x ∈ X.