Let DnkE, DBknE, and DDknE be the Eulerian numbers in the types A, B, and D, respectively-that is, number of permutations of n elements with k descents, the number of signed permutations (of n elements) with k type B descents, the number of even signed permutations (of n elements) with k type DBknE tk, and Dn(t) = Pkn=0 DDknE tk. and of Stembridge's identity
Bn(t2) = (1 + t)n+1Sn(t) 2ntSn(t2) .
Dn(t) = Bn(t) n2n 1tSn 1(t) .
representation we establish a bijective correspondence between even signed permutations and pairs (w, E) with ([n], E) a threshold graph and w a degree ordering of ([n], E). 1 Introduction For n 0, we use [n] for the set { 1, . . . , n } and Sn for the set of permutations of n-elements—that is, bijections of [n]. We write a permutation w 2 Sn as a word w1w2 . . . wn with wi 2 [n] and wi 6= wj for i 6= j. A descent of w 2 Sn is an index (or position) i 2 [n 1] such that wi > wi+1. The Eulerian number DnkE counts the number of permutations w 2 Sn that have k descent positions. This is, of course, one among the many interpretations that we can give to these numbers, see e.g. [14]. The given interpretation is closely related to order theory. Let us recall that the set Sn can be endowed with a lattice structure, see e.g. [11, 6]. The lattice Sn is known under the name of Permutohedron or weak (Bruhat) order. Exploiting the bijection between descent positions and lower covers of w 2 Sn, the Eulerian number DnkE counts the number of permutations w 2 Sn with k lower covers. In particular, Dn1E = 2n n 1 is the number of join-irreducible elements in Sn. A subtler order-theoretic interpretation is given in [2]: since the Sn are (join-)semidistributive as lattices, every element can be written canonically as the join of join-irreducible elements [9]; the numbers DnkE counts then the permutations w 2 Sn that can be written canonically as the join of k join-irreducible elements.
The symmetric groups Sn are particular instances of Coxeter groups, see [4]. Under the usual classification of finite Coxeter groups, the symmetric group Sn yields a concrete model for the Coxeter group An 1 in the family A. Similarly to the symmetric groups, notions of length, descent, and inversion, and a weak order as well, can be defined for elements of an arbitrary Coxeter group [3]. We move our focus to the families B and D of Coxeter groups. More precisely, this paper concerns the Eulerian numbers in the types B and D. The Eulerian number DBknE (resp., DDknE) counts the number of elements in the group Bn (resp., Dn) with k descent positions. Order-theoretic interpretations of these numbers, analogous to the ones mentioned for the standard Eulerian numbers, are still valid. As the abstract group An 1 has a concrete realization as the symmetric group Sn, the group Bn (resp., Dn) has a realization as the hyperoctahedral group of signed permutations (resp., the group of even signed permutations). Starting from these concrete representations of Coxeter groups in the types B and D, we pinpoint some new representations of signed permutations relying on which we provide bijective proofs of known formulas for Eulerian numbers in the types B and D. These formulas allow to compute the Eulerian numbers in the types B and D. from the better known Eulerian numbers in type A.
n 1 ⌧n Sn(t) := X k tk , k=0 n ⌧Bn Bn(t) := X k k=0 tk .
Considering that, for f (t) = Pk 0 aktk, 2Bn(t2) = (1 + t)n+1Sn(t) + (1 t)n+1Sn( t) .
Investigating further the terms 2nSn(t), we also ended up finding a simple bijective proof, that we present here, of
which, in terms of the Eulerian numbers in type D, amounts to
Let us remark that the proofs presented here follow different paths from known proofs of the identities (
Considering that, for f (t) = Pk 0 aktk,
the identity (
Let now Dn(t) be the Eulerian polynomial in type D: 2n+1tSn(t2) = (1 + t)n+1Sn(t) (1
t)n+1Sn( t) . (1 + t)n+1Sn(t) = Bn(t2) + 2ntSn(t2) .
f (t) + f ( t) = 2 X a2kt2k , ⌧Bn k
Notation, elementary definitions, and facts The notation used is chosen to be consistent with [14]. As mentioned before, we use [n] for the set { 1, . . . , n } and Sn for the set of permutations of [n]. We use [n]0 for the set { 0, 1, . . . , n }, [ n] for { n, . . . , 1 }, and [±n] for { n, . . . , 1, 1, . . . , n }. We write a permutation w 2 Sn as a word w = w1w2 . . . wn, with wi 2 [n]. For w 2 Sn, its set of descents and its set of inversions1 are defined follows:
Des(w) := { i 2 { 1, . . . , n 1 } | wi > wi+1 } ,
Inv(w) := { (i, j) | 1 i < j n, w 1(i) > w 1(j) } .
des(w) := |Des(w)| .
The Eulerian number DnkE, counting the number of permutations of n elements with k descents, can be formally defined as follows: ⌧n k
:= |{ w 2 Sn | des(w) = k }| .
Let us define a signed permutation of [n] as a permutation u of [±n] such that, for each i 2 [±n], u i = ui. We use Bn for the set of signed permutations of [n]. When writing a signed permutation u as a word u n . . . u 1u1 . . . un, we prefer writing ui = x in place of x if ui < 0 and |ui| = x. Also, we often write u 2 Bn in window notation, that is, we only write the suffix u1u2 . . . un; indeed, the prefix u nun 1 . . . u 1 is uniquely determined by the suffix u1u2 . . . un, by mirroring it and by exchanging the signs. Obviously, the set Bn is a group and, as mentioned before, it is the standard model for a Coxeter group in the family B with n generators. Therefore, general notions from the theory of Coxeter groups (descent, inversion) apply to signed permutations. We present below as definitions the well-known explicit formulas for the descent and inversion sets of u 2 Bn. We let
DesB(u) := { i 2 { 0, . . . , n
InvB(u) := { (i, j) | 1 | i| j n, u 1(i) > u 1(j) } , where we set u0 := 0, so 0 is a descent of u if and only if u1 < 0, desB(u) = |DesB(u)| , := |{ u 2 Bn | desB(u) = k }| .
Finally, and recalling the definition in (
k n k
1 n ⌧ An(t) := X k=1 tk = tSn(t) .
We shall exclusively manipulate the polynomials Sn(t) and not the An(t). Notice that Sn(t) has degree n
1 and We shall introduce later even signed permutations and their groups, as well as related notions arising from the fact that these groups are standard models for Coxeter groups in the family D.
For the time being, let us observe the following. For u 2 Bn we let DesB+(u) := DesB(u) \ { 0 }—thus DesB+(u) is the set of strictly positive descents of u. We have then: Lemma 2.1. | { u 2 Bn | DesB+(u) = k } | = 2n DnkE.
Proof. By considering its window notation, a signed permutation u yields a mapping u˜ : [n!] [±n] with a unique decomposition of the form u˜ = ◆ w with w 2 Sn and ◆ : [n]! [±n] an order preserving injection such that x 2 ◆ ([n]) iff x 62 ◆ ([n]). The monotone injections with this property are uniquely determined by their positive image ◆ ([n]) \ [n], so there are 2n such injections. Moreover, for i = 1, . . . , n 1, wi > wi+1 if and only if ui > ui+1, so |DesB+(◆ w)| = |Des(w)|.
1It is also also possible to define Inv(w) as the set { (i, j) | 1 i < j n, wi > wj }. We stick in this paper to the one given here.
Path representation of signed permutations, simply barred permutations We present here our combinatorial tools to deal with signed permutations, the path representation and the simply barred permutations.
Definition 3.1. The path representation of u 2 Bn is a triple (⇡ u, xu, yu) where ⇡ u is a discrete path, drawn on a grid [n]0 ⇥ [n]0 and joining the point (0, n) to the point (n, 0), xu : [n]! [n], and yu : [n]! [ n]. The triple (⇡ u, xu, yu) is constructed from u according to the following algorithm: (i) u is written in full notation as a word and scanned from left to right: each positive letter yields an East step (a length 1 step along the x-axis towards the right), and each negative letter yields a South step (a length 1 step along the y-axis towards the bottom) ; (ii) the labelling xu : [n]! [n] is obtained by projecting each positive letter on the x-axis, (iii) the labelling yu : [n]! [ n] is obtained by projecting each negative letter on the y-axis.
Example 3.2. Consider the signed permutation u := 2316475, in window notation, that is, 57461322316475, in full notation. Applying the algorithm above, we draw the path ⇡ u and the labellings xu, yu as follows: 5 6 1 3 2 4 7 7 4 2 3 1 6 5
It is easily seen that, for an arbitrary u 2 Bn, (⇡ u, xu, yu) has the following properties: (i) ⇡ u is symmetric along the diagonal, (ii) u x 2 Sn and, moreover, it is the subword of u of positive letters, ⌃ corresponding to the set of unordered pairs
(iii) for each i 2 [n], y(i) =
x(i) and, moreover, yu is the mirror of the subword of u of negative letters.
In particular, we see that the data (⇡ u, xu, yu) is redundant, since we could give away yu which is completely determined from xu.
Proposition 3.3. The mapping u 7! (⇡ u, xu) is a bijection from the set of signed permutations Bn to the set of pairs (⇡, w ), where w 2 Sn and ⇡ is a discrete path from (0, n) to (n, 0) with East and South steps which, moroever, is symmetric along the diagonal.
We leave the reader convince himself of the above statement. Let us argue that the path representation of a signed
permutation is, possibly, the more interesting combinatorial representation available to represent signed permutations.
For example, the type B inversions of u can be identified with the type A inversions of xu and the unordered pairs or
singletons {wi, wj } with 1 i j n such that the square (i, j) lies below ⇡ u (we index squares from left to right
and from bottom to top). Indeed, (i, j) lies below ⇡ u if and only if (j, i) does, by symmetry of ⇡ u.
With respect to Example 3.2, the set of type B inversions of 2316475 is the disjoint union of the set of type A inversions
of 7423165 and the set
{ (
Proposition 3.4. Let u 2 Bn. For each i, j with 1 )| 1i(|j ))jappears below ⇡ u. n, (i, j) 2 InvB(u) if and only if either 1 i < j n and (i, j) 2 Inv( xu) or i < 0 and (( xu) 1(i), ( xu Proof. Let in the following w = xu. If i > 0, then the statement that (i, j) 2 InvB(u) if and only if (i, j) 2 Inv(w) follows since w is the subword of u (written in full notation) of positive integers. On the other hand, if i < 0, then recall that ( i, j) 2 InvB(u) if and only if ( i, j) 2 Inv(u) if and only if ( j, i) 2 Inv(u), where, in the expression Inv(u), u is considered as a permutation of the linear order [±n]. Moreover, since the ⇡ xu is symmetric along the diagonal, observe that (i, j) is below the ⇡ xu if and only (j, i) is below the ⇡ xu. Therefore, it will be enough to observe that for y < 0 and x > 0, (x, y) is below ⇡ xu if and only if x appears before y in u, as suggested in the picture on the right. y • x
Definition 3.5. A simply barred permutation of [n] is a pair (w, B) where w 2 Sn and B ✓ { be the set of simply barred permutations of [n]. 1, . . . , n }. We let SBPn We think of B as a set of positions of w, the barred positions. We have added the adjective “simply” to “barred permutation” since we do not require that B is a superset of Des(w), as for example in [10].
Example 3.6. Consider (w, B) with w = 7423165 and B = { 2, 4, 6 }. We represent (w, B) as a permutation divided into blocks by the bars, placing a vertical bar after ui for each i 2 B, e.g. 74|23|16|5. Notice that we allow a bar to appear in the last position, for example 34|1|265|7| stands for the simply barred permutation (3412657, { 2, 3, 6, 7 }). Thus, a bar appears in the last position if and only if the last block is empty. ⌃ We describe next a bijection—that we call —from the set SBPn to Bn. Let us notice that, in order to establish equipotence of these two sets, other bijections are available and more straightforward.
Definition 3.7. For (w, B) 2 SBPn, we define the signed permutation (w, B) 2 Bn according to the following algorithm: (i) draw the grid [n]0 ⇥ [n]0; (ii) since B ✓ [n], B ⇥ B defines a subgrid of [n]0 ⇥ [n]0, construct the upper anti-diagonal ⇡ of this subgrid; (iii) (w, B) is the signed permutation u whose path representation (⇡ u, xu, yu) equals (⇡, w, w).
Example 3.8. The required construction can be understood as raising the bars and transforming them into a grid. For example, for the simply barred permutation 74|2|316|5 (that is (w, B) with w = 7423165 and B = { 2, 3, 6 }) the construction is as follows: 5 6 1 3 2 4 7 7 4 2 3 1 6 5 The dashed path is the anti-diagonal of the subgrid. The resulting signed permutation (w, B) is 2316475 as from Example 3.2. ⌃ Notice that the inverse image of has a possibly easier description, as it can be constructed according to the following algorithm: for u 2 Bn (i) construct the path representation (⇡ u, xu, yu) of u, (ii) insert a bar in w at each vertical step of ⇡ u (and remove consecutive bars), (iii) remove a bar at position 0 if it exists. Said otherwise, (w, B) = 1(u) is obtained from u by transforming each negative letter into a bar, by removing consecutive bars, and then by removing a bar at position 0 if needed.
In the following chapter we shall deal mostly with simply barred permutations. Even if we understand simply barred permutations just as shorthands for path representations of even signed permutations, some remarks are due: Lemma 3.9. If u =
(w, B), then there is a bijection between the set B of bars and the set of xy-turns of ⇡ u. 4
Descents from simply barred permutations
Proposition 4.1. For a simply barred permutation (w, B), we have desB( (w, B)) = |Des(w) \ B| + ⇠ |B| ⇡ .
2 Proof. Write u = (w, B) in window notation and divide it in maximal blocks of consecutive letters having the same sign. If the first block has negative sign, add a zero positive block which is empty. Each change of sign + among consecutive blocks yields a descent. These changes of sign bijectively correspond to xy-turns of ⇡ u that lie on or below the diagonal. By Lemma 3.9, each bar determines an xy-turn and, by symmetry of ⇡ u along the diagonal, the number of xy-turns that are on or below the diagonal is l |B| m. Therefore this quantity counts the number of descents 2 determined by a change of sign.
The other descents of (w, B) are either of the form wiwi+1 with wi > wi+1 and wi, wi+1 belonging to the same positive block, or of the form wi+1wi with wi > wi+1 and wi, wi+1 belonging to the same negative block. These descents are in bijection with the descent positions of w that do not belong to the set B. that |D(w) \ B| + l |B| m = k.
2 The following lemma might be immediately proved by considering that 0 2 DesB(u) if and only if, in the path representation of (w, B), the first step of ⇡ u is along the y-axis. In this case (and only in this case), ⇡ u makes an xy-turn on the diagonal. This happens exactly when ⇡ u has an odd number of xy-turns.
Lemma 4.2. We have 0 2 DesB( (w, B)) if and only if |B| is odd.
For each k 2 { 0, 1, . . . , n }, in the following we let SBPn,k be the set simply barred permutations (w, B) 2 SBPn such Corollary 4.3. The set SBPn,k is in bijection with the set of signed permutations of n with k descents. Definition 4.4. A loosely barred permutation of [n] is a pair (w, B) where w is a permutation of [n] and B ✓ { 0, . . . , n } is a set of positions (the bars). We let LBPn be the set of loosely barred permutations of [n]. Loosely barred permutations are being introduced only as a tool to index simply barred permutations independently of the even/odd cardinalities of their set of bars. Namely, for a loosely barred permutation (w, B), let us define its simplification &(w, B) by
&(w, B) := (w, B \ { 0 }) . often need to evaluate the expression l |B\{ 0 }| m. We record this value once for all in the lemma below.
2 Then &(w, B) is a simply barred permutation whose set of bars has even (resp., odd) cardinality if either 0 2 B and |B| is odd (resp., even), or 0 62 B and |B| is even (resp., odd). For a loosely barred permutations (w, B), we shall Lemma 4.5. For a loosely barred permutation (w, B) we have ⇠ |B \ { 0 }| ⇡ 2
>>>8 |B2 | , if |B| is even, = < |B2| 1 , if |B| is odd and 0 2 B , > >>: |B|+1 , if |B| is odd and 0 62 B .
2
(
✓ (w, B) := (w, Des(w) B) ,
where stands for symmetric difference. Let us insist that this involution is defined for all loosely barred
permutations, not just for the simply barred permutations.2
Lemma 4.6. If (u, C) = ✓ (w, B), then
|D(w)| + |B| = 2|D(u) \ C| + |C| .
(
Proposition 4.8. For each n to SBPn,k.
Proof. Recall that C = D(w) B and so D(u) \ C = D(w) \ B. Equation (
⇥ n(w, B) := &(✓ (w, B)) = (w, Des(w) B \ { 0 }) .
0 and k 2 [n]0, the restriction of ⇥ n to LBPn,2k yields a bijection ⇥ n,k from LBPn,2k
Proof. Let (w, B) 2 LBPn,2k, so |Des(w)| + |B| = 2k. Let also (u, C) = ✓ (w, B), so ⇥ n(w, B) = (w, C \ { 0 }).
Then, by (
2k = 2|D(u) \ C| + |C|
and so |C| is even. Therefore
|D(w) \ (C \ { 0 })| +
⇠ |C \ { 0 }| ⇡
2
= |D(u) \ C| +
⇠ |C \ { 0 }| ⇡ = |D(u) \ C| + |C| = k ,
2 2
where in the last step we have used equation (
The transformation ⇥ n,k is injective. If ⇥ n(w, B) = ⇥ n(w0, B0), then w = w0 and Des(w) = Des(w0). Moreover, from Des(w) B \ { 0 } = Des(w) B0 \ { 0 } we deduce B \ { 0 } = B0 \ { 0 }. If moreover (w, B), (w0, B0) 2 LBPn,2k, then |B| = 2k | Des(w)| = |B0| and B \ { 0 } = B0 \ { 0 } imply that 0 2 Des(w) B if and only if 0 2 Des(w) B0. It follows that B = B0.
In order to show that the transformation ⇥ n,k is surjective, let us fix (u, C) 2 SBPn,k, so |Des(u) \ C| + l |C| m = k.
2
If |C| is even, then (w, B) := ✓ (u, C) is such that ⇥ n(w, B) = ✓ (w, B) = (u, C) and, using equations (
Definition 4.9. For each k 2 [n |DesB+( (w, B))| = k.
Notice that |DesB+( (w, B))| = k iff 8< 0 62 DesB( (w, B)) and desB( (w, B)) = k, or : 0 2 DesB( (w, B)) and desB( (w, B)) = k + 1 . (w, B) 2 SBPkn
iff
Using Lemma 4.2 and equation (
2 >: |B| is odd and |D(w) \ B| + l |B| m = k + 1 .
2 2At the moment of writing we cannot pinpoint any other usage of this involution apart, of course, from yielding our bijections and counting results.
SBPkn.
Proposition 4.10. For each k 2 [n
1]0, the restriction of ⇥ n to LBPn,2k+1 yields a bijection ⇥ kn from LBPn,2k+1 to
Proof. Let (w, B) 2 LBPn,2k+1 and (u, C) = ✓ (w, B), so ⇥ n(w, B) = (w, C \ { 0 }). Thus |Des(w)| + |B| = 2k + 1
and, by (
2 that is, (u, C \ { 0 }) = ⇥ n(w, B) 2 SBPkn.
The transformation ⇥ kn is injective, the reason being similar to the one for ⇥ n,k. If ⇥ n(w, B) = ⇥ n(w0, B0) then w = w0 and Des(w) = Des(w0). Moreover, from Des(w) B \ { 0 } = Des(w) B0 \ { 0 } we deduce B \ { 0 } = B0 \ { 0 }. Considering now that |B| = 2k + 1 | Des(w)| = |B0| and B \ { 0 } = B0 \ { 0 }, we derive 0 2 Des(w) B if and only if 0 2 Des(w) B0, whence B = B0.
|D(u) \ C| + l |C| m = k or (ii) |C| is odd and |D(u) \ C| + l |C| m = k + 1. 2 2
(w, B) 2 LBPn,2k+1:
Let us suppose (i). Then (w, B) := ✓ (u, C [ { 0 }) is such that ⇥ n(w, B) = (u, C) and, using equations (
Let us suppose (ii). Then (w, B) := ✓ (u, C) is such that ⇥ n(w, B) = ✓ (w, B) = (u, C) and, using equations (
Theorem 4.11. The following relations hold:
⌧Bn
k
Proof. We have seen that signed permutations u 2 Bn such that desB(u) = k are in bijection (via the mapping of
Definition 3.7) with simply barred permutations in SBPn,k. Next, this set is in bijection (see Proposition (4.8)) with the
set LBPn,2k of loosely barred permutations (w, B) 2 LBPn such that des(w) + |B| = 2k. The cardinality of LBPn,2k
is the right-hand side of equality (
The left-hand side of equality (
2 ⇠ |C| ⇡ 2 1 2 1 2 Theorem 4.12. The following relation holds:
Proof. By (
Bn(t2) + 2ntSn(t2) = (1 + t)n+1Sn(t) ,
whence equation (
Stembridge’s identity for Eulerian numbers in type D Let us recall that a signed permutation u 2 Bn is even signed if the number of negative letters in its window notation is even. The even signed permutations of Bn form a subgroup Dn of Bn and in fact the groups Dn are the standard models for abstract Coxeter groups of type D.
Definitions analogous to those given in Section 2 for the types A and B can be given for type D. Namely, for u 2 Dn, we set
DesD(u) := { i 2 { 0, 1, . . . , n
The formula in (
It is convenient to consider a more flexible representation of elements of Dn. If u 2 Bn, then its mate is the signed
permutation u 2 Bn that differs from u only for the sign of the first letter. Notice that u = u. We define a forked
signed permutation (see [14, §13]) as an unordered pair of the form {u, u} for some u 2 Bn. Clearly, just one of the
mates is even signed and therefore forked signed permutations are combinatorial models of Dn.
The path representation of a forked signed permutation is insensitive of how the diagonal is crossed, either from the
West, or from the North. The following are possible ways to draw a forked signed permutation on a grid:
(
Even if the formulas in (
1 1 .
Definition 5.2. A signed permutation u is smooth if u1, u2 have equal sign and, otherwise, it is non-smooth.
The reason for naming a signed permutation smooth arises again from the path representation of a signed permutation:
the smooth signed permutation is, between the two mates, the one that minimizes the turns nearby the diagonal, as
suggested below with two pairs of mates as examples:
(
The process of normalizing the sequence u2 . . . un can be understood as applying to each letter of this sequence the unique order preserving bijection Nn,x : [±n] \ { x, x }! [± n 1] where, in general, x 2 [n] and, in this case, x = |u1|.
Lemma 5.4. Let n 2. For each pair (x, v) with x 2 [n] and v 2 Bn 1, there exists a unique non-smooth u 2 Bn such that (u) = (x, v).
Proof. We construct u firstly by renaming v to v0 so that none of x, x appears in v0 (that is, we apply to each letter of v the inverse of Nn,x) and then by adding in front of v0 either x or x, according to the sign of the first letter of v0. Lemma 5.5. The correspondence restricts to a bijection from the set of non-smooth signed permutations u 2 Bn such that desB(u) = k to the set of pairs (x, v) where x 2 [n] and v 2 Bn 1 is such that |DesB+(v)| = k 1. Proof. We have already argued that is a bijection from the set of non-smooth signed permutations u of [n] to the set of pairs (x, v) with x 2 [n] and v 2 Bn 1. Therefore, we are left to argue that, for non-smooth u and v, if desB(u) = k, then |DesB+(v)| = k 1. Since u1, u2 have different sign, then |DesB(u) \ { 0, 1 }| = 1. Clearly, if (u) = (x, v), then DesB+(v) = { i 1 | i 2 DesB(u) \ { 2, . . . , n 1 } }, from which the statement of the lemma follows.
Theorem 5.6. The following relations hold: ⌧Bn k = ⌧Dn k + n2n 1 ⌧n k such |DesB+(v)| = k
Proof. Every signed permutation is either smooth or non-smooth. By Lemma 5.3, the smooth signed permutations
with k type B descents are in bijection with the even signed permutations with k type D descents. By Lemma 5.5, the
non-smooth signed permutations u 2 Bn with k type B descents are in bijection with the pairs (x, v) 2 [n] ⇥ Bn 1
Example 5.7. We end this section exemplifying the use of formulas (
For type B, we have ⌧Bn 1
⌧n = 0 ✓n + 1◆ 2 , n
The computation in type D is then immediate from Stembridge’s identity (
(
Threshold graphs and their degree orderings Besides presenting the bijective proofs, a goal of this paper is to exemplify the potential of the path representation of signed permutations. The attentive reader might object then that the path representation is not being used in Section 5. Indeed, after discovering this proof via this representation of signed permutations, we realized that the presentation of the proof could be simplified by avoiding mention of the path representation. It might be asked then whether the path representation yields something more, in particular with respect to the lattices of the Coxeter groups Dn. We answer. The type D set of inversions of an even signed permutation (or of a forked signed permutation) can be defined as follows:
InvD(u) := InvB(u) \ { ( i, i) | i 2 [n] } , which, graphically, amounts to ignoring boxes on the diagonal: 2 5 1 4 3 ⇥ ⇥
⇥ ⇥
⇥ 3 4 1 5 2 As mentioned in Proposition 3.4, we can identify the set of inversions of a signed permutation u with the disjoint union of Inv( xu) and a set of unordered pairs. For even signed permutations, this identification yields InvD(u) = Inv( xu) [ Eu with
Eu := { {i, j} | i, j 2 [n], i 6= j, (( xu) 1(i), ( xu) 1(j)) lies below ⇡ u } . Thus, we may consider ([n], Eu) as a simple graph on the set of vertices [n]. Let us recall the following standard definitions that apply to an arbitrary simple graph (V, E) and to a vertex v 2 V :
NE (v) := { u 2 V | {v, u} 2 E } , degE (v) := |NE (v)| ,
NE [v] := N (v) [ { v } .
A linear ordering v1, . . . , vn of V is a degree ordering of (V, E) if degE (v1) degE (v2) . . . degE (vn). The vicinal preorder of a graph (V, E), noted CE , is defined by saying that v CE u iff NE (v) ✓ NE [u]. That the vicinal preorder is indeed a preorder is well known, see e.g. [12]. Next, we take Theorem 1 in [7] as the definition of the class of threshold graphs and consider, among the possible characterisations of this class, the one that uses the vicinal preorder.
Definition 6.1. A graph (V, E) is threshold if it does not contain an induced subgraph isomorphic to one among K2,2,
Proposition 6.2 (see e.g. [12, Theorem 1.2.4]). A graph (V, E) is threshold if and only if the vicinal preorder is total.
Theorem 6.3. The mapping sending u to ( xu, Eu) is a bijection from the set Dn to the set of pairs (w, E) such that ([n], E) is a threshold graph and w 2 Sn is a degree ordering on this graph.
Proof. We start arguing that, for u 2 Dn, ([n], Eu) is a threshold graph and that xu is a degree ordering on this graph. Notice that Eu = Eu, so we can suppose that u is the mate such that u1 > 0. Clearly, we can also suppose that xu is the identity permutation. Under these hypothesis, the paths ⇡ u that are symmetric along the diagonal bijectively correspond to fixed-point free self-adjoint Galois connections, see e.g. [16] for the general correspondence between paths and sup-preserving functions. For a fixed-point free self-adjoint Galois connection we mean an antitone map f : [n]0! [n]0 such that, for each x, y 2 [n]0, x f (y) iff y f (x) and x 6= f (x). Moreover, under these hypothesis, we have that {x, z} 2 Eu if and only if z 6= x and z f (x), where f bijectively corresponds to ⇡ u. Then, if y < x and z 2 NEu (x), then z f (x) f (y) and so either z = y or z 2 NEu (y). We have argued that x < y implies that NEu (y) ✓ NEu [x] which, in particular, implies that the identity permutation is a degree ordering on Eu and that the vicinal preorder is total, so ([n], Eu) is a threshold graph.
The mapping sending u to ( xu, Eu) is clearly injective, so we are left to argue that every pair (w, E), with ([n], E) a threshold graph and w 2 Sn a degree ordering on it, arises in this way. Again, we can assume that w is the identity permutation, so we need to find a fixed-point free self-adjoint Galois connection f : [n]0! [n]0 such that, for x, z 2 [n], {x, z} 2 E if and only if x 6= z and z f (x).
Observe that if degE (y) degE (x), then necessarily we have NE (y) ✓ NE [x], otherwise NE (x) ✓ NE [y] and we get a contradiction. Thus, if x < y, then NE (y) ✓ NE [x], since the identity permutation is a degree ordering. Define then f (x) = max NE (x), with the conventions that max ; = 0 and NE (0) = [n]0. For x, z 2 [n], if {x, z} 2 E, then z 2 NE (x) and then z f (x). Conversely, if z f (x), then x 2 NE (f (x)) ✓ NE [z], so if x 6= z, then x 2 NE (z) and {x, z} 2 E. Finally f is a fixed-point free self-adjoint Galois connection: it is fixed-point free since x 62 NE (x), and it is easily seen that y f (x) if and only if x f (y), for each x, y 2 [n]0, property that also implies that f is antitone.
Let us remark that Theorem 6.3 also yields a natural representation of the weak ordering on Dn as follows: under the bijection, (w1, E1) (w2, E2) holds if and only if w1 w2 in the weak ordering of Sn and, moreover, E1 ✓ E2. This poset (actually a lattice, since it is isomorphic to Dn) is built out from threshold graphs but is only loosely related to the lattice of threshold graphs of [13] where unlabeled (that is, up to isomorphism) threshold graphs are considered. That threshold graphs are related to the families B and D in the theory of Coxeter groups has already been observed, see e.g. [8], [20, Exercise 5.25], and [21, Exercise 3.115]. As part of possible future research, it is tempting to investigate further the bijection presented in Theorem 6.3 (which can be further adapted to fit the type B) and try to understand if it plays any important role with respect to the problem, partly solved in [8], of characterizing free sub-arrangements of the Coxeter arrangements Bn.