text: 1-step representations have rational singularities (in particular, are normal and Cohen-Macaulay) when Q is a Dynkin quiver (Theorem ). Moreover, we get minimal free resolutions whose terms can be computed using Bott’s theorem. Also, we give the analogous results for the normalizations of 1-step orbit closures in the extended Dynkin case (Theorem 3.7). A In Section we give more explicit results for type Dynkin quivers. Using the ﬁrst term F 1 in the minimal free resolution, we identify the minimal deﬁning equations of 1-step orbit closures as certain minors that come from rank conditions (Theorems 4.3,4.6). Using these results, prove A that the orbit closure of any representation for a type quiver can be written as a scheme- theoretic intersection of 1-step orbit closures (Theorem 4.7). This gives an algorithm for a type A quiver for ﬁnding an eﬃcient set of generators for the deﬁning ideal of the orbit closure of any representation. 1 Quivers and 1-step representations Throughout we work over an algebraically closed ﬁeld k of characteristic 0. A quiver Q is an oriented graph, i.e. a pair Q = (Q , Q ) formed by a ﬁnite set of vertices Q and a ﬁnite set of 0 1 0 arrows Q . An arrow a has a head ha, and tail ta, that are elements in Q : 1 0 a (cid:47)(cid:47) ta ha { | ∈ } A representation V of Q is a family of ﬁnite dimensional vector spaces V x Q together { → | ∈ } x ∈ N 0 with linear maps V (a) : Vta Vha a Q1 . The dimension vect→or dim V Q0 of a repre- sentation V is the tuple dim V = (dim V ) ∈ . A morphism φ : V W of two representations x {x Q0 → | ∈ } V, W is a collection of linear maps φ = φ(x) : V W x Q , with the property that ∈ (cid:88) (cid:88) x x 0 for each a Q we have φ(ha)V (a) = W(a)φ(ta). Denote by Hom (V, W) the vector space of 1 Q∈ Z morphisms of representations from V to W. For two vectors α, β Q0, we deﬁne the Euler (cid:104) (cid:105) − product α, β = α β α β . The Euler form E of a quiver Q is the quadratic x x ta ha Q ∈ ∈ Z → Z x Q0 a Q(cid:104)1 (cid:105) map Q0 given by EQ(α) = α, α . It is known that E is positive deﬁnite (resp. positive semi-deﬁnite) iﬀ Q is a Dynkin (resp. Q extended Dynkin) quiver. For more on quivers cf. [4, 22]. (cid:77) ∈ N We form the aﬃne space of representations with dimension vector α Q0 by Rep(Q, α) := Hom(kαta, kαha). ∈ a Q1(cid:89) The group GL(α) := GL(α ) x ∈ x Q0 acts by conjugation on Rep(Q, α) in the obvious way. Under the action GL(α) two elements lie in the same orbit iﬀ they are isomorphic as representations. For any two representatio(cid:77)ns V and W, we have the following exact sequence: → −→ (cid:77) 0 Hom (V, W) Hom(V (x), W(x)) Q ∈ x Q0 −d→V −→ → (1) W Hom(V (ta), W(ha)) Ext (V, W) 0, Q ∈ a Q1 2 ##LTLine##

text: representations

text: have

text: rational

text: singularities

text: (in

text: particular,

text: are

text: normal

text: and

text: Cohen-Macaulay)

text: when

text: Q

text: is

text: a

text: Dynkin

text: quiver

text: (Theorem

text: Moreover,

text: we

text: get

text: minimal

text: free

text: resolutions

text: whose

text: terms

text: can

text: be

text: computed

text: using

text: Bott’s

text: theorem.

text: Also,

text: we

text: give

text: the

text: analogous

text: results

text: for

text: the

text: normalizations

text: of

text: orbit

text: closures

text: in

text: the

text: extended

text: Dynkin

text: case

text: (Theorem

text: A

text: In

text: Section

text: we

text: give

text: more

text: explicit

text: results

text: for

text: type

text: Dynkin

text: quivers.

text: Using

text: the

text: ﬁrst

text: term

text: F

text: in

text: the

text: minimal

text: free

text: resolution,

text: we

text: identify

text: the

text: minimal

text: deﬁning

text: equations

text: of

text: orbit

text: closures

text: as

text: certain

text: minors

text: that

text: come

text: from

text: rank

text: conditions

text: (Theorems

text: Using

text: these

text: results,

text: prove

text: A

text: that

text: the

text: orbit

text: closure

text: of

text: any

text: representation

text: for

text: a

text: type

text: quiver

text: can

text: be

text: written

text: as

text: a

text: scheme-

text: theoretic

text: intersection

text: of

text: orbit

text: closures

text: (Theorem

text: This

text: gives

text: an

text: algorithm

text: for

text: a

text: type

text: A

text: quiver

text: for

text: ﬁnding

text: an

text: eﬃcient

text: set

text: of

text: generators

text: for

text: the

text: deﬁning

text: ideal

text: of

text: the

text: orbit

text: closure

text: of

text: any

text: representation.

text: Quivers

text: and

text: representations

text: Throughout

text: we

text: work

text: over

text: an

text: algebraically

text: closed

text: ﬁeld

text: k

text: of

text: characteristic

text: A

text: quiver

text: Q

text: is

text: an

text: oriented

text: graph,

text: i.e.

text: a

text: pair

text: Q

text: (Q

text: Q

text: formed

text: by

text: a

text: ﬁnite

text: set

text: of

text: vertices

text: Q

text: and

text: a

text: ﬁnite

text: set

text: of

text: arrows

text: Q

text: An

text: arrow

text: a

text: has

text: a

text: head

text: ha,

text: and

text: tail

text: ta,

text: that

text: are

text: elements

text: in

text: Q

text: a

text: ta

text: ha

text: A

text: representation

text: V

text: of

text: Q

text: is

text: a

text: family

text: of

text: ﬁnite

text: dimensional

text: vector

text: spaces

text: V

text: x

text: Q

text: together

text: x

text: N

text: with

text: linear

text: maps

text: V

text: (a)

text: Vta

text: Vha

text: a

text: The

text: dimension

text: vect→or

text: dim

text: V

text: of

text: a

text: repre-

text: sentation

text: V

text: is

text: the

text: tuple

text: dim

text: V

text: (dim

text: V

text: A

text: morphism

text: φ

text: V

text: W

text: of

text: two

text: representations

text: x

text: {x

text: V,

text: W

text: is

text: a

text: collection

text: of

text: linear

text: maps

text: φ

text: φ(x)

text: V

text: W

text: x

text: Q

text: with

text: the

text: property

text: that

text: x

text: x

text: for

text: each

text: a

text: Q

text: we

text: have

text: φ(ha)V

text: (a)

text: W(a)φ(ta).

text: Denote

text: by

text: Hom

text: (V,

text: W)

text: the

text: vector

text: space

text: of

text: Q∈

text: Z

text: morphisms

text: of

text: representations

text: from

text: V

text: to

text: W.

text: For

text: two

text: vectors

text: α,

text: β

text: we

text: deﬁne

text: the

text: Euler

text: product

text: α,

text: β

text: α

text: β

text: α

text: β

text: The

text: Euler

text: form

text: E

text: of

text: a

text: quiver

text: Q

text: is

text: the

text: quadratic

text: x

text: x

text: ta

text: ha

text: Q

text: Z

text: Z

text: x

text: a

text: map

text: given

text: by

text: EQ(α)

text: α,

text: α

text: It

text: is

text: known

text: that

text: E

text: is

text: positive

text: deﬁnite

text: (resp.

text: positive

text: semi-deﬁnite)

text: iﬀ

text: Q

text: is

text: a

text: Dynkin

text: (resp.

text: Q

text: extended

text: Dynkin)

text: quiver.

text: For

text: more

text: on

text: quivers

text: cf.

text: N

text: We

text: form

text: the

text: aﬃne

text: space

text: of

text: representations

text: with

text: dimension

text: vector

text: α

text: by

text: Rep(Q,

text: α)

text: Hom(kαta,

text: kαha).

text: a

text: The

text: group

text: GL(α)

text: GL(α

text: x

text: x

text: acts

text: by

text: conjugation

text: on

text: Rep(Q,

text: α)

text: in

text: the

text: obvious

text: way.

text: Under

text: the

text: action

text: GL(α)

text: two

text: elements

text: lie

text: in

text: the

text: same

text: orbit

text: iﬀ

text: they

text: are

text: isomorphic

text: as

text: representations.

text: For

text: any

text: two

text: V

text: and

text: W,

text: we

text: have

text: the

text: following

text: exact

text: sequence:

text: Hom

text: (V,

text: W)

text: Hom(V

text: (x),

text: W(x))

text: Q

text: x

text: −d→V

text: W

text: Hom(V

text: (ta),

text: W(ha))

text: Ext

text: (V,

text: W)

text: Q

text: a

text: ##LTLine##


text: As mentioned, we work on the support of rp,q. First, we show that Hom (E , T ) = 0. We − Q p,q γ apply reﬂections successively at the vertices p, p + 1, . . . , si 1. Since γp(cid:48)< γp,si, t−he generic representation T will be sent to another generic representation T (cid:48), and γ − = γ γ . The γ γ si 1 si p indecomposable E will be sent to E , and dim Hom (E , T ) = dim Hom (E , T (cid:48)). − p,q si,q Q −p,q γ Q si,q γ Since s 1 is a sink, we can delete the vertices p, p + 1, . . . s 2, and not change the dimension i − i (cid:48) of morphisms. Moreover, it is easy to see that rsi 1,q is relevant with respect to γ , that is, (cid:48) − the inequalities involving γ necessary for rsi 1,q to be relevant are satisﬁed (see Deﬁnition 4.1). Applying the construction (8) for this smaller quiver, we get precisely E = E − . So si,q 1 we reduced the argument to the case when the quiver starts with a sink. More precisely, we can assume from the onset p is a sink in the support of rp,q with p < s , where s a source, i i γ a dimension vector and rp,q is relevant with respect to γ. In the construction (8), we have E = E . We want to prove that dim Hom (E , T ) = 0. We proceed by induction on p+1,q Q p+1,q γ the number of vertices. If s = q, then the quiver is equioriented in which case the result is i easy to check directly. Otherwise, we reﬂect successively on the vertices s , s − , . . . , p + 1 and (cid:48)(cid:48) (cid:48)(cid:48)i i 1 obtain a dimension vector γ . Since γsi < γsi,sp + γsi,si+1, we see that γ has positive entries, in particular T is sent to a generic representation T (cid:48)(cid:48). Also, E is sent to E , so we can γ γ p+1,q p+2,q delete the vertex p without changing the dimension of morphisms. Moreover, it is easy to see that (cid:48)(cid:48) rp+1,q is relevant with respect to γ . Hence we conclude by induction that Hom (E , T ) = 0. (cid:48) (cid:54) Q p,q γ Now to see that Ext (E , T ) = 0, we note that the equioriented case is easy to see directly. In Q γ the induction process above we always worked with roots relevant with respect to γ, and the (cid:48) reﬂection functor applied to a source preserves the dimensions of extensions whenever E is not a simple representation at a source. Similarly, it is easy to see that the deleted vertices in the (cid:48) (cid:48) process did not change Ext(E , T ). So we only need to check that if E is a simple representation γ (cid:48) (cid:54) at a source and the inequalities for γ as in Deﬁnition 4.1 are satisﬁed, then Ext(E , T ) = 0. γ This is easy to see directly. Now let Q denote our original quiver. If rp,q is relevant, and E is obtained by the con- struction in (8), we showed that Hom (E, T ) = 0 and Ext (E, T ) = 0. Applying the functor − →Q →γ → → Q β Hom (E, ) to the exact sequence 0 T V T 0, we obtain that dim Hom (E, V ) = Q (cid:104) (cid:105) β(cid:88) γ (cid:88) Q dim Hom (E, T ) = dim E, β . Using this, by (9) we get for rp,q relevant that Q β rank V = γ + β . p,q x y inxsuspouprrcep,q in syupsipnkrp,q Using Theorem 4.3, we obtain the conclusion. A ∈ O For any representation Y of a quiver of type , it is known (see [2]) that X if and ≤ ≤ ≤ n Y only if rank X rank Y , for all 1 p < q n. In fact, the rank conditions give deﬁning Op,q p,q equations of by [21, Theorem 6.4]. Using the 1-step representations, we give an alternative Y proof of this fact. Moreover, the proof we give is an eﬀective algorithm for producing a smaller set of minors coming from rank conditions that generate the deﬁning ideal of the orbit closure of a representation: A ∈ Theorem 4.7. Let Q be a quiver of type and Y Rep(Q, α) be an arbitrary representation. O n − Then can be written as a (scheme-theoretic) intersection of n 1 one-step orbit closures. In Y O particular, some rank conditions generate the deﬁning ideal of . Y ∈ { − Proof. First, we show that such a set-theoretic intersection exists. Fix a vertex p 1, 2, . . . , n } ∈ ∈ O 1 . We construct a 1-step representation Wp Rep(Q, α) such that Y and rank Wp = ∈ { } W≤p p,q rank Y , for any q p + 1, . . . , n . As usual, we assume WLOG that s − p < s with s − p,q i 1 i i 1 16 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: As

label: paragraph

text: mentioned,

text: we

text: work

text: on

text: the

text: support

text: of

text: rp,q.

text: First,

text: we

text: show

text: that

text: Hom

text: (E

text: T

text: We

text: Q

text: p,q

text: γ

text: apply

text: reﬂections

text: successively

text: at

text: the

text: vertices

text: p,

text: p

text: si

text: Since

text: γp,si,

text: t−he

text: generic

text: representation

text: T

text: will

text: be

text: sent

text: to

text: another

text: generic

text: representation

text: T

text: and

text: γ

text: γ

text: γ

text: The

text: γ

text: γ

text: si

text: si

text: p

text: indecomposable

text: E

text: will

text: be

text: sent

text: to

text: E

text: and

text: dim

text: Hom

text: (E

text: T

text: dim

text: Hom

text: (E

text: T

text: p,q

text: si,q

text: Q

text: −p,q

text: γ

text: Q

text: si,q

text: γ

text: Since

text: s

text: is

text: a

text: sink,

text: we

text: can

text: delete

text: the

text: vertices

text: p,

text: p

text: s

text: and

text: not

text: change

text: the

text: dimension

text: i

text: i

text: of

text: morphisms.

text: Moreover,

text: it

text: is

text: easy

text: to

text: see

text: that

text: rsi

text: is

text: relevant

text: with

text: respect

text: to

text: γ

text: that

text: is,

text: the

text: inequalities

text: involving

text: γ

text: necessary

text: for

text: rsi

text: to

text: be

text: relevant

text: are

text: satisﬁed

text: (see

text: Deﬁnition

text: Applying

text: the

text: construction

text: for

text: this

text: smaller

text: quiver,

text: we

text: get

text: precisely

text: E

text: E

text: So

text: si,q

text: we

text: reduced

text: the

text: argument

text: to

text: the

text: case

text: when

text: the

text: quiver

text: starts

text: with

text: a

text: sink.

text: More

text: precisely,

text: we

text: can

text: assume

text: from

text: the

text: onset

text: p

text: is

text: a

text: sink

text: in

text: the

text: support

text: of

text: rp,q

text: with

text: p

text: s

text: where

text: s

text: a

text: source,

text: i

text: i

text: γ

text: a

text: dimension

text: vector

text: and

text: rp,q

text: is

text: relevant

text: with

text: respect

text: to

text: γ.

text: In

text: the

text: construction

text: we

text: have

text: E

text: E

text: We

text: want

text: to

text: prove

text: that

text: dim

text: Hom

text: (E

text: T

text: We

text: proceed

text: by

text: induction

text: on

text: Q

text: γ

text: the

text: number

text: of

text: vertices.

text: If

text: s

text: q,

text: then

text: the

text: quiver

text: is

text: equioriented

text: in

text: which

text: case

text: the

text: result

text: is

text: i

text: easy

text: to

text: check

text: directly.

text: Otherwise,

text: we

text: reﬂect

text: successively

text: on

text: the

text: vertices

text: s

text: s

text: p

text: and

text: i

text: obtain

text: a

text: dimension

text: vector

text: γ

text: Since

text: γsi

text: γsi,sp

text: we

text: see

text: that

text: γ

text: has

text: positive

text: entries,

text: in

text: particular

text: T

text: is

text: sent

text: to

text: a

text: generic

text: representation

text: T

text: Also,

text: E

text: is

text: sent

text: to

text: E

text: so

text: we

text: can

text: γ

text: γ

text: delete

text: the

text: vertex

text: p

text: without

text: changing

text: the

text: dimension

text: of

text: morphisms.

text: Moreover,

text: it

text: is

text: easy

text: to

text: see

text: that

text: is

text: relevant

text: with

text: respect

text: to

text: γ

text: Hence

text: we

text: conclude

text: by

text: induction

text: that

text: Hom

text: (E

text: T

text: Q

text: p,q

text: γ

text: Now

text: to

text: see

text: that

text: Ext

text: (E

text: T

text: we

text: note

text: that

text: the

text: equioriented

text: case

text: is

text: easy

text: to

text: see

text: directly.

text: In

text: Q

text: γ

text: the

text: induction

text: process

text: above

text: we

text: always

text: worked

text: with

text: roots

text: relevant

text: with

text: respect

text: to

text: γ,

text: and

text: the

text: reﬂection

text: functor

text: applied

text: to

text: a

text: source

text: preserves

text: the

text: dimensions

text: of

text: extensions

text: whenever

text: E

text: is

text: not

text: a

text: simple

text: representation

text: at

text: a

text: source.

text: Similarly,

text: it

text: is

text: easy

text: to

text: see

text: that

text: the

text: deleted

text: vertices

text: in

text: the

text: process

text: did

text: not

text: change

text: Ext(E

text: T

text: So

text: we

text: only

text: need

text: to

text: check

text: that

text: if

text: E

text: is

text: a

text: simple

text: representation

text: γ

text: at

text: a

text: source

text: and

text: the

text: inequalities

text: for

text: γ

text: as

text: in

text: Deﬁnition

text: are

text: satisﬁed,

text: then

text: Ext(E

text: T

text: γ

text: This

text: is

text: easy

text: to

text: see

text: directly.

text: Now

text: let

text: Q

text: denote

text: our

text: original

text: quiver.

text: If

text: rp,q

text: is

text: relevant,

text: and

text: E

text: is

text: obtained

text: by

text: the

text: con-

text: struction

text: in

text: we

text: showed

text: that

text: Hom

text: (E,

text: T

text: and

text: Ext

text: (E,

text: T

text: Applying

text: the

text: functor

text: →Q

text: →γ

text: Q

text: β

text: Hom

text: (E,

text: to

text: the

text: exact

text: sequence

text: T

text: V

text: T

text: we

text: obtain

text: that

text: dim

text: Hom

text: (E,

text: V

text: Q

text: γ

text: Q

text: dim

text: Hom

text: (E,

text: T

text: dim

text: E,

text: β

text: Using

text: this,

text: by

text: we

text: get

text: for

text: rp,q

text: relevant

text: that

text: Q

text: β

text: rank

text: V

text: γ

text: β

text: p,q

text: x

text: y

text: inxsuspouprrcep,q

text: in

text: syupsipnkrp,q

text: Using

text: Theorem

text: we

text: obtain

text: the

text: conclusion.

text: A

text: O

text: For

text: any

text: representation

text: Y

text: of

text: a

text: quiver

text: of

text: type

text: it

text: is

text: known

text: (see

text: that

text: X

text: if

text: and

text: n

text: Y

text: only

text: if

text: rank

text: X

text: rank

text: Y

text: for

text: all

text: p

text: q

text: n.

text: In

text: fact,

text: the

text: rank

text: conditions

text: give

text: deﬁning

text: Op,q

text: p,q

text: equations

text: of

text: by

text: Theorem

text: Using

text: the

text: representations,

text: we

text: give

text: an

text: alternative

text: Y

text: proof

text: of

text: this

text: fact.

text: Moreover,

text: the

text: proof

text: we

text: give

text: is

text: an

text: eﬀective

text: algorithm

text: for

text: producing

text: a

text: smaller

text: set

text: of

text: minors

text: coming

text: from

text: rank

text: conditions

text: that

text: generate

text: the

text: deﬁning

text: ideal

text: of

text: the

text: orbit

text: closure

text: of

text: a

text: representation:

text: A

text: Theorem

text: Let

text: Q

text: be

text: a

text: quiver

text: of

text: type

text: and

text: Y

text: Rep(Q,

text: α)

text: be

text: an

text: arbitrary

text: representation.

text: O

text: n

text: Then

text: can

text: be

text: written

text: as

text: a

text: (scheme-theoretic)

text: intersection

text: of

text: n

text: one-step

text: orbit

text: closures.

text: In

text: Y

text: O

text: particular,

text: some

text: rank

text: conditions

text: generate

text: the

text: deﬁning

text: ideal

text: of

text: Y

text: Proof.

text: First,

text: we

text: show

text: that

text: such

text: a

text: set-theoretic

text: intersection

text: exists.

text: Fix

text: a

text: vertex

text: p

text: n

text: O

text: We

text: construct

text: a

text: representation

text: Wp

text: Rep(Q,

text: α)

text: such

text: that

text: Y

text: and

text: rank

text: Wp

text: W≤p

text: p,q

text: rank

text: Y

text: for

text: any

text: q

text: p

text: n

text: As

text: usual,

text: we

text: assume

text: WLOG

text: that

text: s

text: p

text: s

text: with

text: s

text: p,q

text: i

text: i

text: i

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Remark 4.8. The argument above using Frobenius splitting fails for other Dynkin types. The E ﬁrst author constructed in [16] an example of a nullcone of a type quiver that is not re- 8 duced. But this nullcone is the intersection of the codimension 1 orbit closures (which are in fact subgeneric, hence 1-step by Proposition 1.4). References [1] S. Abeasis, Codimension 1 orbits and semi-invariants for the representations of an oriented A graph of type , Trans. Amer. Math. Soc. 282 (1984), no. 2, 463–485. n A [2] S. Abeasis and A. Del Fra, Degenerations for the representations of a quiver of type , J. m Algebra 93 (1985), 376–412. [3] S. Abeasis, A. Del Fra, and H. Kraft, The geometry of representations of A , Mathematische m Annalen 256 (1981), no. 3, 401–418. [4] I. Assem, D. Simson, and A. Skowron´ski, Elements of the representation theory of associative algebras, Vol. 1, Techniques of representation theory, London Mathematical Society Student Texts, vol. 65, Cambridge University Press, Cambridge, 2006. A [5] G. Bobin´ski and G. Zwara, Normality of orbit closures for Dynkin quivers of type , n Manuscripta Math. 105 (2001), 103–109. [6] , Schubert varieties and representations of Dynkin quivers, Colloq. Math. 94 (2002), 285–309. [7] K. Bongartz, On degenerations and extensions of ﬁnite dimensional modules, Adv. Math. 121 (1996), 245–287. [8] M. Brion and S. Kumar, Frobenius splitting methods in geometry and representation theory, Progress in Mathematics, vol. 231, Birkh¨auser Boston, Inc., Boston, MA. [9] H. Derksen and J. Weyman, On the canonical decomposition of quiver representations, Com- pos. Math. 133 (2002), 245–265. [10] W. Fulton, Eigenvalues of sums of Hermitian matrices (after A. Klyachko), S´eminaire Bour- baki. Vol. 1997/98, Ast´erisque (1998), no. 252, 255–269, Exp. 845. [11] G. C. Irelli, E. Feigin, and M. Reineke, Quiver Grassmannians and degenerate ﬂag varieties, Algebra Number Theory 6 (2012), no. 1, 165–194. [12] R. Kinser and J. Rajchgot, Type A quiver loci and Schubert varieties, J. Commut. Algebra 7 (2015), no. 2, 265–301. [13] S. Kov´acs, A characterization of rational singularities, Duke Math. J. 102 (2000), no. 2, 187–191. [14] V. Lakshmibai and P. Magyar, Degeneracy schemes, quiver schemes, and Schubert varieties, Int. Res. Res. Not. 1998 (1998), no. 12, 627–640. [15] A. Lascoux, Syzygies des vari´et´es d´eterminantales, Adv. Math. 30 (1978), no. 3, 202–237. [16] A. C. L˝orincz, Singularities of zero sets of semi-invariants for quivers, http://arxiv.org/ pdf/1509.04170v2.pdf. 18 ##LTLine##

text: Remark

text: The

text: argument

text: above

text: using

text: Frobenius

text: splitting

text: fails

text: for

text: other

text: Dynkin

text: types.

text: The

text: E

text: ﬁrst

text: author

text: constructed

text: in

text: an

text: example

text: of

text: a

text: nullcone

text: of

text: a

text: type

text: quiver

text: that

text: is

text: not

text: re-

text: duced.

text: But

text: this

text: nullcone

text: is

text: the

text: intersection

text: of

text: the

text: codimension

text: orbit

text: closures

text: (which

text: are

text: in

text: fact

text: subgeneric,

text: hence

text: by

text: Proposition

text: References

label: reference

text: S.

text: Abeasis,

text: Codimension

text: orbits

text: and

text: semi-invariants

text: for

text: the

text: representations

text: of

text: an

text: oriented

text: A

text: graph

text: of

text: type

text: Trans.

text: Amer.

text: Math.

text: Soc.

text: no.

text: n

text: A

text: S.

text: Abeasis

text: and

text: A.

text: Del

text: Fra,

text: Degenerations

text: for

text: the

text: representations

text: of

text: a

text: quiver

text: of

text: type

text: J.

text: m

text: Algebra

text: S.

text: Abeasis,

text: A.

text: Del

text: Fra,

text: and

text: H.

text: Kraft,

text: The

text: geometry

text: of

text: representations

text: of

text: A

text: Mathematische

text: m

text: Annalen

text: no.

text: I.

text: Assem,

text: D.

text: Simson,

text: and

text: A.

text: Skowron´ski,

text: Elements

text: of

text: the

text: representation

text: theory

text: of

text: associative

text: algebras,

text: Vol.

text: Techniques

text: of

text: representation

text: theory,

text: London

text: Mathematical

text: Society

text: Student

text: Texts,

text: vol.

text: Cambridge

text: University

text: Press,

text: Cambridge,

text: A

text: G.

text: Bobin´ski

text: and

text: G.

text: Zwara,

text: Normality

text: of

text: orbit

text: closures

text: for

text: Dynkin

text: quivers

text: of

text: type

text: n

text: Manuscripta

text: Math.

text: Schubert

text: varieties

text: and

text: representations

text: of

text: Dynkin

text: quivers,

text: Colloq.

text: Math.

text: K.

text: Bongartz,

text: On

text: degenerations

text: and

text: extensions

text: of

text: ﬁnite

text: dimensional

text: modules,

text: Adv.

text: Math.

text: M.

text: Brion

text: and

text: S.

text: Kumar,

text: Frobenius

text: splitting

text: methods

text: in

text: geometry

text: and

text: representation

text: theory,

text: Progress

text: in

text: Mathematics,

text: vol.

text: Birkh¨auser

text: Boston,

text: Inc.,

text: Boston,

text: MA.

text: H.

text: Derksen

text: and

text: J.

text: Weyman,

text: On

text: the

text: canonical

text: decomposition

text: of

text: quiver

text: representations,

text: Com-

text: pos.

text: Math.

text: W.

text: Fulton,

text: Eigenvalues

text: of

text: sums

text: of

text: Hermitian

text: matrices

text: (after

text: A.

text: Klyachko),

text: S´eminaire

text: Bour-

text: baki.

text: Vol.

text: Ast´erisque

text: no.

text: Exp.

text: G.

text: C.

text: Irelli,

text: E.

text: Feigin,

text: and

text: M.

text: Reineke,

text: Quiver

text: Grassmannians

text: and

text: degenerate

text: ﬂag

text: varieties,

text: Algebra

text: Number

text: Theory

text: no.

text: R.

text: Kinser

text: and

text: J.

text: Rajchgot,

text: Type

text: A

text: quiver

text: loci

text: and

text: Schubert

text: varieties,

text: J.

text: Commut.

text: Algebra

text: no.

text: S.

text: Kov´acs,

text: A

text: characterization

text: of

text: rational

text: singularities,

text: Duke

text: Math.

text: J.

text: no.

text: V.

text: Lakshmibai

text: and

text: P.

text: Magyar,

text: Degeneracy

text: schemes,

text: quiver

text: schemes,

text: and

text: Schubert

text: varieties,

text: Int.

text: Res.

text: Res.

text: Not.

text: no.

text: A.

text: Lascoux,

text: Syzygies

text: des

text: vari´et´es

text: d´eterminantales,

text: Adv.

text: Math.

text: no.

text: A.

text: C.

text: L˝orincz,

text: Singularities

text: of

text: zero

text: sets

text: of

text: semi-invariants

text: for

text: quivers,

text: ##LTLine##


text: We note the similarity of the above result regarding the ﬁber to [11, Proposition 3.1]. Not all 1-step representations are of the above form. For example, let Q be the equioriented A quiver 4 → → → 1 2 3 4, with V the 1-step representation obtained from β = (1, 0, 1, 0) and α = (1, 1, 1, 1). Then V ⊕ ⊕ ⊕ decomposes as V = 1000 0110 0001, but it cannot be written as a decomposition V = M N with M, N generic and Ext(M, N) = 0. Now let Q be an arbitrary quiver, T a generic representation with full support Q and ⊕ · · · ⊕ α = dim T. Writing T = T1λ1 Trλr with λi > 0 and T1, . . . , Tr pair-wise non-isomorphic indecomposables, we must have Ext(T , T ) = 0 for all i, j. We investigate the irreducible com- O i j ponents of the complement of in Rep(Q, α). Whenever such a component is an orbit closure O T of a representation V , we call V a subgeneric representation. V In [20] it is shown that if T is so-called stable, then all the irreducible components of the O complement of are orbit closures. Roughly speaking, T is stable when the multiplicities λ T i are large enough (for a precise deﬁnition of stability, see [20]). In case of Dynkin quivers, any generic representation is stable. Sub-generic representations of codimension 1 are given by semi-invariants, and their geometry has been studied using Bernstein-Sato polynomials [16, 17]. Proposition 1.4. Let T be a stable generic representation. Then subgeneric representations in Rep(Q, dim T) are 1-step. Proof. Assume ﬁrst that V is a subgeneric representation of codimension 1. By [20], V can be (cid:48) ⊕ ⊕ (cid:48) (cid:48) written in the form V = T Z R, with T , Z, R generic and Ext(Z, T ) = k. Hence we can (cid:48) ⊕ apply Proposition 1.3 with M = T R and N = Z. Now if V is subgeneric of codimension larger than 1, then by [20] it can be written as either ⊕ ⊕ V = Tλi+1 X R, where the only non-trivial extension between T , X, R is Ext(T , X) = k, i ⊕ ⊕ i i or V = Tλi+1 Y R with the only non-trivial extension group Ext(Y, T ) = k. We can apply i ⊕ i Proposition 1.3 in the former case with M = X and N = Tλi+1 R, while in the latter with ⊕ i M = Tλi+1 R and N = Y . i 2 The geometric technique Throughout we incorporate much of the notation used in [25]. For more on the geometric technique, see [26]. ∈ Let V Rep(Q, α) be a 1-step representation with ⊂ (cid:16) O q : Z(Q, β α) (cid:76) V for some dimension vector β and let α = β + γ. ∗ ⊗ We can identify the aﬃne space Rep(Q, α) with ∈ V V . Denote by A the coordinate a Q1 ta ha ring of Rep(Q, α). ∈ R Q For a vertex x Q , denote by (resp. ) the tautological bundle (resp. factorbundle) 0 ×x x E on Gr(β , α ). We view Rep(Q, α) Gr(β, α) as the total space of the trivial bundle and x x 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: We

text: note

text: the

text: similarity

text: of

text: the

text: above

text: result

text: regarding

text: the

text: ﬁber

text: to

text: Proposition

text: Not

text: all

text: representations

text: are

text: of

text: the

text: above

text: form.

text: For

text: example,

text: let

text: Q

text: be

text: the

text: equioriented

text: A

text: quiver

text: with

text: V

text: the

text: representation

text: obtained

text: from

text: β

text: and

text: α

text: Then

text: V

text: decomposes

text: as

text: V

text: but

text: it

text: cannot

text: be

text: written

text: as

text: a

text: decomposition

text: V

text: M

text: N

text: with

text: M,

text: N

text: generic

text: and

text: Ext(M,

text: N)

text: Now

text: let

text: Q

text: be

text: an

text: arbitrary

text: quiver,

text: T

text: a

text: generic

text: representation

text: with

text: full

text: support

text: Q

text: and

text: α

text: dim

text: T.

text: Writing

text: T

text: Trλr

text: with

text: λi

text: and

text: Tr

text: pair-wise

text: non-isomorphic

text: indecomposables,

text: we

text: must

text: have

text: Ext(T

text: T

text: for

text: all

text: i,

text: j.

text: We

text: investigate

text: the

text: irreducible

text: com-

text: O

text: i

text: j

text: ponents

text: of

text: the

text: complement

text: of

text: in

text: Rep(Q,

text: α).

text: Whenever

text: such

text: a

text: component

text: is

text: an

text: orbit

text: closure

text: O

text: T

text: of

text: a

text: representation

text: V

text: we

text: call

text: V

text: a

text: subgeneric

text: representation.

text: V

text: In

text: it

text: is

text: shown

text: that

text: if

text: T

text: is

text: so-called

text: stable,

text: then

text: all

text: the

text: irreducible

text: components

text: of

text: the

text: O

text: complement

text: of

text: are

text: orbit

text: closures.

text: Roughly

text: speaking,

text: T

text: is

text: stable

text: when

text: the

text: multiplicities

text: λ

text: T

text: i

text: are

text: large

text: enough

text: (for

text: a

text: precise

text: deﬁnition

text: of

text: stability,

text: see

text: In

text: case

text: of

text: Dynkin

text: quivers,

text: any

text: generic

text: representation

text: is

text: stable.

text: Sub-generic

text: representations

text: of

text: codimension

text: are

text: given

text: by

text: semi-invariants,

text: and

text: their

text: geometry

text: has

text: been

text: studied

text: using

text: Bernstein-Sato

text: polynomials

text: Proposition

text: Let

text: T

text: be

text: a

text: stable

text: generic

text: representation.

text: Then

text: subgeneric

text: representations

text: in

text: Rep(Q,

text: dim

text: T)

text: are

text: Proof.

text: Assume

text: ﬁrst

text: that

text: V

text: is

text: a

text: subgeneric

text: representation

text: of

text: codimension

text: By

text: V

text: can

text: be

text: written

text: in

text: the

text: form

text: V

text: T

text: Z

text: R,

text: with

text: T

text: Z,

text: R

text: generic

text: and

text: Ext(Z,

text: T

text: k.

text: Hence

text: we

text: can

text: apply

text: Proposition

text: with

text: M

text: T

text: R

text: and

text: N

text: Z.

text: Now

text: if

text: V

text: is

text: subgeneric

text: of

text: codimension

text: larger

text: than

text: then

text: by

text: it

text: can

text: be

text: written

text: as

text: either

text: V

text: X

text: R,

text: where

text: the

text: only

text: non-trivial

text: extension

text: between

text: T

text: X,

text: R

text: is

text: Ext(T

text: X)

text: k,

text: i

text: i

text: i

text: or

text: V

text: Y

text: R

text: with

text: the

text: only

text: non-trivial

text: extension

text: group

text: Ext(Y,

text: T

text: k.

text: We

text: can

text: apply

text: i

text: i

text: Proposition

text: in

text: the

text: former

text: case

text: with

text: M

text: X

text: and

text: N

text: R,

text: while

text: in

text: the

text: latter

text: with

text: i

text: M

text: R

text: and

text: N

text: Y

text: i

text: The

text: geometric

text: technique

text: Throughout

text: we

text: incorporate

text: much

text: of

text: the

text: notation

text: used

text: in

text: For

text: more

text: on

text: the

text: geometric

text: technique,

text: see

text: Let

text: V

text: Rep(Q,

text: α)

text: be

text: a

text: representation

text: with

text: O

text: q

text: Z(Q,

text: β

text: α)

text: V

text: for

text: some

text: dimension

text: vector

text: β

text: and

text: let

text: α

text: β

text: γ.

text: We

text: can

text: identify

text: the

text: aﬃne

text: space

text: Rep(Q,

text: α)

text: with

text: V

text: V

text: Denote

text: by

text: A

text: the

text: coordinate

text: a

text: ta

text: ha

text: ring

text: of

text: Rep(Q,

text: α).

text: R

text: Q

text: For

text: a

text: vertex

text: x

text: Q

text: denote

text: by

text: (resp.

text: the

text: tautological

text: bundle

text: (resp.

text: factorbundle)

text: ×x

text: x

text: E

text: on

text: Gr(β

text: α

text: We

text: view

text: Rep(Q,

text: α)

text: Gr(β,

text: α)

text: as

text: the

text: total

text: space

text: of

text: the

text: trivial

text: bundle

text: and

text: x

text: x

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ⊂ S E Z(Q, β α) as the total space of some subbundle of . Let ξ denote the dual of the factorbundle E S (cid:77) / . More explicitly, it is given by R ⊗ Q∗ ξ = . ta ha ∈ a Q1 Applying [26, Theorem 5.1.2](cid:77), we consider the (cid:94)complex F• with terms i+j ⊗ − − F = Hj(Gr(β, α), ξ) A( i j). (2) i ≥ j 0 We use the following version of [26, Theorem 5.1.3] without assuming that q is birational. Theorem 2.1. Using the notation above, we have the following: − (a) If F = 0 for all i < 0, and the ﬁber q 1(V ) is connected, then F• is a ﬁnite minimal free i O resolution of the normalization of , and the normalization has rational singularities. V O (b) If F = 0 for all i < 0 and F = A, then is normal and it has rational singularities. i 0 V ⊂ O Proof. (a) Put Z := Z(Q, β α). We factor q through the normalization Y of , then −→f (cid:48) → (cid:48) apply Stein factorization to obtain Z Y Y , where Y is an integral scheme with O O (cid:48) → f∗ = (cid:48). The map Y Y is birational since the general ﬁber of q is connected. Z Y (cid:48) (cid:39) This shows that Y Y . The statement about minimal free resolution follows as in [26, Theorem 5.1.3]. and the statement about rational singularities follows from [13]. O (b) Let = Spec A/I, where I is a prime ideal. Applying Stein factorization we have → V → Z X Spec A/I, where X is an integral aﬃne scheme. Since F = A and F = 0 for 0 i all i < 0, [26, Theorem 5.1.3] implies that X = Spec A/J for some prime ideal J. But → Spec A/J Spec A/I is surjective, so it must be an isomorphism. The rest follows as in part (a). A partition (with n parts) λ = (λ , λ , . . . , λ ) is a non-increasing sequence of non-negative 1 2 n integers. For a partition λ we associate its corresponding Young diagram that consists of λ | | · · · i boxes in the ith row. We denote the number of boxes by λ := λ + + λ . We denote by u 1 n λ the size of the Durfee square of λ, that is, the biggest square ﬁtting inside of the Young diagram ≥ ≤ of λ. Its deﬁning property is λ u and λ u . u−λ λ − uλ+1 −λ − Let λ+ be the partition (λ u , λ u , . . . , λ u ) and λ the partition (λ , . . . , λ ). 1 λ 2 λ uλ λ − uλ+1 ×n Hence we can view the Young diagram of λ as the composite of the 3 parts λ+, λ and a u u λ λ square: × uλ uλ λ+ λ : − λ (cid:48) (cid:48) (cid:48) (cid:48) The conjugate partition λ = (λ , . . . , λ ) is a partition with λ being the number of boxes 1 m i in the ith column of the Young diagram of λ. Note that u = u (cid:48). − λ λ − − − Denote by λ the non-increasing sequence of non-positive integers ( λ , λ − , . . . , λ ). n n 1 1 A weight (with n parts) is any sequence of integers δ := (δ , δ , . . . , δ ). For a weight δ and ∈ Z 1 2 n a number u we denote by δ + u the weight (δ + u, δ + u, . . . , δ + u). 1 2 n 6 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: S

text: E

text: Z(Q,

text: β

text: α)

text: as

text: the

text: total

text: space

text: of

text: some

text: subbundle

text: of

text: Let

text: ξ

text: denote

text: the

text: dual

text: of

text: the

text: factorbundle

text: E

text: S

text: More

text: explicitly,

text: it

text: is

text: given

text: by

text: R

text: Q∗

text: ξ

text: ta

text: ha

text: a

text: Applying

text: Theorem

label: equation

text: we

text: consider

text: the

text: F•

text: with

text: terms

text: i+j

text: F

text: Hj(Gr(β,

text: α),

text: ξ)

text: A(

text: i

text: j).

text: i

text: j

text: We

text: use

text: the

text: following

text: version

text: of

text: Theorem

text: without

text: assuming

text: that

text: q

text: is

text: birational.

text: Theorem

text: Using

text: the

text: notation

text: above,

text: we

text: have

text: the

text: following:

label: list

text: (a)

text: If

text: F

text: for

text: all

text: i

text: and

text: the

text: ﬁber

text: q

text: is

text: connected,

text: then

text: F•

text: is

text: a

text: ﬁnite

text: minimal

text: free

text: i

text: O

text: resolution

text: of

text: the

text: normalization

text: of

text: and

text: the

text: normalization

text: has

text: rational

text: singularities.

text: V

text: O

text: (b)

text: If

text: F

text: for

text: all

text: i

text: and

text: F

text: A,

text: then

text: is

text: normal

text: and

text: it

text: has

text: rational

text: singularities.

text: i

text: V

text: O

text: Proof.

text: (a)

text: Put

text: Z

text: Z(Q,

text: β

text: α).

text: We

text: factor

text: q

text: through

text: the

text: normalization

text: Y

text: of

text: then

text: −→f

text: apply

text: Stein

text: factorization

text: to

text: obtain

text: Z

text: Y

text: Y

text: where

text: Y

text: is

text: an

text: integral

text: scheme

text: with

text: O

text: O

text: f∗

text: The

text: map

text: Y

text: Y

text: is

text: birational

text: since

text: the

text: general

text: ﬁber

text: of

text: q

text: is

text: connected.

text: Z

text: Y

text: This

text: shows

text: that

text: Y

text: Y

text: The

text: statement

text: about

text: minimal

text: free

text: resolution

text: follows

text: as

text: in

text: Theorem

text: and

text: the

text: statement

text: about

text: rational

text: singularities

text: follows

text: from

text: O

text: (b)

text: Let

text: Spec

text: A/I,

text: where

text: I

text: is

text: a

text: prime

text: ideal.

text: Applying

text: Stein

text: factorization

text: we

text: have

text: V

text: Z

text: X

text: Spec

text: A/I,

text: where

text: X

text: is

text: an

text: integral

text: aﬃne

text: scheme.

text: Since

text: F

text: A

text: and

text: F

text: for

text: i

text: all

text: i

text: Theorem

text: implies

text: that

text: X

text: Spec

text: A/J

text: for

text: some

text: prime

text: ideal

text: J.

text: But

text: Spec

text: A/J

text: Spec

text: A/I

text: is

text: surjective,

text: so

text: it

text: must

text: be

text: an

text: isomorphism.

text: The

text: rest

text: follows

text: as

text: in

text: part

text: (a).

text: A

text: partition

text: (with

text: n

text: parts)

text: λ

text: (λ

text: λ

text: λ

text: is

text: a

text: non-increasing

text: sequence

text: of

text: non-negative

text: n

text: integers.

text: For

text: a

text: partition

text: λ

text: we

text: associate

text: its

text: corresponding

text: Young

text: diagram

text: that

text: consists

text: of

text: λ

text: i

text: boxes

text: in

text: the

text: ith

text: row.

text: We

text: denote

text: the

text: number

text: of

text: boxes

text: by

text: λ

text: λ

text: λ

text: We

text: denote

text: by

text: u

text: n

text: λ

text: the

text: size

text: of

text: the

text: Durfee

text: square

text: of

text: λ,

text: that

text: is,

text: the

text: biggest

text: square

text: ﬁtting

text: inside

text: of

text: the

text: Young

text: diagram

text: of

text: λ.

text: Its

text: deﬁning

text: property

text: is

text: λ

text: u

text: and

text: λ

text: u

text: u−λ

text: λ

text: −λ

text: Let

text: λ+

text: be

text: the

text: partition

text: (λ

text: u

text: λ

text: u

text: λ

text: u

text: and

text: λ

text: the

text: partition

text: (λ

text: λ

text: λ

text: λ

text: uλ

text: λ

text: ×n

text: Hence

text: we

text: can

text: view

text: the

text: Young

text: diagram

text: of

text: λ

text: as

text: the

text: composite

text: of

text: the

text: parts

text: λ+,

text: λ

text: and

text: a

text: u

text: u

text: λ

text: λ

text: square:

text: uλ

text: uλ

text: λ+

text: λ

text: λ

text: The

text: conjugate

text: partition

text: λ

text: (λ

text: λ

text: is

text: a

text: partition

text: with

text: λ

text: being

text: the

text: number

text: of

text: boxes

text: m

text: i

text: in

text: the

text: ith

text: column

text: of

text: the

text: Young

text: diagram

text: of

text: λ.

text: Note

text: that

text: u

text: u

text: λ

text: λ

text: Denote

text: by

text: λ

text: the

text: non-increasing

text: sequence

text: of

text: non-positive

text: integers

text: λ

text: λ

text: λ

text: n

text: n

text: A

text: weight

text: (with

text: n

text: parts)

text: is

text: any

text: sequence

text: of

text: integers

text: δ

text: (δ

text: δ

text: δ

text: For

text: a

text: weight

text: δ

text: and

text: Z

text: n

text: a

text: number

text: u

text: we

text: denote

text: by

text: δ

text: u

text: the

text: weight

text: (δ

text: u,

text: δ

text: u,

text: δ

text: u).

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: We consider the action of the symmetric group Σ on weights deﬁned as follows: a transpo- n sition σ = (i, i + 1) acts according to the exchange rule i · − σ δ = (δ , . . . , δ − , δ 1, δ + 1, δ , . . . , δ ). i 1 i 1 i+1 i i+2 n ∈ · Let N(δ) be length of the (unique) permutation σ Σ such that the sequence σ δ is non- n −∞ increasing, if there exists such a permutation, otherwise put N(δ) := . In other words, N(δ) is the minimal number of exchanges applied to δ that turn it non-increasing. Clearly, we have ∈ Z N(δ) = N(δ + (cid:86)u), for any u . ≤ ≤ For any partition λ, we denote by S the corresponding Schur functor. Now for 1 t dim ξ, λ we decompose t ξ using Ca(cid:94)uchy’s form(cid:77)ula (see(cid:79)[26(cid:94)]) as in [25]: t (cid:80) ka R ⊗ Q∗ ξ = = ta ha (cid:77) a∈Q1(cid:79)ka=t a∈Q1 (cid:80) R ⊗ Q∗ = S S (cid:48) = λ(a) ta λ(a) ha | | ∈  (cid:77) a∈(cid:79)Q1 λa =t a(cid:79)Q1 (cid:79)   (cid:80) R ⊗ Q∗ = S S (cid:48) . (3) λ(a) x λ(b) x | | ∈ ∈ ∈ a∈Q1 λa =t x Q0 a Q1:ta=x b Q1:hb=x ∈ For any arrow a Q , we choose a partition λ(a) with its Young diagram having at most β 1 ∈ ta rows and at most γ columns. Now to any vertex x Q , we associate two partitions µ(x) and ha 0 ν(x) as follows. Let a , . . . , a be all outgoing arrows and b , . . . , b all the incoming arrows at 1 k 1 l x. Then choose µ(x) (resp. ν(x)) a partition corresponding to any Young diagram occurring in (cid:48) (cid:48) the Littlewood-Richardson product of λ(a ), . . . , λ(a ) (resp. λ(b ) , . . . , λ(b ) ) with at most β 1 k 1 l x rows (resp. γ rows). Denote the collection of all these partitions by x λ := ((λ(a)) ∈ , (µ(x)) ∈ , (ν(x)) ∈ ). (4) a Q1 x Q0 x Q0 R ⊗ Q∗ To compute the cohomology of a factor S S of a summand in (3), we apply µ(x) x ν(x) x Bott’s Theorem. Namely, consider the corresponding weight − δ(x) := ( ν(x), µ(x)), − where ν(x) has γ parts and µ(x) has β parts (appending with zeroes, if necessary). We have x x (see [26, Corollary 4.1.7, Corollary 4.1.9]): R ⊗ Q∗ (cid:54) Theorem 2.2. The cohomologies Hi(Gr(β , α ), S S ) vanish when i = N(δ(x)), x x µ(x) x ν(x) x and R ⊗ Q∗ HN(δ(x))(Gr(β , α ), S S ) = S V , x x µ(x) x ν(x) x τ x where τ is the non-increasing sequence obtained from δ(x). 7 ##LTLine##

text: We

text: consider

text: the

text: action

text: of

text: the

text: symmetric

text: group

text: Σ

text: on

text: weights

text: deﬁned

text: as

text: follows:

text: a

text: transpo-

text: n

text: sition

text: σ

text: (i,

text: i

text: acts

text: according

text: to

text: the

text: exchange

text: rule

text: i

text: σ

text: δ

text: (δ

text: δ

text: δ

text: δ

text: δ

text: δ

text: i

text: i

text: i

text: n

text: Let

text: N(δ)

text: be

text: length

text: of

text: the

text: (unique)

text: permutation

text: σ

text: Σ

text: such

text: that

text: the

text: sequence

text: σ

text: δ

text: is

text: non-

text: n

text: increasing,

text: if

text: there

text: exists

text: such

text: a

text: permutation,

text: otherwise

text: put

text: N(δ)

text: In

text: other

text: words,

text: N(δ)

text: is

text: the

text: minimal

text: number

text: of

text: exchanges

text: applied

text: to

text: δ

text: that

text: turn

text: it

text: non-increasing.

text: Clearly,

text: we

text: have

text: Z

text: N(δ)

text: N(δ

text: for

text: any

text: u

text: For

text: any

text: partition

text: λ,

text: we

text: denote

text: by

text: S

text: the

text: corresponding

text: Schur

text: functor.

text: Now

text: for

text: t

text: dim

text: ξ,

text: λ

text: we

text: decompose

text: t

text: ξ

text: using

text: as

text: in

text: t

text: ka

text: R

text: Q∗

text: ξ

text: ta

text: ha

text: R

text: Q∗

text: S

text: S

text: λ(a)

text: ta

text: λ(a)

text: ha

text: λa

text: =t

text: R

text: Q∗

text: S

text: S

text: λ(a)

text: x

text: λ(b)

text: x

text: λa

text: =t

text: x

text: a

text: b

text: For

text: any

text: arrow

text: a

text: Q

text: we

text: choose

text: a

text: partition

text: λ(a)

text: with

text: its

text: Young

text: diagram

text: having

text: at

text: most

text: β

text: ta

text: rows

text: and

text: at

text: most

text: γ

text: columns.

text: Now

text: to

text: any

text: vertex

text: x

text: Q

text: we

text: associate

text: two

text: partitions

text: µ(x)

text: and

text: ha

text: ν(x)

text: as

text: follows.

text: Let

text: a

text: a

text: be

text: all

text: outgoing

text: arrows

text: and

text: b

text: b

text: all

text: the

text: incoming

text: arrows

text: at

text: k

text: l

text: x.

text: Then

text: choose

text: µ(x)

text: (resp.

text: ν(x))

text: a

text: partition

text: corresponding

text: to

text: any

text: Young

text: diagram

text: occurring

text: in

text: the

text: Littlewood-Richardson

text: product

text: of

text: λ(a

text: λ(a

text: (resp.

text: λ(b

text: λ(b

text: with

text: at

text: most

text: β

text: k

text: l

text: x

text: rows

text: (resp.

text: γ

text: rows).

text: Denote

text: the

text: collection

text: of

text: all

text: these

text: partitions

text: by

text: x

text: λ

text: ((λ(a))

text: (µ(x))

text: (ν(x))

text: a

text: x

text: x

text: R

text: Q∗

text: To

text: compute

text: the

text: cohomology

text: of

text: a

text: factor

text: S

text: S

text: of

text: a

text: summand

text: in

text: we

text: apply

text: µ(x)

text: x

text: ν(x)

text: x

text: Bott’s

text: Theorem.

text: Namely,

text: consider

text: the

text: corresponding

text: weight

text: δ(x)

text: ν(x),

text: µ(x)),

text: where

text: ν(x)

text: has

text: γ

text: parts

text: and

text: µ(x)

text: has

text: β

text: parts

text: (appending

text: with

text: zeroes,

text: if

text: necessary).

text: We

text: have

text: x

text: x

text: (see

text: Corollary

text: Corollary

text: R

text: Q∗

text: Theorem

text: The

text: cohomologies

text: Hi(Gr(β

text: α

text: S

text: S

text: vanish

text: when

text: i

text: N(δ(x)),

text: x

text: x

text: µ(x)

text: x

text: ν(x)

text: x

text: and

text: R

text: Q∗

text: HN(δ(x))(Gr(β

text: α

text: S

text: S

text: S

text: V

text: x

text: x

text: µ(x)

text: x

text: ν(x)

text: x

text: τ

text: x

text: where

text: τ

text: is

text: the

text: non-increasing

text: sequence

text: obtained

text: from

text: δ(x).

text: ##LTLine##


text: 3 Minimal free resolutions of 1-step orbit closures We start with some preliminary lemmas. ≤ | | Lemma 3.1. Let λ, µ be two partitions and n the number of parts of µ. Then N(λ, µ+n) µ . ≥ Proof. We can assume WLOG that N(λ, µ + n) 0. We proceed by induction on n. Write ∈ N ≤ λ = (λ , . . . , λ ) and pick k to be the largest number with the property λ − + k µ 1 m − ≥ · m k+1 n (here set λ := 0). Then we must have λ − +k 1 µ . Applying n k exchanges we arrive m+1 m k n at the sequence − − − (λ , . . . , λ − , µ + n k, µ + n k, . . . , µ + n k, λ − + n, λ − + n, . . . , λ + n), 1 m k 1 2 n m k+1 m k+2 m and we see that the last k + 1 elements of the sequence are in their ﬁnal places. We have the following · − − N(λ, µ + n) = n k + N(λ , . . . , λ − , µ + n k, . . . , µ + n k, λ − + n, . . . , λ + n) = 1 m k 1 n m k+1 m · − − = n k + N(λ , . . . , λ − , µ + n k, . . . , µ − + n k) = 1 m k 1 n 1 · − − − − − − − − = n k + N(λ + k 1 µ , . . . , λ − + k 1 µ , µ µ + n 1, . . . , µ − µ + n 1). 1 n m k n 1 n n 1 n Now the induction hypothesis is satisﬁed and we obtain − − − − − − − − ≤ | | − · N(λ + k 1 µ , . . . , λ − + k 1 µ , µ µ + n 1, . . . , µ − µ + n 1) µ n µ . 1 n m k n 1 n n 1 n n Hence we obtain ≤ | | − ≤ | | N(λ, µ + n) µ + n(k µ ) µ . n − ≤ | | | | · Lemma 3.2. For two partitions λ, µ we have N( λ, µ) λ+ + µ+ + u u . λ µ · Proof. Put λ = (λ , . . . , λ ), µ = (µ , . . . , µ ) and u := u , v := u . After u v exchanges we get 1 m 1 n λ µ − · − − − − − − N( λ, µ) = u v + N( λ , . . . , λ , µ u, . . . , µ u, λ + v, . . . , λ + v, µ , . . . , µ ) = m u+1 1 v u 1 v+1 n · − − − − − − = u v + N( λ , . . . , λ , µ u, . . . , µ u) + N( λ + v, . . . , λ + v, µ , . . . , µ ). m u+1 1 v u 1 v+1 n Now using Lemma 3.1 we have − − − − − − ≤ | | N( λ , . . . , λ , µ u, . . . , µ u) = N( λ + u, . . . , λ + u, µ , . . . , µ ) µ+ . m u+1 1 v m u+1 1 v − − ≤ | | Similarly, we have N( λ + v, . . . , λ + v, µ , . . . , µ ) λ+ , hence the conclusion. u 1 v+1 n The following result is well-known (cf. [10]): Lemma 3.3. Suppose ν is a partition occurring in the Littlewood-Richardson product of λ and ∈ N µ. Then for any k · · · ≤ · · · · · · ν + ν + + ν λ + + λ + µ + + µ . 1 2 k 1 k 1 k 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: section

text: Minimal

text: free

text: resolutions

text: of

text: orbit

text: closures

text: We

text: start

text: with

text: some

text: preliminary

text: lemmas.

text: Lemma

text: Let

text: λ,

text: µ

text: be

text: two

text: partitions

text: and

text: n

text: the

text: number

text: of

text: parts

text: of

text: µ.

text: Then

text: N(λ,

text: µ+n)

text: µ

text: Proof.

text: We

text: can

text: assume

text: WLOG

text: that

text: N(λ,

text: µ

text: n)

text: We

text: proceed

text: by

text: induction

text: on

text: n.

text: Write

text: N

text: λ

text: (λ

text: λ

text: and

text: pick

text: k

text: to

text: be

text: the

text: largest

text: number

text: with

text: the

text: property

text: λ

text: k

text: µ

text: m

text: m

text: n

text: (here

text: set

text: λ

text: Then

text: we

text: must

text: have

text: λ

text: +k

text: µ

text: Applying

text: n

text: k

text: exchanges

text: we

text: arrive

text: m

text: k

text: n

text: at

text: the

text: sequence

text: (λ

text: λ

text: µ

text: n

text: k,

text: µ

text: n

text: k,

text: µ

text: n

text: k,

text: λ

text: n,

text: λ

text: n,

text: λ

text: n),

text: m

text: k

text: n

text: m

text: m

text: m

text: and

text: we

text: see

text: that

text: the

text: last

text: k

text: elements

text: of

text: the

text: sequence

text: are

text: in

text: their

text: ﬁnal

text: places.

text: We

text: have

text: the

text: following

text: N(λ,

text: µ

text: n)

text: n

text: k

text: N(λ

text: λ

text: µ

text: n

text: k,

text: µ

text: n

text: k,

text: λ

text: n,

text: λ

text: n)

text: m

text: k

text: n

text: m

text: m

text: n

text: k

text: N(λ

text: λ

text: µ

text: n

text: k,

text: µ

text: n

text: k)

text: m

text: k

text: n

text: n

text: k

text: N(λ

text: k

text: µ

text: λ

text: k

text: µ

text: µ

text: µ

text: n

text: µ

text: µ

text: n

text: n

text: m

text: k

text: n

text: n

text: n

text: n

text: Now

text: the

text: induction

text: hypothesis

text: is

text: satisﬁed

text: and

text: we

text: obtain

text: N(λ

text: k

text: µ

text: λ

text: k

text: µ

text: µ

text: µ

text: n

text: µ

text: µ

text: n

text: µ

text: n

text: µ

text: n

text: m

text: k

text: n

text: n

text: n

text: n

text: n

text: Hence

text: we

text: obtain

text: N(λ,

text: µ

text: n)

text: µ

text: n(k

text: µ

text: µ

text: n

text: Lemma

text: For

text: two

text: partitions

text: λ,

text: µ

text: we

text: have

text: N(

text: λ,

text: µ)

text: λ+

text: µ+

text: u

text: u

text: λ

text: µ

text: Proof.

text: Put

text: λ

text: (λ

text: λ

text: µ

text: (µ

text: µ

text: and

text: u

text: u

text: v

text: u

text: After

text: u

text: v

text: exchanges

text: we

text: get

text: m

text: n

text: λ

text: µ

text: N(

text: λ,

text: µ)

text: u

text: v

text: N(

text: λ

text: λ

text: µ

text: u,

text: µ

text: u,

text: λ

text: v,

text: λ

text: v,

text: µ

text: µ

text: m

text: v

text: u

text: n

text: u

text: v

text: N(

text: λ

text: λ

text: µ

text: u,

text: µ

text: u)

text: N(

text: λ

text: v,

text: λ

text: v,

text: µ

text: µ

text: m

text: v

text: u

text: n

text: Now

text: using

text: Lemma

text: we

text: have

text: N(

text: λ

text: λ

text: µ

text: u,

text: µ

text: u)

text: N(

text: λ

text: u,

text: λ

text: u,

text: µ

text: µ

text: µ+

text: m

text: v

text: m

text: v

text: Similarly,

text: we

text: have

text: N(

text: λ

text: v,

text: λ

text: v,

text: µ

text: µ

text: λ+

text: hence

text: the

text: conclusion.

text: u

text: n

text: The

text: following

text: result

text: is

text: well-known

text: (cf.

text: Lemma

text: Suppose

text: ν

text: is

text: a

text: partition

text: occurring

text: in

text: the

text: Littlewood-Richardson

text: product

text: of

text: λ

text: and

text: N

text: µ.

text: Then

text: for

text: any

text: k

text: ν

text: ν

text: ν

text: λ

text: λ

text: µ

text: µ

text: k

text: k

text: k

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: we work with to capture the notion of a “broadcast schedule” for multiple access channels. For the proof of Theorem 1 to be valid, the following property of such broadcast schedules needs to be satisﬁed: for any round t, the action of each station p at this round is uniquely determined by what has been heard on the channel prior to round t and how the adversary has been injecting packets S S into p prior to round t. In particular, if there are two scenarios and such that the behavior S 1 S 2 of an adversary is the same prior to some round t in both and but the behavior diﬀers at 1 2 round t in precisely that (1) the adversary injects the same number of packets into a station p at t S S in both and while (2) the numbers of packets injected into some other station q diﬀer in the 1S 2S scenarios and , then the actions taken by the station p at round t + 1 are the same under both 1 2 scenarios, while only the actions of q may diﬀer. The property that the actions of stations at a round are uniquely determined by the history prior to the round follows from the assumption that algorithms are deterministic. The property that the actions of stations at a round are aﬀected by other stations only through what has been heard on the channel prior to the round holds because algorithms are assumed to be distributed. The sequence t , t , t , . . . of milestone rounds, as considered in the proof of Theorem 1, may 0 1 2 − ≥ have the property that there is no upper bound on the diﬀerences t t , for i 0. If such i+1 i an upper bound, say w, existed, then the behavior of the adversary would be consistent with the deﬁnition of type (1, w) window adversary. It follows from Theorem 3, given in the part of this section devoted to window adversaries, that one cannot strengthen the proof above to show existence of such a bound, as otherwise impossibility would hold for window adversaries. Regarding window adversaries, possibility is shown for three stations in Theorem 5 of Section , while impossibility holds for four stations, as shown in Corollary 1 of Section . When algorithms are restricted to be full sensing, then even stability is not possible to be achieved in a system of two stations, as we show next. The proof of Theorem 2 relies on the property that messages cannot carry control bits to redirect the course of action of listening stations. This property can be formally abstracted as follows: Consider a full sensing algorithm and two scenarios S S and for a system of two stations. If station p has the same injections up to round t under the 1 2 two scenarios, while station q transmits at the same rounds up to round t under the two scenarios, then p cannot detect any diﬀerence between the injections into q under the two scenarios up to S S round t, so p is at the same state at the beginning of round t under both and . 1 2 Theorem 2 No full sensing algorithm can be stable for a system of at least two stations against the leaky-bucket adversary with burstiness 2. E P Proof: We show that the adversary can enforce an execution of with inﬁnitely many void rounds, while maintaining the average injection rate 1. Similarly as in the proof of Theorem 1, ≥ we identify consecutive milestone rounds t , t , t , . . ., where t < t for any i 0, and specify 0 1 2 i i+1 how packets are injected at every round. If a void round occurs before the end of the described construction, then this gives a milestone round and we are done. Thus we will always consider a scenario in which the current round is not a void one, whenever logically possible. Let the adversary inject one packet into q at the ﬁrst round, and deﬁne t to be the ﬁrst round E P E 0 of execution of . Round t is void in because no packets have been injected before the E0 round. Suppose the execution and injections have been deﬁned by a milestone round t , for some ≥ i i 0, we deﬁne the milestone round t > t and how packets are injected in the interval starting E i+1 i from t + 1 through t in . i i+1 14

text: we

text: work

text: with

text: to

text: capture

text: the

text: notion

text: of

text: a

text: “broadcast

text: schedule”

text: for

text: multiple

text: access

text: channels.

text: For

text: the

text: proof

text: of

text: Theorem

text: to

text: be

text: valid,

text: the

text: following

text: property

text: of

text: such

text: broadcast

text: schedules

text: needs

text: to

text: be

text: satisﬁed:

text: for

text: any

text: round

text: t,

text: the

text: action

text: of

text: each

text: station

text: p

text: at

text: this

text: round

text: is

text: uniquely

text: determined

text: by

text: what

text: has

text: been

text: heard

text: on

text: the

text: channel

text: prior

text: to

text: round

text: t

text: and

text: how

text: the

text: adversary

text: has

text: been

text: injecting

text: packets

text: S

text: S

text: into

text: p

text: prior

text: to

text: round

text: t.

text: In

text: particular,

text: if

text: there

text: are

text: two

text: scenarios

text: and

text: such

text: that

text: the

text: behavior

text: S

text: S

text: of

text: an

text: adversary

text: is

text: the

text: same

text: prior

text: to

text: some

text: round

text: t

text: in

text: both

text: and

text: but

text: the

text: behavior

text: diﬀers

text: at

text: round

text: t

text: in

text: precisely

text: that

text: the

text: adversary

text: injects

text: the

text: same

text: number

text: of

text: packets

text: into

text: a

text: station

text: p

text: at

text: t

text: S

text: S

text: in

text: both

text: and

text: while

text: the

text: numbers

text: of

text: packets

text: injected

text: into

text: some

text: other

text: station

text: q

text: diﬀer

text: in

text: the

text: scenarios

text: and

text: then

text: the

text: actions

text: taken

text: by

text: the

text: station

text: p

text: at

text: round

text: t

text: are

text: the

text: same

text: under

text: both

text: scenarios,

text: while

text: only

text: the

text: actions

text: of

text: q

text: may

text: diﬀer.

text: The

text: property

text: that

text: the

text: actions

text: of

text: stations

text: at

text: a

text: round

text: are

text: uniquely

text: determined

text: by

text: the

text: history

text: prior

text: to

text: the

text: round

text: follows

text: from

text: the

text: assumption

text: that

text: algorithms

text: are

text: deterministic.

text: The

text: property

text: that

text: the

text: actions

text: of

text: stations

text: at

text: a

text: round

text: are

text: aﬀected

text: by

text: other

text: stations

text: only

text: through

text: what

text: has

text: been

text: heard

text: on

text: the

text: channel

text: prior

text: to

text: the

text: round

text: holds

text: because

text: algorithms

text: are

text: assumed

text: to

text: be

text: distributed.

text: The

text: sequence

text: t

text: t

text: t

text: of

text: milestone

text: rounds,

text: as

text: considered

text: in

text: the

text: proof

text: of

text: Theorem

text: may

text: have

text: the

text: property

text: that

text: there

text: is

text: no

text: upper

text: bound

text: on

text: the

text: diﬀerences

text: t

text: t

text: for

text: i

text: If

text: such

text: i

text: an

text: upper

text: bound,

text: say

text: w,

text: existed,

text: then

text: the

text: behavior

text: of

text: the

text: adversary

text: would

text: be

text: consistent

text: with

text: the

text: deﬁnition

text: of

text: type

text: w)

text: window

text: adversary.

text: It

text: follows

text: from

text: Theorem

text: given

text: in

text: the

text: part

text: of

text: this

text: section

text: devoted

text: to

text: window

text: adversaries,

text: that

text: one

text: cannot

text: strengthen

text: the

text: proof

text: above

text: to

text: show

text: existence

text: of

text: such

text: a

text: bound,

text: as

text: otherwise

text: impossibility

text: would

text: hold

text: for

text: window

text: adversaries.

text: Regarding

text: window

text: adversaries,

text: possibility

text: is

text: shown

text: for

text: three

text: stations

text: in

text: Theorem

text: of

text: Section

text: while

text: impossibility

text: holds

text: for

text: four

text: stations,

text: as

text: shown

text: in

text: Corollary

text: of

text: Section

text: When

text: algorithms

text: are

text: restricted

text: to

text: be

text: full

text: sensing,

text: then

text: even

text: stability

text: is

text: not

text: possible

text: to

text: be

text: achieved

text: in

text: a

text: system

text: of

text: two

text: stations,

text: as

text: we

text: show

text: next.

text: The

text: proof

text: of

text: Theorem

text: relies

text: on

text: the

text: property

text: that

text: messages

text: cannot

text: carry

text: control

text: bits

text: to

text: redirect

text: the

text: course

text: of

text: action

text: of

text: listening

text: stations.

text: This

text: property

text: can

text: be

text: formally

text: abstracted

text: as

text: follows:

text: Consider

text: a

text: full

text: sensing

text: algorithm

text: and

text: two

text: scenarios

text: S

text: S

text: and

text: for

text: a

text: system

text: of

text: two

text: stations.

text: If

text: station

text: p

text: has

text: the

text: same

text: injections

text: up

text: to

text: round

text: t

text: under

text: the

text: two

text: scenarios,

text: while

text: station

text: q

text: transmits

text: at

text: the

text: same

text: rounds

text: up

text: to

text: round

text: t

text: under

text: the

text: two

text: scenarios,

text: then

text: p

text: cannot

text: detect

text: any

text: diﬀerence

text: between

text: the

text: injections

text: into

text: q

text: under

text: the

text: two

text: scenarios

text: up

text: to

text: S

text: S

text: round

text: t,

text: so

text: p

text: is

text: at

text: the

text: same

text: state

text: at

text: the

text: beginning

text: of

text: round

text: t

text: under

text: both

text: and

text: Theorem

text: No

text: full

text: sensing

text: algorithm

text: can

text: be

text: stable

text: for

text: a

text: system

text: of

text: at

text: least

text: two

text: stations

text: against

text: the

text: leaky-bucket

text: adversary

text: with

text: burstiness

text: E

text: P

text: Proof:

text: We

text: show

text: that

text: the

text: adversary

text: can

text: enforce

text: an

text: execution

text: of

text: with

text: inﬁnitely

text: many

text: void

text: rounds,

text: while

text: maintaining

text: the

text: average

text: injection

text: rate

text: Similarly

text: as

text: in

text: the

text: proof

text: of

text: Theorem

text: we

text: identify

text: consecutive

text: milestone

text: rounds

text: t

text: t

text: t

text: where

text: t

text: t

text: for

text: any

text: i

text: and

text: specify

text: i

text: how

text: packets

text: are

text: injected

text: at

text: every

text: round.

text: If

text: a

text: void

text: round

text: occurs

text: before

text: the

text: end

text: of

text: the

text: described

text: construction,

text: then

text: this

text: gives

text: a

text: milestone

text: round

text: and

text: we

text: are

text: done.

text: Thus

text: we

text: will

text: always

text: consider

text: a

text: scenario

text: in

text: which

text: the

text: current

text: round

text: is

text: not

text: a

text: void

text: one,

text: whenever

text: logically

text: possible.

text: Let

text: the

text: adversary

text: inject

text: one

text: packet

text: into

text: q

text: at

text: the

text: ﬁrst

text: round,

text: and

text: deﬁne

text: t

text: to

text: be

text: the

text: ﬁrst

text: round

text: E

text: P

text: E

text: of

text: execution

text: of

text: Round

text: t

text: is

text: void

text: in

text: because

text: no

text: packets

text: have

text: been

text: injected

text: before

text: the

text: round.

text: Suppose

text: the

text: execution

text: and

text: injections

text: have

text: been

text: deﬁned

text: by

text: a

text: milestone

text: round

text: t

text: for

text: some

text: i

text: i

text: we

text: deﬁne

text: the

text: milestone

text: round

text: t

text: t

text: and

text: how

text: packets

text: are

text: injected

text: in

text: the

text: interval

text: starting

text: E

text: i

text: from

text: t

text: through

text: t

text: in

text: i


text: Station g has informed the remaining stations about this fact by the transmission at the last round of the current phase. Now the situation is similar as in the previous case after g sent the “over” (cid:48) (cid:48)(cid:48) signal, with k = i. If any among g or g has received i packets to be available for the next phase, then this station unloads all its i available packets in the remaining rounds of the next phase, and (cid:48) also gains the status to be the last station for the next phase. Otherwise station g starts unloading (cid:48)(cid:48) its available packets, if any, while g gains the status to be the last station for the next phase. (cid:48)(cid:48) Station g takes over as soon as either silence or the “over” signal is heard. Lemma 1 Algorithm 3-Adaptive-Window(w) provides packet latency at most 2w + 1 against the adversary with window size w in a system of three stations. Proof: It is suﬃcient to show that all the packets available at the end of a phase are transmitted in the next phase. This is because there are w rounds during which packets are injected to be available for the next phase, followed by the last round of the current phase, and w rounds of the next phase. The proof is by induction on the numbers of phases. No packets are injected before the ﬁrst phase, therefore the base of induction holds for the ﬁrst phase by default. Next we show the inductive step. Consider some current phase and suppose that when the next phase starts, then there are no packets available for the current phase still in queues. Consider a packet u available for the next phase. If u was injected into a station g that is the last one for the current phase, then station g indicates in the transmission at the last round of the current phase that it holds packets available for the next phase. This allows g to unload all its packets, including u, starting from the ﬁrst round of the next phase. (cid:48) Next suppose that packet u resides at g . If g has no packets available for the next phase, then (cid:48) (cid:48) g knows this after the last round of the current phase and so g may start unloading all its available packets, including u, starting from the ﬁrst round of the next phase. Otherwise station g unloads (cid:48) its available packets ﬁrst, and then station g takes over without a delay after station g is done, and unloads all its available packets including u. (cid:48)(cid:48) (cid:48)(cid:48) Finally, suppose that u was injected into g . If g has w packets available for the next phase, (cid:48)(cid:48) then g has no such packets and g begins unloading its packets starting from the ﬁrst round of the (cid:48)(cid:48) next phase, by the speciﬁcation of the algorithm. Suppose that g has k packets available for the − − next phase, where k < w. If g has w k available packets, then after w k rounds of the next (cid:48)(cid:48) phase, station g knows that it needs to transmit in the remaining k rounds of this phase, which (cid:48)(cid:48) − g does. Otherwise, when g has some (cid:96) < w k available packets, possibly (cid:96) = 0, then eventually (cid:48) (cid:48) − − all these packets have been heard and g is to take over. Station g has at most w k (cid:96) packets (cid:48) (cid:48)(cid:48) available for the next phase, so after the packets of g and g have been heard and station g takes over, there are at least k rounds in the phase, so packet u is transmitted in one of them. These cases exhaust all the possibilities, which shows that u is transmitted eventually in the next phase. (cid:3) This completes the proof of the inductive step. We show next that there is a stable and fair algorithm for three stations that does not rely on the knowledge of the window but but resorts to the mechanism of collision detection. The algorithm is called 3-Adaptive-Col-Det. It is obtained by modifying algorithm 3-Adaptive- Window(i) as follow. Initially algorithm 3-Adaptive-Col-Det runs 3-Adaptive-Window(1) 20

text: Station

text: g

text: has

text: informed

text: the

text: remaining

text: stations

text: about

text: this

text: fact

text: by

text: the

text: transmission

text: at

text: the

text: last

text: round

text: of

text: the

text: current

text: phase.

text: Now

text: the

text: situation

text: is

text: similar

text: as

text: in

text: the

text: previous

text: case

text: after

text: g

text: sent

text: the

text: “over”

text: signal,

text: with

text: k

text: i.

text: If

text: any

text: among

text: g

text: or

text: g

text: has

text: received

text: i

text: packets

text: to

text: be

text: available

text: for

text: the

text: next

text: phase,

text: then

text: this

text: station

text: unloads

text: all

text: its

text: i

text: available

text: packets

text: in

text: the

text: remaining

text: rounds

text: of

text: the

text: next

text: phase,

text: and

text: also

text: gains

text: the

text: status

text: to

text: be

text: the

text: last

text: station

text: for

text: the

text: next

text: phase.

text: Otherwise

text: station

text: g

text: starts

text: unloading

text: its

text: available

text: packets,

text: if

text: any,

text: while

text: g

text: gains

text: the

text: status

text: to

text: be

text: the

text: last

text: station

text: for

text: the

text: next

text: phase.

text: Station

text: g

text: takes

text: over

text: as

text: soon

text: as

text: either

text: silence

text: or

text: the

text: “over”

text: signal

text: is

text: heard.

text: Lemma

text: Algorithm

text: provides

text: packet

text: latency

text: at

text: most

text: against

text: the

text: adversary

text: with

text: window

text: size

text: w

text: in

text: a

text: system

text: of

text: three

text: stations.

text: Proof:

text: It

text: is

text: suﬃcient

text: to

text: show

text: that

text: all

text: the

text: packets

text: available

text: at

text: the

text: end

text: of

text: a

text: phase

text: are

text: transmitted

text: in

text: the

text: next

text: phase.

text: This

text: is

text: because

text: there

text: are

text: w

text: rounds

text: during

text: which

text: packets

text: are

text: injected

text: to

text: be

text: available

text: for

text: the

text: next

text: phase,

text: followed

text: by

text: the

text: last

text: round

text: of

text: the

text: current

text: phase,

text: and

text: w

text: rounds

text: of

text: the

text: next

text: phase.

text: The

text: proof

text: is

text: by

text: induction

text: on

text: the

text: numbers

text: of

text: phases.

text: No

text: packets

text: are

text: injected

text: before

text: the

text: ﬁrst

text: phase,

text: therefore

text: the

text: base

text: of

text: induction

text: holds

text: for

text: the

text: ﬁrst

text: phase

text: by

text: default.

text: Next

text: we

text: show

text: the

text: inductive

text: step.

text: Consider

text: some

text: current

text: phase

text: and

text: suppose

text: that

text: when

text: the

text: next

text: phase

text: starts,

text: then

text: there

text: are

text: no

text: packets

text: available

text: for

text: the

text: current

text: phase

text: still

text: in

text: queues.

text: Consider

text: a

text: packet

text: u

text: available

text: for

text: the

text: next

text: phase.

text: If

text: u

text: was

text: injected

text: into

text: a

text: station

text: g

text: that

text: is

text: the

text: last

text: one

text: for

text: the

text: current

text: phase,

text: then

text: station

text: g

text: indicates

text: in

text: the

text: transmission

text: at

text: the

text: last

text: round

text: of

text: the

text: current

text: phase

text: that

text: it

text: holds

text: packets

text: available

text: for

text: the

text: next

text: phase.

text: This

text: allows

text: g

text: to

text: unload

text: all

text: its

text: packets,

text: including

text: u,

text: starting

text: from

text: the

text: ﬁrst

text: round

text: of

text: the

text: next

text: phase.

text: Next

text: suppose

text: that

text: packet

text: u

text: resides

text: at

text: g

text: If

text: g

text: has

text: no

text: packets

text: available

text: for

text: the

text: next

text: phase,

text: then

text: g

text: knows

text: this

text: after

text: the

text: last

text: round

text: of

text: the

text: current

text: phase

text: and

text: so

text: g

text: may

text: start

text: unloading

text: all

text: its

text: available

text: packets,

text: including

text: u,

text: starting

text: from

text: the

text: ﬁrst

text: round

text: of

text: the

text: next

text: phase.

text: Otherwise

text: station

text: g

text: unloads

text: its

text: available

text: packets

text: ﬁrst,

text: and

text: then

text: station

text: g

text: takes

text: over

text: without

text: a

text: delay

text: after

text: station

text: g

text: is

text: done,

text: and

text: unloads

text: all

text: its

text: available

text: packets

text: including

text: u.

text: Finally,

text: suppose

text: that

text: u

text: was

text: injected

text: into

text: g

text: If

text: g

text: has

text: w

text: packets

text: available

text: for

text: the

text: next

text: phase,

text: then

text: g

text: has

text: no

text: such

text: packets

text: and

text: g

text: begins

text: unloading

text: its

text: packets

text: starting

text: from

text: the

text: ﬁrst

text: round

text: of

text: the

text: next

text: phase,

text: by

text: the

text: speciﬁcation

text: of

text: the

text: algorithm.

text: Suppose

text: that

text: g

text: has

text: k

text: packets

text: available

text: for

text: the

text: next

text: phase,

text: where

text: k

text: w.

text: If

text: g

text: has

text: w

text: k

text: available

text: packets,

text: then

text: after

text: w

text: k

text: rounds

text: of

text: the

text: next

text: phase,

text: station

text: g

text: knows

text: that

text: it

text: needs

text: to

text: transmit

text: in

text: the

text: remaining

text: k

text: rounds

text: of

text: this

text: phase,

text: which

text: g

text: does.

text: Otherwise,

text: when

text: g

text: has

text: some

text: w

text: k

text: available

text: packets,

text: possibly

text: then

text: eventually

text: all

text: these

text: packets

text: have

text: been

text: heard

text: and

text: g

text: is

text: to

text: take

text: over.

text: Station

text: g

text: has

text: at

text: most

text: w

text: k

text: packets

text: available

text: for

text: the

text: next

text: phase,

text: so

text: after

text: the

text: packets

text: of

text: g

text: and

text: g

text: have

text: been

text: heard

text: and

text: station

text: g

text: takes

text: over,

text: there

text: are

text: at

text: least

text: k

text: rounds

text: in

text: the

text: phase,

text: so

text: packet

text: u

text: is

text: transmitted

text: in

text: one

text: of

text: them.

text: These

text: cases

text: exhaust

text: all

text: the

text: possibilities,

text: which

text: shows

text: that

text: u

text: is

text: transmitted

text: eventually

text: in

text: the

text: next

text: phase.

text: This

text: completes

text: the

text: proof

text: of

text: the

text: inductive

text: step.

text: We

text: show

text: next

text: that

text: there

text: is

text: a

text: stable

text: and

text: fair

text: algorithm

text: for

text: three

text: stations

text: that

text: does

text: not

text: rely

text: on

text: the

text: knowledge

text: of

text: the

text: window

text: but

text: but

text: resorts

text: to

text: the

text: mechanism

text: of

text: collision

text: detection.

text: The

text: algorithm

text: is

text: called

text: It

text: is

text: obtained

text: by

text: modifying

text: algorithm

text: Window(i)

text: as

text: follow.

text: Initially

text: algorithm

text: runs


text: to try the window w = 1. When a collision occurs while running 3-Adaptive-Window(i), then 3- Adaptive-Window(i+1) is invoked. We apply a similar approach as in Section by using a queue called DELAY. Packets stored already in the queues at a round when 3-Adaptive-Window(i+1) is invoked are called old. First the old packets are transmitted, by the stations p, q and r, in this order, while records of actions of the adversary are enqueued, with an entry for each round. A transition to the next station is indicated either by a control bit “over” attached to the last old packet of a station or by only this bit transmitted when the station does not have any old packets. After all the old packets have been heard, the stations start executing 3-Adaptive-Window(i + 1). To this end, they keep dequeuing DELAY, if it is nonempty, while simultaneously enqueueing the current actions of the adversary. Details are as follows. An invocation of 3-Adaptive-Window(i + 1) starts with the ﬁrst phase of i+1 rounds. During the i initial rounds the stations pause storing up to i packets to be available for the next phase. When multiple invocations of 3-Adaptive-Window(i) are performed back-to-back, for consecutive values of i, we can modify the action performed during a transition from i to i+1 to save on void rounds: let the stations begin 3-Adaptive-Window(i+1) by dequeuing either i + 1 entries from the queue DELAY or all of them, whichever is smaller, and let this contribute towards the beginning of the ﬁrst phase of 3-Adaptive-Window(i + 1). Next the stations dequeue one entry per round, unless DELAY is empty, in which case it is not used. Lemma 2 Algorithm 3-Adaptive-Col-Det is of fair latency in a system of three stations with a channel with collision detection. Proof: The proof is similar to that of Theorem 3, with some arguments provided by Lemma 1. − There are at most w 1 collisions before the correct window size is reached. Each collision triggers unloading old packets. Each such an instance of transmitting old packets may cause at most one void round because at most one station holds no packets. The cumulative eﬀect of ﬁrst phases consisting of void rounds of procedures 3-Adaptive-Window(i), for consecutive values of i, contributes an − additional delay of at most w. This is because transition to i from i 1, for i > 1, begins by dequeuing up to i entries form DELAY: when there are less than i entries in DELAY, then up to i void rounds are generated, but when there are at least i of them then no extra void round occurs. By Lemma 1, after the size of the window has been set correctly, packet delay is at most 2w + 1. − − (cid:3) Thus the total delay of a packet is at most w 1 + w 1 + w + 2w + 1 < 5w. Next we present the ultimate algorithm for three stations for the channel without collision detection, it is called 3-Adaptive. We simulate algorithm 3-Adaptive-Col-Det by detecting collisions by silences. Consider a phase that is at least second after an invocation of 3-Adaptive- ≥ Window(i) in 3-Adaptive-Col-Det, for i 1. If a collision occurs at a round of such a phase (cid:48) that is not the last one in the phase, then there are only two stations involved, say, g and g , by the design of 3-Adaptive-Col-Det. In such a case, the station g stops transmissions in this (cid:48) (cid:48)(cid:48) phase while station g continues by repeating the last transmission. At this point the station g (cid:48)(cid:48) may not know about the collision. To allow g learn this, we use the property of 3-Adaptive- Col-Det that some station transmits at the last round of every phase. Let every station that knows about a collision in a phase transmit at the last round of the phase, the contents being a dummy message for a station that is not designated to be the last one for the phase. All the stations hear silence at this round, so all of them learn of collision, which triggers an invocation of 3-Adaptive-Window(i + 1). If the ﬁrst collision in a phase occurs at the last round of the phase, then this automatically makes every station learn about the collision by the silence heard, which immediately triggers an invocation of 3-Adaptive-Window(i + 1). 21

text: to

text: try

text: the

text: window

text: w

text: When

text: a

text: collision

text: occurs

text: while

text: running

text: then

text: is

text: invoked.

text: We

text: apply

text: a

text: similar

text: approach

text: as

text: in

text: Section

text: by

text: using

text: a

text: queue

text: called

text: DELAY.

text: Packets

text: stored

text: already

text: in

text: the

text: queues

text: at

text: a

text: round

text: when

text: is

text: invoked

text: are

text: called

text: old.

text: First

text: the

text: old

text: packets

text: are

text: transmitted,

text: by

text: the

text: stations

text: p,

text: q

text: and

text: r,

text: in

text: this

text: order,

text: while

text: records

text: of

text: actions

text: of

text: the

text: adversary

text: are

text: enqueued,

text: with

text: an

text: entry

text: for

text: each

text: round.

text: A

text: transition

text: to

text: the

text: next

text: station

text: is

text: indicated

text: either

text: by

text: a

text: control

text: bit

text: “over”

text: attached

text: to

text: the

text: last

text: old

text: packet

text: of

text: a

text: station

text: or

text: by

text: only

text: this

text: bit

text: transmitted

text: when

text: the

text: station

text: does

text: not

text: have

text: any

text: old

text: packets.

text: After

text: all

text: the

text: old

text: packets

text: have

text: been

text: heard,

text: the

text: stations

text: start

text: executing

text: To

text: this

text: end,

text: they

text: keep

text: dequeuing

text: DELAY,

text: if

text: it

text: is

text: nonempty,

text: while

text: simultaneously

text: enqueueing

text: the

text: current

text: actions

text: of

text: the

text: adversary.

text: Details

text: are

text: as

text: follows.

text: An

text: invocation

text: of

text: starts

text: with

text: the

text: ﬁrst

text: phase

text: of

text: rounds.

text: During

text: the

text: i

text: initial

text: rounds

text: the

text: stations

text: pause

text: storing

text: up

text: to

text: i

text: packets

text: to

text: be

text: available

text: for

text: the

text: next

text: phase.

text: When

text: multiple

text: invocations

text: of

text: are

text: performed

text: back-to-back,

text: for

text: consecutive

text: values

text: of

text: i,

text: we

text: can

text: modify

text: the

text: action

text: performed

text: during

text: a

text: transition

text: from

text: i

text: to

text: to

text: save

text: on

text: void

text: rounds:

text: let

text: the

text: stations

text: begin

text: by

text: dequeuing

text: either

text: i

text: entries

text: from

text: the

text: queue

text: DELAY

text: or

text: all

text: of

text: them,

text: whichever

text: is

text: smaller,

text: and

text: let

text: this

text: contribute

text: towards

text: the

text: beginning

text: of

text: the

text: ﬁrst

text: phase

text: of

text: Next

text: the

text: stations

text: dequeue

text: one

text: entry

text: per

text: round,

text: unless

text: DELAY

text: is

text: empty,

text: in

text: which

text: case

text: it

text: is

text: not

text: used.

text: Lemma

text: Algorithm

text: is

text: of

text: fair

text: latency

text: in

text: a

text: system

text: of

text: three

text: stations

text: with

text: a

text: channel

text: with

text: collision

text: detection.

text: Proof:

text: The

text: proof

text: is

text: similar

text: to

text: that

text: of

text: Theorem

text: with

text: some

text: arguments

text: provided

text: by

text: Lemma

text: There

text: are

text: at

text: most

text: w

text: collisions

text: before

text: the

text: correct

text: window

text: size

text: is

text: reached.

text: Each

text: collision

text: triggers

text: unloading

text: old

text: packets.

text: Each

text: such

text: an

text: instance

text: of

text: transmitting

text: old

text: packets

text: may

text: cause

text: at

text: most

text: one

text: void

text: round

text: because

text: at

text: most

text: one

text: station

text: holds

text: no

text: packets.

text: The

text: cumulative

text: eﬀect

text: of

text: ﬁrst

text: phases

text: consisting

text: of

text: void

text: rounds

text: of

text: procedures

text: for

text: consecutive

text: values

text: of

text: i,

text: contributes

text: an

text: additional

text: delay

text: of

text: at

text: most

text: w.

text: This

text: is

text: because

text: transition

text: to

text: i

text: from

text: i

text: for

text: i

text: begins

text: by

text: dequeuing

text: up

text: to

text: i

text: entries

text: form

text: DELAY:

text: when

text: there

text: are

text: less

text: than

text: i

text: entries

text: in

text: DELAY,

text: then

text: up

text: to

text: i

text: void

text: rounds

text: are

text: generated,

text: but

text: when

text: there

text: are

text: at

text: least

text: i

text: of

text: them

text: then

text: no

text: extra

text: void

text: round

text: occurs.

text: By

text: Lemma

text: after

text: the

text: size

text: of

text: the

text: window

text: has

text: been

text: set

text: correctly,

text: packet

text: delay

text: is

text: at

text: most

text: Thus

text: the

text: total

text: delay

text: of

text: a

text: packet

text: is

text: at

text: most

text: w

text: w

text: w

text: Next

text: we

text: present

text: the

text: ultimate

text: algorithm

text: for

text: three

text: stations

text: for

text: the

text: channel

text: without

text: collision

text: detection,

text: it

text: is

text: called

text: We

text: simulate

text: algorithm

text: by

text: detecting

text: collisions

text: by

text: silences.

text: Consider

text: a

text: phase

text: that

text: is

text: at

text: least

text: second

text: after

text: an

text: invocation

text: of

text: Window(i)

text: in

text: for

text: i

text: If

text: a

text: collision

text: occurs

text: at

text: a

text: round

text: of

text: such

text: a

text: phase

text: that

text: is

text: not

text: the

text: last

text: one

text: in

text: the

text: phase,

text: then

text: there

text: are

text: only

text: two

text: stations

text: involved,

text: say,

text: g

text: and

text: g

text: by

text: the

text: design

text: of

text: In

text: such

text: a

text: case,

text: the

text: station

text: g

text: stops

text: transmissions

text: in

text: this

text: phase

text: while

text: station

text: g

text: continues

text: by

text: repeating

text: the

text: last

text: transmission.

text: At

text: this

text: point

text: the

text: station

text: g

text: may

text: not

text: know

text: about

text: the

text: collision.

text: To

text: allow

text: g

text: learn

text: this,

text: we

text: use

text: the

text: property

text: of

text: Col-Det

text: that

text: some

text: station

text: transmits

text: at

text: the

text: last

text: round

text: of

text: every

text: phase.

text: Let

text: every

text: station

text: that

text: knows

text: about

text: a

text: collision

text: in

text: a

text: phase

text: transmit

text: at

text: the

text: last

text: round

text: of

text: the

text: phase,

text: the

text: contents

text: being

text: a

text: dummy

text: message

text: for

text: a

text: station

text: that

text: is

text: not

text: designated

text: to

text: be

text: the

text: last

text: one

text: for

text: the

text: phase.

text: All

text: the

text: stations

text: hear

text: silence

text: at

text: this

text: round,

text: so

text: all

text: of

text: them

text: learn

text: of

text: collision,

text: which

text: triggers

text: an

text: invocation

text: of

text: If

text: the

text: ﬁrst

text: collision

text: in

text: a

text: phase

text: occurs

text: at

text: the

text: last

text: round

text: of

text: the

text: phase,

text: then

text: this

text: automatically

text: makes

text: every

text: station

text: learn

text: about

text: the

text: collision

text: by

text: the

text: silence

text: heard,

text: which

text: immediately

text: triggers

text: an

text: invocation

text: of