Dual polar spaces as extremal distance-regular graphs

Arnold Neumaier

Institut für Mathematik, Universität Wien Strudlhofgasse 4, A-1090 Wien, Austria email: Arnold.Neumaier@univie.ac.at WWW: http://www.mat.univie.ac.at/∼neum/

Dedicated to the Memory of Jaap Seidel

Abstract. A new inequality for the parameters of distance-regular graphs is proved. It implies that if there are infinitely many distance-regular graphs with fixed λ, μ, a_{i} and c_{i} containing an induced quadrangle then necessarily c_{i+1} ≥ 1 + (μ − 1)c_{i}. As the dual polar graphs show, this inequality is best possible. Some related results are also discussed.

1 A new inequality

The family of distance-regular graphs coming from dual polar spaces (see Brouwer et al. [1] for notation and terminology) has parameters of the form

c_{i} = \frac{q^{i} − 1}{q − 1}, a_{i} = λc_{i}, b_{i} = k − a_{i} − c_{i},  (1)

and for each prime power q and λ = q^{e}(q + 1), e ∈ \{0, \frac{1}{2}, 1, \frac{3}{2}, 2\}, there is an example with arbitrarily large values of k (and large diameter). One may therefore ask about partial lists of intersection numbers realized by infinitely many distance regular graphs. The purpose of this note is to show that the dual polar parameter sets are extremal with respect to this point of view.

1.1 Theorem. The parameters of a distance-regular graph satisfy the restriction

\begin{matrix}[c_{i} + p_{2i−1}^{i}, c_{i}a_{i−1}] + [a_{i} + p_{2i}^{i}, c_{i}(b_{i−1} − 1)] \\ ≤ c_{i}(c_{i} − 1) max(λ − 1, μ − 1) − c_{i}c_{i−1}(μ − 1) \end{matrix}  (2)

for i = 2, …, d, where

p_{2i}^{i} = μ^{−1}(c_{i}b_{i−1} + a_{i}(a_{i} − λ) + b_{i}c_{i+1} − k)),

p_{2i−1}^{i} = μ^{−1}c_{i}(a_{i} + a_{i−1} − λ),

[p, q] = \{ \begin{matrix}⌊\frac{q}{p}⌋(2q − p − ⌊\frac{q}{p}⌋ p) & if p ≠ 0, \\ 0 & otherwise. \end{matrix}

Proof. Fix α, β at distance i. For j ∈ {i, i − 1}, let S_{j} := Γ_{j}(α) ∩ (Γ(β) ∪ Γ_{2}(β)), and denote by N(γ) the number of points in Δ := Γ_{i−1}(α) ∩ Γ(β) ∩ Γ(γ). Counting in two ways the number of configurations involving α, β, γ and 0, 1, or 2 points of Δ gives

∑_{γ∈S_{j}} 1 = p_{1j}^{i} + p_{2j}^{i},  (3)

∑_{γ∈S_{j}} N(γ) = c_{i}(p_{1j}^{i−1} − δ_{ij}),  (4)

∑_{γ∈S_{i−1}∪S_{i}} N(γ)(N(γ) − 1) ≤ c_{i}((c_{i} − 1) max(λ − 1, μ − 1) − c_{i−1}(μ − 1)). (5)

Since

N(N − 1) = s(2N − 1 − s) + (N − s)(N − s − 1) ≥ s(2N − 1 − s)

for any integer s we can bound the left hand side of (5) from below by

∑_{j=i−1}^{i} s_{j} ∑_{γ∈S_{j}}(2N(γ)−1−s_{j}) = ∑_{j=i−1}^{i} s_{j}(2c_{i}(p_{1j}^{i−1}−δ_{ij})−(1+s_{j})(p_{1j}^{i} +p_{2j}^{i})). (6)

Choosing the integers s_{j} to maximize this lower bound results in the inequal-

ity (2).  ⊓ ⊔

A form of the special case i = 2 of the above bound with slightly weaker assumptions – indeed, the above proof only requires ’distance regularity up to some distance’ – is in Brouwer et al. [1, Proposition 5.8.1].

1.2 Corollary. If

k > a_{1}^{2} + μ(a_{i} + c_{i}) + μ\frac{c_{i}(c_{i} − 1)}{2} max(λ − 1, μ − 1)  (7)

then

c_{i+1} ≥ 1 + (μ − 1)c_{i}.  (8)

Proof. For s_{i−1} = 0, s_{i} = 1, the lower bound (6) for (5) takes the value

2(c_{i}(b_{i−1} −1)−a_{i} −p_{2i}^{i}) = \frac{2}{μ}(k −a_{i}(a_{i} −λ)−μ(a_{i} +c_{i})−b_{i}c_{i+1} +c_{i}(μ−1)b_{i−1}).

(9)

If (8) is violated then c_{i+1} ≤ (μ − 1)c_{i}, hence

−b_{i}c_{i+1} + c_{i}(μ − 1)b_{i−1} ≥ c_{i}(μ − 1)(b_{i−1} − b_{i}) ≥ 0.  (10)

Thus (6) is bounded from below by \frac{2}{μ}(k − a_{i}(a_{i} − λ) − μ(a_{i} + c_{i})), and from above by c_{i}(c_{i} − 1) max(λ − 1, μ − 1), contradicting (6). Therefore (8) must

hold.  ⊓ ⊔

1.3 Corollary. If there are infinitely many distance-regular graphs with fixed λ, μ , a_{i}, and c_{i} containing an induced quadrangle then necessarily c_{i+1} ≥ 1 + (μ − 1)c_{i}. Equality holds, e.g., for dual polar graphs.

Proof. (i) If a distance regular graph contains an induced quadrangle then d ≤ k by the diameter bound of Terwilliger [4] (cf. [1, Corollary 5.2.2]). Now if (8) is violated then k (and therefore d) is bounded by the right hand side of (6). Hence the number of vertices is bounded, too. Thus there are only finitely many possibilities, contradition.

(ii) For dual polar graphs, (1) holds. Hence μ = q+1 and c_{i+1} = 1+(μ−1)c_{i},

so that (8) holds with equality.  ⊓ ⊔

Note that graphs violating (8) satisfy μ > 1. Since there are only three known quadrangle-free distance regular graph with μ > 1 [1, p. 36], the hypothesis about quadrangles is almost certainly superfluous.

It would be interesting if the arguments used in the proofs of the above results could be tightened in such a way that it gives useful geometric information about graphs with c_{i+1} = 1 + (μ − 1)c_{i} and large k. Ideally, one would like to conclude that there are no induced subgraphs K_{1,1,2} (a 4-clique minus an edge); then the standard characterization theorems for Hamming graphs and dual polar graphs (cf. [1, Chapter 9]) apply (unless λ = 0 or μ = 1).

The assumption in (7) is convenient but can be weakened by using the upper bound from (5) and the lower bound from (10) together with b_{i−1} − b_{i} = c_{i} − c_{i−1} + a_{i} − a_{i−1}. In general, this gives a messy expression. However, in the bipartite case, where all a_{i} = 0, it reproduces the following result of Caughman [3].

1.4 Corollary. For a bipartite distance-regular graph,

k > c_{i} + \binom{μ − 1}{2}c_{i}(c_{i} − c_{i−1} − 1) ⇒ c_{i+1} ≥ 1 + (μ − 1)c_{i}.

2 Distance-regular graphs with fixed λ, μ

It is likely that much stronger results than Corollary 1.3 hold, but current techniques do not seem to give a handle for attack. The final goal would be the following conjecture.

Conjecture. For given λ and μ, there are only finitely many distance-regular graphs of diameter > 3 that contain an induced subgraph K_{1,1,2}. Any such graph has diameter d ≤ λ/2 + 1.

Note that the Johnson graphs J(2d, d) have equality in this conjectured diameter bound.

In the remainder of this section, we collect some observations in support of the conjecture. Clearly, the conjecture holds trivially if λ = 0 or μ = 1. For λ > 0, μ > 1, all but finitely many of the known distance regular graphs with diameter d > 3 have parameters of the form either (”classical parameters”)

b_{i} = ([{d \atop 1}] − [{i \atop 1}])(β − α[{i \atop 1}]), c_{i} = [{i \atop 1}](1 + α[{i − 1 \atop 1}]), (11)

with

[{i \atop 1}] = \{ \begin{matrix}i & if q = 1, \\ (q^{i} − 1)/(q − 1) & otherwise \end{matrix}

for some integer q ≠ −1, 0, or (”partition parameters”)

b_{i} = (m − i)(1 + α(m − 1 − i)), c_{i} = i(1 + α(i − 1)) for i < d, (12)
b_{d} = 0, c_{d} = γd(1 + α(d − 1)), (m, γ) ∈ {2d, 2), (2d + 1, 1)}  (13)

(see Chapter 6 of [1]; α, β are not necessarily integers).

If α = 0, the known realizations of these parameter sets with d > 3 are near polygons (Hamming graphs, dual polar spaces, and folded cubes), which have no K_{1,1,2}. We investigate the case α ≠ 0.

2.1 Proposition. A distance-regular graph with partition parameters (12),

(13) and α ≠ 0 has diameter d ≤ \frac{1}{4}(λ + 2), valency k ≤ \frac{1}{4}(λ + 2)^{2}, and μ ≥ 4. In particular, given λ, there are only finitely many possibilities.

Proof. We have

k = b_{0} = m + αm(m − 1), λ = k − 1 − b_{1} = 2α(m − 1), μ = 2 + 2α. (14)

The cases μ ∈ {1, 3} are impossible by Bussemaker & Neumaier [2, Theorem 3.3], and μ ≠ 2 since α ≠ 0. Hence μ ≥ 4, α ≥ 1, m ≤ 1 + λ/2,

d ≤ m/2 ≤ (λ + 2)/4, and k = m(1 + λ/2) ≤ (λ + 2)^{2}/4.  ⊓ ⊔

The realizations of partition parameters are classified in [2], apart from finitely many undecided cases.

2.2 Proposition. A distance regular graph of diameter d ≥ 3 with classical parameters (11) has

c_{i} = [{i \atop 1}] + κ[{i \atop 2}], a_{i} = [{i \atop 1}](λ − κ[{i − 1 \atop 1}]) = [{i \atop 1}]λ − κ(q + 1)[{i \atop 2}], (15)
k = a_{d} + c_{d} = [{d \atop 1}](λ + 1) − κq[{d \atop 2}]  (16)

for some integer κ ≥ 0, where

[{i \atop 2}] = \{ \begin{matrix}i(i − 1)/2 & if q = 1, \\ (q^{i} − 1)(q^{i−1} − 1)/(q^{2} − 1)(q − 1) & otherwise. \end{matrix}

Proof. κ := α(q+1) = μ−1−q is an integer, and the formulas follow directly from b_{d} = 0, k = b_{0}, λ = k − 1 − b_{1}. Since 0 < c_{3} = (q^{2} + q + 1)(1 + κ), we

have κ > −1, hence κ is nonnegative.  ⊓ ⊔

Note that [{i \atop 1}] and [{i \atop 2}] are integers, and [{i \atop 2}] > 0 for i > 1. We have κ = 0 iff α = 0, and κ > 0 otherwise.

2.3 Proposition. If a distance-regular graph with classical parameters contains an induced subgraph K_{1,1,2} then either κ = 0 or

0 < q ≤ μ − 2, d ≤ λ/2 + 1.

In particular, given λ and μ, there are only finitely many possibilities with κ ≠ 0.

Proof. Suppose that κ ≠ 0. Then κ > 0 and q = μ−1−κ ≤ μ−2. Moreover,

λ ≥ κ \left[{d − 1 \atop 1}\right] ,  (17)

since 0 ≤ a_{d} = [{d \atop 1}](λ − κ[{d−1 \atop 1}]). If q < 0 then Terwilliger [5] proved the absence of subgraphs K_{1,1,2}; hence q > 0.

If q = 1, the graphs are classified [1, Theorem 6.1.1], giving κ = 2α ∈ {0, 2, 4, 8}; hence λ ≥ 2d − 2 by (17). If q > 1, d ≥ 3 then (17) implies λ ≥ 2d − 2 except when d = 3, q = 1, κ = 1, λ = 3. This would correspond to an intersection array {14, 10, 4; 1, 4, 14}, which is not feasible. Finally, if q > 1, d ≤ 2 then λ ≥ 2d − 2 holds since the existence of a K_{1,1,2} implies λ ≥ 2.

Hence λ ≥ 2d − 2 holds generally, giving d ≤ λ/2 + 1.  ⊓ ⊔

As Table 6.6 of [1] shows, there are several infinite families of regular near polygons with fixed λ, μ (and indeed with fixed a_{1}, … a_{s}, c_{1}, …, c_{s}), among then the known graphs with classical parameters and κ = 0. The graphs with classical parameters and κ = 0 containing no K_{1,1,2} must be regular near polygons [1, Theorem 6.4.1], and are completely classified for λ > 0 ([1, Theorem 9.4.4]).

The graphs with classical parameters and q = −r < 0 also contain such infinite families. For d > 3, λ > 0, μ > 1, they have been nearly classified by Weng [6], who showed that in this case

κ = s(r + 1), λ = s − 1, μ = κ + 1 − r

for some prime power r and some positive integer

s ∈ {r, r − 1, (r + 1)/2}.

The first two cases are realized uniquely by dual polar graphs ^{2}A_{2d−1}(r) and Hermitian forms graphs Her_{r}(d), while the third case is apparently open. For λ = 0 or μ = 1 little is known, but Weng [7] showed that for d > 3, μ = 1, 1 < λ < r − 1 is impossible.

For d ≤ 3, the situation seems to be different. I haven’t looked at the diameter three case, but for strongly regular graphs (d = 2) one finds the following.

2.4 Proposition. If there are infinitely many connected strongly regular graphs with fixed λ, μ then one of the following three cases holds:

(i) λ = μ − 2,

(ii) μ = t^{2}, λ = t^{2} ± 2t for some t > 0,

(iii) μ = t^{2} ± t, λ = t^{2} ± 3t for some t > 0.

Proof. If we have a conference graph then v = 4μ+1 is fixed, so that there are only finitely many choices. Otherwise, cf. [1, Theorem 1.3.1], the eigenvalues r, s are integral, and the parameters are determined by μ, r, s as

k = μ − rs, λ = μ + r + s.

Then

(s + 1)k(k − s) ≡ 0 mod n := r − s,

since the multiplicity f must be an integer. It follows that

λ − μ ≡ 2r ≡ 2s mod n, (λ − μ)^{2} ≡ 4(μ − k) mod n,

and hence

\begin{matrix}(λ − μ + 2)(4μ − (λ − μ)^{2})(4μ − (λ − μ)^{2} − 2(λ − μ)) \\ ≡ (2s + 2)4k(4k − 4s) ≡ 0 mod n. \end{matrix}

If the left hand side is nonzero, this leaves only finitely many choices for n, hence of r = \frac{1}{2}(λ − μ + n) and s = \frac{1}{2}(λ − μ − n), and hence only finitely many graphs. If the left hand side vanishes, one of the factors vanishes, giving the

three cases (i)–(iii).  ⊓ ⊔

Note that every connected strongly regular graph is classical in two ways, realized by any of the two settings

q = −1 − s > 0, κ = μ + s,
q = −1 − r < 0, κ = μ + r.

The case κ = 0 corresponds to s = −μ, r = λ, which defines pseudo generalized quadrangles.

References

[1] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer, Berlin 1989.

[2] F.C. Bussemaker and A. Neumaier, Exceptional graphs with smallest eigenvalue −2 and related problems, Math. Comput. 59 (1992), 583– 608.

[3] J. Caughman, Intersection numbers of bipartite distance-regular graphs, Discrete Math. 163 (1997), 235–241.

[4] P. Terwilliger, Distance-regular graphs with girth 3 and 4, I, J. Combin. Th. (B) 39 (1985), 265–281.

[5] P. Terwilliger, Kite-free distance-regular graphs, Europ. J. Combinatorics 16 (1995), 405–414.

[6] C. Weng, Classical distance-regular graphs of negative type, J. Combin. Theory B 76 (1999), 93–116.

[7] C. Weng, D-bounded distance-regular graphs, Europ. J. Combinatorics 18 (1997), 211–229.