Séminaire Lotharingien de Combinatoire 53 (2006), Article B53g

ON DEGREES IN THE HASSE DIAGRAM OF THE STRONG BRUHAT ORDER

RON M. ADIN^{1} AND YUVAL ROICHMAN^{1}

Abstract. For a permutation π in the symmetric group S_{n} let the total degree be its valency in the Hasse diagram of the strong Bruhat order on S_{n}, and let the down degree be the number of permutations which are covered by π in the strong Bruhat order. The maxima of the total degree and the down degree and their values at a random permutation are computed. Proofs involve variants of a classical theorem of Turán from extremal graph theory.

1. The Down, Up and Total Degrees

Definition 1.1. For a permutation π ∈ S_{n} let the down degree d_{−}(π) be the number of permutations in S_{n} which are covered by π in the strong Bruhat order. Let the up degree d_{+}(π) be the number of permutations which cover π in this order. The total degree of π is the sum

d(π) := d_{−}(π) + d_{+}(π),

i.e., the valency of π in the Hasse diagram of the strong Bruhat order.

Explicitly, for 1 ≤ a < b ≤ n let t_{a,b} = t_{b,a} ∈ S_{n} be the transposition interchanging a and b, and for π ∈ S_{n} let

ℓ(π) := min{k | π = s_{i_{1}}s_{i_{2}} ⋯ s_{i_{k}}}

be the length of π with respect to the standard Coxeter generators s_{i} = t_{i,i+1} (1 ≤ i < n) of S_{n}. Then

d_{−}(π) = #{t_{a,b} | ℓ(t_{a,b}π) = ℓ(π) − 1},
d_{+}(π) = #{t_{a,b} | ℓ(t_{a,b}π) = ℓ(π) + 1},
d(π) = d_{−}(π) + d_{+}(π) = #{t_{a,b} | ℓ(t_{a,b}π) = ℓ(π) ± 1}.

1Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan

52900, Israel. Email: radin@math.biu.ac.il, yuvalr@math.biu.ac.il.

The Research of both authors was supported in part by the Israel Science Foundation, founded by the Israel Academy of Sciences and Humanities, and by the EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe,” grant HPRN-CT-2001-00272.

For the general definitions and other properties of the weak and strong Bruhat orders see, e.g., [9, Ex. 3.75] and [2, §§2.1, 3.1].

We shall describe π ∈ S_{n} by its sequence of values [π(1), …, π(n)].

Observation 1.2. π covers σ in the strong Bruhat order on S_{n} if and only if there exist 1 ≤ i < k ≤ n such that

(1) b := π(i) > π(k) =: a.

(2) σ = t_{a,b}π, i.e., π = […, b, …, a, …] and σ = […, a, …, b, …].

(3) There is no i < j < k such that a < π(j) < b.

Corollary 1.3. For every π ∈ S_{n}

d_{−}(π) = d_{−}(π^{−1}).

Example 1.4. In S_{3}, d_{−}[123] = 0, d_{−}[132] = d_{−}[213] = 1, and d_{−}[321] = d_{−}[231] = d_{−}[312] = 2. On the other hand, d[321] = d[123] = 2 and d[213] = d[132] = d[312] = d[231] = 3.

Remark 1.5. The classical descent number of a permutation π in the symmetric group S_{n} is the number of permutations in S_{n} which are covered by π in the (right) weak Bruhat order. Thus, the down degree may be considered as a “strong descent number”.

Definition 1.6. For π ∈ S_{n} denote

D_{−}(π) := {t_{a,b} | ℓ(t_{a,b}π) = ℓ(π) − 1},

the strong descent set of π.

Example 1.7. The strong descent set of π = [7, 9, 5, 2, 3, 8, 4, 1, 6] is

D_{−}(π) = {t_{1,2}, t_{1,3}, t_{1,4}, t_{2,5}, t_{3,5}, t_{4,5}, t_{4,8}, t_{5,7}, t_{5,9}, t_{6,7}, t_{6,8}, t_{8,9}}.

Remark 1.8. Generalized pattern avoidance, involving strong descent sets, was applied by Woo and Yong [11] to determine which Schubert varieties are Gorenstein.

Proposition 1.9. The strong descent set D_{−}(π) uniquely determines the permutation π.

Proof. By induction on n. The claim clearly holds for n = 1.

Let π be a permutation in S_{n}, and let π̄ ∈ S_{n−1} be the permutation obtained by deleting the value n from π. Note that, by Observation 1.2,

D_{−}(π̄) = D_{−}(π) \ {t_{a,n} | 1 ≤ a < n}.

By the induction hypothesis π̄ is uniquely determined by this set. Hence it suffices to determine the position of n in π.

DEGREES IN THE HASSE DIAGRAM OF THE STRONG BRUHAT ORDER 3

Now, if j := π^{−1}(n) < n then clearly t_{π(j+1),n} ∈ D_{−}(π). Moreover, by Observation 1.2, t_{a,n} ∈ D_{−}(π) ⟹ a ≥ π(j + 1). Thus D_{−}(π) determines

π̄(j) = π(j + 1) = min{a | t_{a,n} ∈ D_{−}(π)},

and therefore determines j. Note that this set of a’s is empty if and only if j = n. This completes the proof. □

2. Maximal Down Degree

In this section we compute the maximal value of the down degree on S_{n} and find all the permutations achieving the maximum. We prove

Proposition 2.1. For every positive integer n

max{d_{−}(π)| π ∈ S_{n}} = ⌊n^{2}/4⌋.

Remark 2.2. The same number appears as the order dimension of the strong Bruhat poset [7]. An upper bound on the maximal down degree for finite Coxeter groups appears in [4, Prop. 3.4].

For the proof of Proposition 2.1 we need a classical theorem of Turán.

Definition 2.3. Let r ≤ n be positive integers. The Turán graph T_{r}(n) is the complete r-partite graph with n vertices and all parts as equal in size as possible, i.e., each size is either ⌊n/r⌋ or ⌈n/r⌉. Denote by t_{r}(n) the number of edges of T_{r}(n).

Theorem 2.4 (Turán’s Theorem; [10], [3, IV, Theorem 8]).

(1) Every graph of order n with more than t_{r}(n) edges contains a complete subgraph of order r + 1.

(2) T_{r}(n) is the unique graph of order n with t_{r}(n) edges that does not contain a complete subgraph of order r + 1.

We shall apply the special case r = 2 (due to Mantel) of Turán’s theorem to the following graph.

Definition 2.5. The strong descent graph of π ∈ S_{n}, denoted Γ_{−}(π), is the undirected graph whose set of vertices is {1, …, n} and whose set of edges is

{{a, b} | t_{a,b} ∈ D_{−}(π)}.

By definition, the number of edges in Γ_{−}(π) equals d_{−}(π).

Remark 2.6. Permutations for which the strong descent graph is connected are called indecomposable. Their enumeration was studied in [5]; see [6, pp. 7–8]. The number of components in Γ_{−}(π) is equal to the number of global descents in πw_{0} (where w_{0} := [n, n − 1, …, 1]), which were introduced and studied in [1, Corollaries 6.3 and 6.4].

Lemma 2.7. For every π ∈ S_{n}, the strong descent graph Γ_{−}(π) is triangle-free.

Proof. Assume that Γ_{−}(π) contains a triangle. Then there exist 1 ≤ a < b < c ≤ n such that t_{a,b}, t_{a,c}, t_{b,c} ∈ D_{−}(π). By Observation 1.2,

t_{a,b}, t_{b,c} ∈ D_{−}(π) ⟹ π^{−1}(c) < π^{−1}(b) < π^{−1}(a) ⟹ t_{a,c} ∉ D_{−}(π).

This is a contradiction. □

Proof of Proposition 2.1. By Theorem 2.4(1) together with Lemma 2.7, for every π ∈ S_{n}

d_{−}(π) ≤ t_{2}(n) = ⌊n^{2}/4⌋.

Equality holds since

d_{−}([⌊n/2⌋ + 1, ⌊n/2⌋ + 2, …, n, 1, 2, …, ⌊n/2⌋]) = ⌊n^{2}/4⌋.

□

Next we classify (and enumerate) the permutations which achieve the maximal down degree.

Lemma 2.8. Let π ∈ S_{n} be a permutation with maximal down degree. Then π has no decreasing subsequence of length 4.

Proof. Assume that π = [… d … c … b … a …] with d > c > b > a and π^{−1}(a) − π^{−1}(d) minimal. Then t_{a,b}, t_{b,c}, t_{c,d} ∈ D_{−}(π) but, by Observation 1.2, t_{a,d} ∉ D_{−}(π). It follows that Γ_{−}(π) is not a complete bipartite graph, since {a, b}, {b, c}, and {c, d} are edges but {a, d} is not. By Lemma 2.7, combined with Theorem 2.4(2), the number of edges in Γ_{−}(π) is less than ⌊n^{2}/4⌋. □

Proposition 2.9. For every positive integer n

#\{π ∈ S_{n} | d_{−}(π) = ⌊n^{2}/4⌋\} = \begin{cases}n, & if n is odd; \\ n/2, & if n is even. \end{cases}

Each such permutation has the form

π = [t + m + 1, t + m + 2, …, n, t + 1, t + 2, …, t + m, 1, 2, …, t],

where m ∈ {⌊n/2⌋, ⌈n/2⌉} and 1 ≤ t ≤ n − m. Note that t = n − m (for m) gives the same permutation as t = 0 (for n − m instead of m).

Proof. It is easy to verify the claim for n ≤ 3. Assume n ≥ 4.

Let π ∈ S_{n} with d_{−}(π) = ⌊n^{2}/4⌋. By Theorem 2.4(2), Γ_{−}(π) is isomorphic to the complete bipartite graph K_{⌊n/2⌋,⌈n/2⌉}. Since n ≥ 4, each side of the graph contains at least two vertices. Let 1 = a < b be two vertices on one side, and c < d two vertices on the other side of the graph. Since t_{b,c}, t_{b,d} ∈ D_{−}(π), there are three possible cases:

(1) b < c, and then π = [… c … d … b …] (since π = [… d … c … b …] contradicts t_{b,d} ∈ D_{−}(π)).

(2) c < b < d, and then π = [… d … b … c …].

(3) d < b, and then π = [… b … c … d …] (since π = [… b … d … c …] contradicts t_{b,c} ∈ D_{−}(π)).

The same also holds for a = 1 instead of b, but then cases 2 and 3 are impossible since a = 1 < c. Thus necessarily c appears before d in π, and case 2 is therefore impossible for any b on the same side as a = 1. In other words: no vertex on the same side as a = 1 is intermediate, either in position (in π) or in value, to c and d.

Assume now that n is even. The vertices not on the side of 1 form (in π) a block of length n/2 of numbers which are consecutive in value as well in position. They also form an increasing subsequence of π, since Γ_{−}(π) is bipartite. The numbers preceding them are all larger in value, and are increasing; the numbers succeeding them are all smaller in value, are increasing, and contain 1. It is easy to check that each permutation π of this form has maximal d_{−}(π). Finally, π is completely determined by the length 1 ≤ t ≤ n/2 of the last increasing subsequence.

For n odd one obtains a similar classification, except that the length of the side not containing 1 is either ⌊n/2⌋ or ⌈n/2⌉. This completes the proof. □

3. Maximal Total Degree

Obviously, the maximal value of the total degree d = d_{−} +d_{+} cannot exceed \binom{n}{2}, the total number of transpositions in S_{n}. This is slightly better than the bound 2⌊n^{2}/4⌋ obtainable from Proposition 2.1. The actual maximal value is smaller.

Theorem 3.1. For n ≥ 2, the maximal total degree in the Hasse diagram of the strong Bruhat order on S_{n} is

⌊n^{2}/4⌋ + n − 2.

In order to prove this result, associate with each permutation π ∈ S_{n} a graph Γ(π), whose set of vertices is {1, …, n} and whose set of edges is

{{a, b} | ℓ(t_{a,b}π) − ℓ(π) = ±1}.

This graph has many properties; e.g., it is K_{5}-free and is the edgedisjoint union of two triangle-free graphs on the same set of vertices. However, these properties are not strong enough to imply the above result. A property which does imply it is the following bound on the minimal degree.

Lemma 3.2. There exists a vertex in Γ(π) with degree at most ⌊n/2⌋ + 1.

Proof. Assume, on the contrary, that each vertex in Γ(π) has at least ⌊n/2⌋ + 2 neighbors. This applies, in particular, to the vertex π(1). Being the first value of π, the neighborhood of π(1) in Γ(π), viewed as a subsequence of [π(2), …, π(n)], consists of a shuffle of a decreasing sequence of numbers larger than π(1) and an increasing sequence of numbers smaller than π(1). Let a be the rightmost neighbor of π(1). The intersection of the neighborhood of a with the neighborhood of π(1) is of cardinality at most two. Thus the degree of a is at most

n − (⌊n/2⌋ + 2) + 2 = ⌈n/2⌉ ≤ ⌊n/2⌋ + 1,

which is a contradiction. □

Proof of Theorem 3.1. First note that, by definition, the total degree of π ∈ S_{n} in the Hasse diagram of the strong Bruhat order is equal to the number of edges in Γ(π). We will prove that this number e(Γ(π)) ≤ ⌊n^{2}/4⌋ + n − 2, by induction on n.

The claim is clearly true for n = 2. Assume that the claim holds for n − 1, and let π ∈ S_{n}. Let a be a vertex of Γ(π) with minimal degree, and let π̄ ∈ S_{n−1} be the permutation obtained from π by deleting the value a (and decreasing by 1 all the values larger than a). Then

e(Γ(π̄)) ≥ e(Γ(π) \ a),

where the latter is the number of edges in Γ(π) which are not incident with the vertex a. By the induction hypothesis and Lemma 3.2,

e(Γ(π)) = e(Γ(π) \ a) + d(a) ≤ e(Γ(π̄)) + d(a)
≤ ⌊(n − 1)^{2}/4⌋ + (n − 1) − 2 + ⌊n/2⌋ + 1
= ⌊n^{2}/4⌋ + n − 2.

Equality holds since, letting m := ⌊n/2⌋,

e(Γ([m + 1, m + 2, …, n, 1, 2, …, m])) = ⌊n^{2}/4⌋ + n − 2.
□

Theorem 3.3.

#\{π ∈ S_{n} | d(π) = ⌊n^{2}/4⌋ + n − 2\} = \begin{cases}2, & if n = 2; \\ 4, & if n = 3 or n = 4; \\ 8, & if n ≥ 6 is even; \\ 16, & if n ≥ 5 is odd. \end{cases}

The extremal permutations have one of the following forms:

π_{0} := [m + 1, m + 2, …, n, 1, 2, …, m] (m ∈ {⌊n/2⌋, ⌈n/2⌉}),

and the permutations obtained from π_{0} by one or more of the following operations:

π ↦ π^{r} := [π(n), π(n − 1), …, π(2), π(1)]  (reversing π),
π ↦ π^{s} := π · t_{1,n}  (interchanging π(1) and π(n)),
π ↦ π^{t} := t_{1,n} · π  (interchanging 1 and n in π).

Proof. It is not difficult to see that all the specified permutations are indeed extremal, and their number is as claimed (for all n ≥ 2).

The claim that there are no other extremal permutations will be proved by induction on n. For small values of n (say n ≤ 4) this may be verified directly. Assume now that the claim holds for some n ≥ 4, and let π ∈ S_{n+1} be extremal. Following the proof of Lemma 3.2, let a be a vertex of Γ(π) with degree at most ⌊(n + 1)/2⌋ + 1, which is either π(1) or its rightmost neighbor. As in the proof of Theorem 3.1, let π̄ ∈ S_{n} be the permutation obtained from π by deleting the value a (and decreasing by 1 all the values larger than a). All the inequalities in the proof of Theorem 3.1 must hold as equalities, namely: e(Γ(π)\a) = e(Γ(π̄)), d(a) = ⌊(n + 1)/2⌋ + 1, and π̄ is extremal in S_{n}. By the induction hypothesis, π̄ must have one of the prescribed forms. In all of them, {π̄(1), π̄(n)} = {m, m + 1} is an edge of Γ(π̄). Therefore the corresponding edge {π(1), π(n + 1)} (or {π(2), π(n + 1)} if a = π(1), or {π(1), π(n)} if a = π(n + 1)) is an edge of Γ(π) \ a, namely of Γ(π). If a ≠ π(1), π(n + 1) then π(n + 1) is the rightmost neighbor of π(1), contradicting the choice of a. If a = π(n+1) we may use the operation π ↦ π^{r}. Thus we may assume from now on that a = π(1).

Let N(a) denote the set of neighbors of a in Γ(π). Assume first that

π̄ = π_{0} = [m + 1, m + 2, …, n, 1, 2, …, m] (m ∈ {⌊n/2⌋, ⌈n/2⌉}).

Noting that ⌈n/2⌉ = ⌊(n + 1)/2⌋ and keeping in mind the decrease in certain values during the transition π ↦ π̄, we have the following cases:

(1) a > m + 1 : in this case 1, …, m ∉ N(a), so that

d(a) ≤ n − m ≤ ⌈n/2⌉ = ⌊(n + 1)/2⌋ < ⌊(n + 1)/2⌋ + 1.

Thus π is not extremal.

(2) a < m : in this case m + 3, …, n + 1, m + 1 ∉ N(a), so that

d(a) ≤ 1 + (m − 1) ≤ ⌈n/2⌉ < ⌊(n + 1)/2⌋ + 1.

Again, π is not extremal.

(3) a ∈ {m, m + 1} : in this case

d(a) = 1 + m ≤ ⌊(n + 1)/2⌋ + 1,

with equality iff m = ⌊(n + 1)/2⌋. This gives π ∈ S_{n+1} of the required form (either π_{0} or π_{0}^{s}).

A similar analysis for π̄ = π_{0}^{s} gives extremal permutations only for a ∈ {m + 1, m + 2} and d(a) = 3, so that n = 4 and π̄ = [2413] ∈ S_{4}. The permutations obtained are π = [32514] and π = [42513], which are π_{0}^{rt}, π_{0}^{rst} ∈ S_{5}, respectively.

The other possible values of π̄ are obtained by the π ↦ π^{r} and π ↦ π^{t} operations from the ones above, and yield analogous results. □

4. Expectation

In this subsection we prove an exact formula for the expectation of the down degree of a permutation in S_{n}.

Theorem 4.1. For every positive integer n, the expected down degree of a random permutation in S_{n} is

E_{π∈S_{n}}[d_{−}(π)] = ∑_{i=2}^{n} ∑_{j=2}^{i} ∑_{k=2}^{j} \frac{1}{i · (k − 1)} = (n + 1) ∑_{i=1}^{n} \frac{1}{i} − 2n.

It follows that

Corollary 4.2. As n → ∞,

E_{π∈S_{n}}[d_{−}(π)] = n ln n + O(n)

and

E_{π∈S_{n}}[d(π)] = 2n ln n + O(n).

To prove Theorem 4.1 we need some notation. For π ∈ S_{n} and 2 ≤ i ≤ n let π_{|i} be the permutation obtained from π by omitting all letters which are larger than or equal to i. For example, if π = [6, 1, 4, 8, 3, 2, 5, 9, 7] then π_{|9} = [6, 1, 4, 8, 3, 2, 5, 7], π_{|7} = [6, 1, 4, 3, 2, 5], and π_{|4} = [1, 3, 2].

Also, denote by π^{|j} the suffix of length j of π. For example, if π = [6, 1, 4, 8, 3, 2, 5, 9, 7] then π^{|3} = [5, 9, 7] and π_{|4}^{|2} = [3, 2].

Let l.t.r.m.(π) be the number of left-to-right maxima in π:

l.t.r.m.(π) := #{i | π(i) = max_{1≤j≤i} π(j)}

Lemma 4.3. For every π ∈ S_{n}, if π_{|i+1}^{−1}(i) = j then

d_{−}(π_{|i+1}) − d_{−}(π_{|i}) = l.t.r.m.(π_{|i}^{|i−j}).

Proof of Theorem 4.1. Clearly, for every π ∈ S_{n}

d_{−}(π) = ∑_{i=2}^{n} [d_{−}(π_{|i+1}) − d_{−}(π_{|i})] .

Thus, by Lemma 4.3,

d_{−}(π) = ∑_{i=2}^{n} l.t.r.m.(π_{|i}^{|i−j_{i}}),

where j_{i} is the position of i in π_{|i+1}, i.e., j_{i} := π_{|i+1}^{−1}(i).

Define a random variable X to be the down degree d_{−}(π) of a random (uniformly distributed) permutation π ∈ S_{n}. Then, for each 2 ≤ i ≤ n, π_{|i+1} is a random (uniformly distributed) permutation in S_{i}, and therefore j = π_{|i+1}^{−1}(i) is uniformly distributed in {1, …, i} and π_{|i+1}^{|i−j} is essentially a random (uniformly distributed) permutation in S_{i−j} (after monotonically renaming its values). Therefore, by linearity of the expectation,

(1)  E[X] = ∑_{i=2}^{n} \frac{1}{i} ∑_{j=1}^{i} E[X_{i−j}] = ∑_{i=2}^{n} \frac{1}{i} ∑_{t=0}^{i−1} E[X_{t}],

where X_{t} := l.t.r.m.(σ) for a random σ ∈ S_{t}.

Recall from [9, Corollary 1.3.8] that

∑_{σ∈S_{t}} q^{l.t.r.m.(σ)} = ∏_{k=1}^{t}(q + k − 1).

It follows that, for t ≥ 1,

E[X_{t}] = \frac{1}{t!} ∑_{σ∈S_{t}} l.t.r.m.(σ) = \frac{1}{t!} (\frac{d}{dq} ∑_{σ∈S_{t}} q^{l.t.r.m.(σ)})|_{q=1}

= \frac{1}{t!} (\frac{d}{dq} ∏_{k=1}^{t}(q + k − 1))|_{q=1} = \frac{1}{t!} ∑_{r=1}^{t}_{∏_{1≤k≤t} ; k≠r}k = ∑_{r=1}^{t} \frac{1}{r}.

Of course, E[X_{0}] = 0. Substituting these values into (1) gives

E[X] = ∑_{i=2}^{n} ∑_{t=1}^{i−1} ∑_{r=1}^{t} \frac{1}{i · r}

and this is equivalent (with j = t+1 and k = r +1) to the first formula in the statement of the theorem.

The second formula may be obtained through the following manipulations:

E[X] = ∑_{i=2}^{n} ∑_{j=2}^{i} ∑_{k=2}^{j} \frac{1}{i · (k − 1)} = ∑_{2≤k≤j≤i≤n} \frac{1}{i · (k − 1)}

= ∑_{2≤k≤i≤n} \frac{i − k + 1}{i · (k − 1)} = ∑_{2≤k≤i≤n} (\frac{1}{k − 1} − \frac{1}{i})

= ∑_{2≤k≤n} \frac{n − k + 1}{k − 1} − ∑_{2≤i≤n} \frac{i − 1}{i}

= n ∑_{k=2}^{n} \frac{1}{k − 1} − (n − 1) − (n − 1) + ∑_{i=2}^{n} \frac{1}{i}

= n ∑_{i=1}^{n} \frac{1}{i} − 2n + ∑_{i=1}^{n} \frac{1}{i}.

□

Proof of Corollary 4.2. Notice that

∑_{i=1}^{n} \frac{1}{i} = ln n + O(1).

(The next term in the asymptotic expansion is Euler’s constant.) Substitute into Theorem 4.1 to obtain the desired result. □

5. Generalized Down Degrees

Definition 5.1. For π ∈ S_{n} and 1 ≤ r < n let

D_{−}^{(r)}(π) := {t_{a,b}| ℓ(π) > ℓ(t_{a,b}π) > ℓ(π) − 2r}

the r-th strong descent set of π.

Define the r-th down degree as

d_{−}^{(r)}(π) := #D_{−}^{(r)}(π).

Example 5.2. The first strong descent set and down degree are those studied in the previous section; namely, D_{−}^{(1)}(π) = D_{−}(π) and d_{−}^{(1)}(π) = d_{−}(π).

The (n − 1)-th strong descent set is the set of inversions:

D_{−}^{(n−1)}(π) = {t_{a,b} | a < b, π^{−1}(a) > π^{−1}(b)}.

Thus

d_{−}^{(n−1)}(π) = inv(π),

the inversion number of π.

Observation 5.3. For every π ∈ S_{n} and 1 ≤ a < b ≤ n, t_{a,b} ∈ D_{−}^{(r)}(π) if and only if π = […, b, …, a, …] and there are less than r letters between the positions of b and a in π whose value is between a and b.

Example 5.4. Let π = [7, 9, 5, 2, 3, 8, 4, 1, 6]. Then

D_{−}^{(1)}(π) = {t_{6,7}, t_{6,8}, t_{1,4}, t_{1,3}, t_{1,2}, t_{4,8}, t_{4,5}, t_{8,9}, t_{3,5}, t_{2,5}, t_{5,9}, t_{5,7}}

and

D_{−}^{(2)}(π) = D_{−}^{(1)}(π) ∪ {t_{6,9}, t_{1,8}, t_{4,9}, t_{4,7}, t_{3,9}, t_{3,7}, t_{2,9}, t_{2,7}}.

Corollary 5.5. For every π ∈ S_{n} and 1 ≤ r < n

d_{−}^{(r)}(π) = d_{−}^{(r)}(π^{−1}).

Proof. By Observation 5.3, t_{a,b} ∈ D_{−}^{(r)}(π) if and only if t_{π^{−1}(a),π^{−1}(b)} ∈ D_{−}^{(r)}(π^{−1}). □

Definition 5.6. The r-th strong descent graph of π ∈ S_{n}, denoted Γ_{−}^{(r)}(π), is the graph whose set of vertices is {1, …, n} and whose set of edges is

{{a, b}| t_{a,b} ∈ D_{−}^{(r)}(π)}.

The following lemma generalizes Lemma 2.7.

Lemma 5.7. For every π ∈ S_{n}, the graph Γ_{−}^{(r)}(π) contains no subgraph isomorphic to the complete graph K_{r+2}.

Proof. Assume that there is a subgraph in Γ_{−}^{(r)}(π) isomorphic to K_{r+2}. Then there exists a decreasing subsequence

n ≥ a_{1} > a_{2} > ⋯ > a_{r+2} ≥ 1

such that for all 1 ≤ i < j ≤ r + 2, t_{a_{i},a_{j}} are r-th strong descents of π. In particular, for every 1 ≤ i < r + 2, t_{a_{i},a_{i+1}} are r-th strong descents of π. This implies that, for every 1 ≤ i < r + 2, a_{i+1} appears to the right of a_{i} in π. Then, by Observation 5.3, t_{a_{1},a_{r+2}} is not an r-th strong descent. Contradiction. □

Corollary 5.8. For every 1 ≤ r < n,

max\{d_{−}^{(r)}(π) | π ∈ S_{n}\} ≤ t_{r+1}(n) ≤ \binom{r + 1}{2} (\frac{n}{r + 1})^{2} .

Proof. Combining Turán’s Theorem together with Lemma 5.7. □

Note that for r = 1 and r = n − 1 equality holds in Corollary 5.8.

Remark 5.9. For every π ∈ S_{n} let π̄ be the permutation obtained from π by omitting the value n. If j is the position of n in π then

d_{−}^{(r)}(π) − d_{−}^{(r)}(π̄)

equals the number of (r − 1)-th almost left-to-right minima in the (j − 1)-th suffix of π̄, see e.g. [8]. This observation may be applied to calculate the expectation of d_{−}^{(r)}(π).

Acknowledgements. The concept of strong descent graph came up during conversations with Francesco Brenti. Its name and certain other improvements were suggested by Christian Krattenthaler. Thanks also to Nathan Reading, Amitai Regev, Alexander Yong, and the anonymous referees.

References

[1] M. Aguiar and F. Sottile, Structure of the Malvenuto-Reutenauer Hopf algebra of permutations, arχiv:math.CO/0203282.

[2] A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics 231, Springer, New York, 2005.

[3] B. Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer, New York, 1998.

[4] F. Brenti, Upper and lower bounds for Kazhdan-Lusztig polynomials, Europ. J. Combin. 19 (1998), 283–297.

[5] L. Comtet, Sur les coefficients de l’inverse de la série formelle ∑ n!t^{n}, Compt. Rend. Acad. Sci. Paris A-B 275 (1972), A569–A572.

[6] I. M. Gessel and R. P. Stanley, Algebraic Enumeration, in: Handbook of Combinatorics, Vol. 2, Eds. R. Graham et al., M.I.T. Press, 1995.

[7] N. Reading, Order dimension, strong Bruhat order and lattice properties for posets, Order 19 (2002), 73–100.

[8] A. Regev and Y. Roichman, Generalized statistics on S_{n} and pattern avoidance, Europ. J. Combin. 26 (2005), 29–57.

[9] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[10] P. Turán, An extremal problem in graph theory (Hungarian), Mat. Fiz. Lapok 48 (1941), 436–452.

[11] A. Woo and A. Yong, When is a Schubert variety Gorenstein?, Adv. in

Math. (to appear); arχiv:math.AG/0409490.