text: Full sensing algorithms with collision detection. We continue with estimates of packet latency of algorithms Search-Round-Robin (SRR) and Older-First-Search-Round-Robin (OF-SRR), both of which use collision detection. Executions are partitioned into phases, similarly as when considering any older-go-ﬁrst type of algorithm. In the case of algorithm Search-Round- Robin, a phase denotes one full sweep of searches through the range of names of stations. We begin with a technical estimate that will be used in proving bounds on packet latency. Let (cid:100) (cid:101) lg x denote log x . 2 ≥ ≤ ≤ Lemma 5 If there are x 1 packets in the system in a round then, for each 1 y x, algorithms SRR and OF-SRR make y packets heard in the next min(y lg n, 2n + y) rounds. Proof: We argue ﬁrst that each of the considered algorithms takes no more than 2n+y consecutive rounds to transmit successfully at least y packets. It takes at most n rounds with no transmission ≤ to identify stations that store at least y x packets for SRR, because the token needs to make at most one full cycle along the list of stations. Similarly, it takes at most 2n rounds with no ≤ transmission to identify stations that store at least y x packets for OF-SRR. This is because two phases are needed in the worst case, when the ﬁrst phase results in discovering too few old packets. Uploading these y packets takes y rounds. This completes the ﬁrst part of the argument. Next, we prove that these algorithms need no more than y lg n consecutive rounds to upload y packets. Indeed, after a packet has been transmitted, it takes time at most the height of a conceptual search tree to identify another station with an eligible packet. This height is at most lg n, so a (cid:3) packet is heard at least once in any contiguous segment of lg n rounds. Theorem 6 The packet latency for algorithm OF-SRR executed against the adversary of type ≤ (ρ, b) is at most 4 min(b lg n, n + b) for ρ 1 , and it is at most 4n−+2b for ρ > 1 . 2lg n 1 ρ 2lg n Proof: A packet is transmitted successfully by the end of the phase following the one in which it was injected. So the maximum packet latency is upper bounded by twice the maximum length | | | | of a phase. At most ρ τ + b packets get injected in a time interval τ of length τ . The maximum number of packets in the system is upper bounded by the maximum number of packets at the end of an interval plus the number of packets injected within this interval. ≤ Let us begin with the case ρ 1 . We ﬁrst argue that at the end of a round there are at · 2lg n most ρ min(2b lg n, 2n + 2b) + b packets in the system. Suppose it is otherwise and consider the · ﬁrst round t with the number of packets more than ρ min(2b lg n, 2n + 2b) + b at the end of it. Note that t > min(2b lg n, 2n + 2b), as at most ρ min(2b lg n, 2n + 2b) + b packets are injected into the system in the time interval [1, min(2b lg n, 2n + 2b)]. This follows from the assumption that, at − the end of round t min(2b lg n, 2n + 2b), there were at most · ρ min(2b lg n, 2n + 2b) + b packets in the system. From that round until round t, at least this number of packets have been successfully transmitted, by Lemma 5 and the estimate · ≤ 2b lg n ρ min(2b lg n, 2n + 2b) + b + b = 2b , 2 lg n 21 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Full

text: sensing

text: algorithms

text: with

text: collision

text: detection.

text: We

text: continue

text: with

text: estimates

text: of

text: packet

text: latency

text: of

text: algorithms

text: Search-Round-Robin

text: (SRR)

text: and

text: Older-First-Search-Round-Robin

text: (OF-SRR),

text: both

text: of

text: which

text: use

text: collision

text: detection.

text: Executions

text: are

text: partitioned

text: into

text: phases,

text: similarly

text: as

text: when

text: considering

text: any

text: older-go-ﬁrst

text: type

text: of

text: algorithm.

text: In

text: the

text: case

text: of

text: algorithm

text: Search-Round-

text: Robin,

text: a

text: phase

text: denotes

text: one

text: full

text: sweep

text: of

text: searches

text: through

text: the

text: range

text: of

text: names

text: of

text: stations.

text: We

text: begin

text: with

text: a

text: technical

text: estimate

text: that

text: will

text: be

text: used

text: in

text: proving

text: bounds

text: on

text: packet

text: latency.

text: Let

text: lg

text: x

text: denote

text: log

text: x

text: Lemma

text: If

text: there

text: are

text: x

text: packets

text: in

text: the

text: system

text: in

text: a

text: round

text: then,

text: for

text: each

text: y

text: x,

text: algorithms

text: SRR

text: and

text: OF-SRR

text: make

text: y

text: packets

text: heard

text: in

text: the

text: next

text: min(y

text: lg

text: n,

text: y)

text: rounds.

text: Proof:

text: We

text: argue

text: ﬁrst

text: that

text: each

text: of

text: the

text: considered

text: algorithms

text: takes

text: no

text: more

text: than

text: consecutive

text: rounds

text: to

text: transmit

text: successfully

text: at

text: least

text: y

text: packets.

text: It

text: takes

text: at

text: most

text: n

text: rounds

text: with

text: no

text: transmission

text: to

text: identify

text: stations

text: that

text: store

text: at

text: least

text: y

text: x

text: packets

text: for

text: SRR,

text: because

text: the

text: token

text: needs

text: to

text: make

text: at

text: most

text: one

text: full

text: cycle

text: along

text: the

text: list

text: of

text: stations.

text: Similarly,

text: it

text: takes

text: at

text: most

text: rounds

text: with

text: no

text: transmission

text: to

text: identify

text: stations

text: that

text: store

text: at

text: least

text: y

text: x

text: packets

text: for

text: OF-SRR.

text: This

text: is

text: because

text: two

text: phases

text: are

text: needed

text: in

text: the

text: worst

text: case,

text: when

text: the

text: ﬁrst

text: phase

text: results

text: in

text: discovering

text: too

text: few

text: old

text: packets.

text: Uploading

text: these

text: y

text: packets

text: takes

text: y

text: rounds.

text: This

text: completes

text: the

text: ﬁrst

text: part

text: of

text: the

text: argument.

text: Next,

text: we

text: prove

text: that

text: these

text: algorithms

text: need

text: no

text: more

text: than

text: y

text: lg

text: n

text: consecutive

text: rounds

text: to

text: upload

text: y

text: packets.

text: Indeed,

text: after

text: a

text: packet

text: has

text: been

text: transmitted,

text: it

text: takes

text: time

text: at

text: most

text: the

text: height

text: of

text: a

text: conceptual

text: search

text: tree

text: to

text: identify

text: another

text: station

text: with

text: an

text: eligible

text: packet.

text: This

text: height

text: is

text: at

text: most

text: lg

text: n,

text: so

text: a

text: packet

text: is

text: heard

text: at

text: least

text: once

text: in

text: any

text: contiguous

text: segment

text: of

text: lg

text: n

text: rounds.

text: Theorem

text: The

text: packet

text: latency

text: for

text: algorithm

text: OF-SRR

text: executed

text: against

text: the

text: adversary

text: of

text: type

text: (ρ,

text: b)

text: is

text: at

text: most

text: min(b

text: lg

text: n,

text: n

text: b)

text: for

text: ρ

text: and

text: it

text: is

text: at

text: most

text: for

text: ρ

text: n

text: ρ

text: n

text: Proof:

text: A

text: packet

text: is

text: transmitted

text: successfully

text: by

text: the

text: end

text: of

text: the

text: phase

text: following

text: the

text: one

text: in

text: which

text: it

text: was

text: injected.

text: So

text: the

text: maximum

text: packet

text: latency

text: is

text: upper

text: bounded

text: by

text: twice

text: the

text: maximum

text: length

text: of

text: a

text: phase.

text: At

text: most

text: ρ

text: τ

text: b

text: packets

text: get

text: injected

text: in

text: a

text: time

text: interval

text: τ

text: of

text: length

text: τ

text: The

text: maximum

text: number

text: of

text: packets

text: in

text: the

text: system

text: is

text: upper

text: bounded

text: by

text: the

text: maximum

text: number

text: of

text: packets

text: at

text: the

text: end

text: of

text: an

text: interval

text: plus

text: the

text: number

text: of

text: packets

text: injected

text: within

text: this

text: interval.

text: Let

text: us

text: begin

text: with

text: the

text: case

text: ρ

text: We

text: ﬁrst

text: argue

text: that

text: at

text: the

text: end

text: of

text: a

text: round

text: there

text: are

text: at

text: n

text: most

text: ρ

text: lg

text: n,

text: b

text: packets

text: in

text: the

text: system.

text: Suppose

text: it

text: is

text: otherwise

text: and

text: consider

text: the

text: ﬁrst

text: round

text: t

text: with

text: the

text: number

text: of

text: packets

text: more

text: than

text: ρ

text: lg

text: n,

text: b

text: at

text: the

text: end

text: of

text: it.

text: Note

text: that

text: t

text: lg

text: n,

text: as

text: at

text: most

text: ρ

text: lg

text: n,

text: b

text: packets

text: are

text: injected

text: into

text: the

text: system

text: in

text: the

text: time

text: interval

text: lg

text: n,

text: This

text: follows

text: from

text: the

text: assumption

text: that,

text: at

text: the

text: end

text: of

text: round

text: t

text: lg

text: n,

text: there

text: were

text: at

text: most

text: ρ

text: lg

text: n,

text: b

text: packets

text: in

text: the

text: system.

text: From

text: that

text: round

text: until

text: round

text: t,

text: at

text: least

text: this

text: number

text: of

text: packets

text: have

text: been

text: successfully

text: transmitted,

text: by

text: Lemma

text: and

text: the

text: estimate

text: lg

text: n

text: ρ

text: lg

text: n,

text: b

text: b

text: lg

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: This argument relies only on Lemma 5. Next, observe that the following inequality holds: ≥ ≥ t i t x + ρt + b . i i i lg n This is because the number of all packets in the system in phase i multiplied by the maximum time lg n of a void period in phase i is an upper bound on t . There are at most ρt + b newly arrived i ≥ i ≥ packets in this phase. Combine this with the estimate ti ρt to obtain (x + b) lg n t . By 2lg n i ≤ i i an upper bound 2b on the number of packets in the system, in the case of ρ 1 , we obtain that 2lg n the following bound hold: ≤ ≤ t (x + b) lg n 3b lg n . i i Every packet arriving in phase i is transmitted by the end of phase i + 1. Hence the maximum packet latency is at most ≤ · ≤ max(t + t ) 2 3b lg n 6b lg n . i i+1 i In order to estimate packet latency in the case of ρ > 1 , observe that the following inequalities 2lg n hold: ≥ ≥ − t x + (ρt + b) t n . i i i i This is because the number of all packets that are in the system in phase i plus the maximum total number n of void rounds in phase i is an upper bound on t . There are at most ρt +b newly arrived ≥ i i packets in this phase, so xi+−n+b t . Lemma 5 for algorithm SRR implies that 2ρn−+b is an upper 1 ρ i 1 ρ bound on the number of packets in the system in a round. It follows that the following bounds hold: ≤ x + n + b t i − i 1 ρ − ≤ n(1 + ρ) + b(2 ρ) − . (1 ρ)2 A packet arriving in phase i is transmitted by the end of phase i+1, hence the maximum packet latency is upper bounded by − ≤ · n(1 + ρ) + b(2 ρ) max(t + t ) 2 − i i i+1 (1 ρ)2 ≤ 4(n + b) − , (1 ρ)2 (cid:3) which completes the proof. Algorithm Move-Big-To-Front. We conclude with packet latency of algorithm Move-Big- To-Front (MBTF), which is an adaptive algorithm for channels without collision detection. This algorithm was originally designed for channels without jamming, but using control bits in messages without packets allows to transfer the token without unnecessary delay even when a channel is 23 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: This

label: paragraph

text: argument

text: relies

text: only

text: on

text: Lemma

text: Next,

text: observe

text: that

text: the

text: following

text: inequality

text: holds:

text: t

text: i

text: t

text: x

text: ρt

text: b

text: i

text: i

text: i

text: lg

text: n

text: This

text: is

text: because

text: the

text: number

text: of

text: all

text: packets

text: in

text: the

text: system

text: in

text: phase

text: i

text: multiplied

text: by

text: the

text: maximum

text: time

text: lg

text: n

text: of

text: a

text: void

text: period

text: in

text: phase

text: i

text: is

text: an

text: upper

text: bound

text: on

text: t

text: There

text: are

text: at

text: most

text: ρt

text: b

text: newly

text: arrived

text: i

text: i

text: packets

text: in

text: this

text: phase.

text: Combine

text: this

text: with

text: the

text: estimate

text: ti

text: ρt

text: to

text: obtain

text: (x

text: b)

text: lg

text: n

text: t

text: By

text: n

text: i

text: i

text: i

text: an

text: upper

text: bound

text: on

text: the

text: number

text: of

text: packets

text: in

text: the

text: system,

text: in

text: the

text: case

text: of

text: ρ

text: we

text: obtain

text: that

text: n

text: the

text: following

text: bound

text: hold:

text: t

text: (x

text: b)

text: lg

text: n

text: lg

text: n

text: i

text: i

text: Every

text: packet

text: arriving

text: in

text: phase

text: i

text: is

text: transmitted

text: by

text: the

text: end

text: of

text: phase

text: i

text: Hence

text: the

text: maximum

text: packet

text: latency

text: is

text: at

text: most

text: max(t

text: t

text: lg

text: n

text: lg

text: n

text: i

text: i

text: In

text: order

text: to

text: estimate

text: packet

text: latency

text: in

text: the

text: case

text: of

text: ρ

text: observe

text: that

text: the

text: following

text: inequalities

text: n

text: hold:

text: t

text: x

text: (ρt

text: b)

text: t

text: n

text: i

text: i

text: i

text: i

text: This

text: is

text: because

text: the

text: number

text: of

text: all

text: packets

text: that

text: are

text: in

text: the

text: system

text: in

text: phase

text: i

text: plus

text: the

text: maximum

text: total

text: number

text: n

text: of

text: void

text: rounds

text: in

text: phase

text: i

text: is

text: an

text: upper

text: bound

text: on

text: t

text: There

text: are

text: at

text: most

text: ρt

text: +b

text: newly

text: arrived

text: i

text: i

text: packets

text: in

text: this

text: phase,

text: so

text: xi+−n+b

text: t

text: Lemma

text: for

text: algorithm

text: SRR

text: implies

text: that

text: is

text: an

text: upper

text: ρ

text: i

text: ρ

text: bound

text: on

text: the

text: number

text: of

text: packets

text: in

text: the

text: system

text: in

text: a

text: round.

text: It

text: follows

text: that

text: the

text: following

text: bounds

text: hold:

text: x

text: n

text: b

text: t

text: i

text: i

text: ρ

text: ρ)

text: ρ)

text: A

text: packet

text: arriving

text: in

text: phase

text: i

text: is

text: transmitted

text: by

text: the

text: end

text: of

text: phase

text: hence

text: the

text: maximum

text: packet

text: latency

text: is

text: upper

text: bounded

text: by

text: ρ)

text: ρ)

text: max(t

text: t

text: i

text: i

text: b)

text: which

text: completes

text: the

text: proof.

text: Algorithm

text: Move-Big-To-Front.

text: We

text: conclude

text: with

text: packet

text: latency

text: of

text: algorithm

text: Move-Big-

text: To-Front

text: (MBTF),

text: which

text: is

text: an

text: adaptive

text: algorithm

text: for

text: channels

text: without

text: collision

text: detection.

text: This

text: algorithm

text: was

text: originally

text: designed

text: for

text: channels

text: without

text: jamming,

text: but

text: using

text: control

text: bits

text: in

text: messages

text: without

text: packets

text: allows

text: to

text: transfer

text: the

text: token

text: without

text: unnecessary

text: delay

text: even

text: when

text: a

text: channel

text: is

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: [32] D. R. Kowalski. On selection problem in radio networks. In Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC), pages 158–166, 2005. [33] D. Meier, Y. A. Pignolet, S. Schmid, and R. Wattenhofer. Speed dating despite jammers. In Proceedings of the 5th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), Lecture Notes in Computer Science vol. 5516, pages 1–14, 2009. [34] P. Raghavan and E. Upfal. Stochastic contention resolution with short delays. SIAM Journal on Computing, 28(2):709–719, 1998. [35] A. W. Richa, C. Scheideler, S. Schmid, and J. Zhang. Competitive throughput in multi-hop wireless networks despite adaptive jamming. Distributed Computing, 26(3):159–171, 2013. [36] A. Ros´en and M. S. Tsirkin. On delivery times in packet networks under adversarial traﬃc. Theory of Computing Systems, 39(6):805–827, 2006. [37] C. Scheideler and B. V¨ocking. Universal continuous routing strategies. Theory of Computing Systems, 31(4):425–449, 1998. 28

label: reference

text: D.

text: R.

text: Kowalski.

text: On

text: selection

text: problem

text: in

text: radio

text: networks.

text: In

text: Proceedings

text: of

text: the

text: ACM

text: Symposium

text: on

text: Principles

text: of

text: Distributed

text: Computing

text: (PODC),

text: pages

text: D.

text: Meier,

text: Y.

text: A.

text: Pignolet,

text: S.

text: Schmid,

text: and

text: R.

text: Wattenhofer.

text: Speed

text: dating

text: despite

text: jammers.

text: In

text: Proceedings

text: of

text: the

text: IEEE

text: International

text: Conference

text: on

text: Distributed

text: Computing

text: in

text: Sensor

text: Systems

text: (DCOSS),

text: Lecture

text: Notes

text: in

text: Computer

text: Science

text: vol.

text: pages

text: P.

text: Raghavan

text: and

text: E.

text: Upfal.

text: Stochastic

text: contention

text: resolution

text: with

text: short

text: delays.

text: SIAM

text: Journal

text: on

text: Computing,

text: A.

text: W.

text: Richa,

text: C.

text: Scheideler,

text: S.

text: Schmid,

text: and

text: J.

text: Zhang.

text: Competitive

text: throughput

text: in

text: multi-hop

text: wireless

text: networks

text: despite

text: adaptive

text: jamming.

text: Distributed

text: Computing,

text: A.

text: Ros´en

text: and

text: M.

text: S.

text: Tsirkin.

text: On

text: delivery

text: times

text: in

text: packet

text: networks

text: under

text: adversarial

text: traﬃc.

text: Theory

text: of

text: Computing

text: Systems,

text: C.

text: Scheideler

text: and

text: B.

text: V¨ocking.

text: Universal

text: continuous

text: routing

text: strategies.

text: Theory

text: of

text: Computing

text: Systems,


text: simultaneous transmission. A channel is with jamming and without collision detection: a void round is perceived as silence, and the stations cannot distinguish which of the following possible causes makes the round void, that is, either no message is transmitted or there is a collision or the round is jammed. A channel is with jamming and with collision detection: a void round is either perceived as silence, which means there is no transmission, or as a collision, which means that either there are multiple simultaneous transmissions or the round is jammed. Adversarial model of packet injection. We use the general leaky-bucket adversarial model, as considered in [9, 23]. An adversary is determined by injection rate and burstiness. Let a real ≤ number ρ satisfy 0 < ρ 1, and b be a non-negative integer; the leaky-bucket adversary of type (ρ, b) may inject at most ρt+b packets into any set of stations in every contiguous segment of t > 0 rounds. An adversary is said to be of injection rate ρ when it is of type (ρ, b), for some b. Burstiness means the maximum number of packets that can be injected in one round. The adversary of type (cid:98) (cid:99) (ρ, b) has burstiness b + 1 . Knowledge. A property of a system is said to be known when it can be referred to explicitly in a code of a communication algorithm. We assume throughout that the number of stations n is − known to the stations. Each station has a unique integer name in [0, n 1], which it knows. When a station needs to be distinguished in a communication algorithm, for example to be the ﬁrst one to transmit in an execution, then it is always the station with name 0. Deﬁnition of deterministic distributed broadcast algorithms. Broadcast algorithms con- trol timings of transmissions by individual stations. All the stations start simultaneously at the same round. The local queues at stations are under the FIFO discipline, which minimizes packet latency. A packet is never dropped by a station, unless it was heard on the channel. A state of a station is determined by the private values of variables occurring in the code of the algorithm and the number of outstanding packets in its queue that still need to be transmitted. A state transition is a change of state in one round. An execution of a algorithm is a sequence of events occurring at consecutive rounds. An event in a round comprises the following actions at any station in the given order: a) a station either transmits a message or pauses, accordingly to its state, b) a station receives a feedback from the channel, in the form of either hearing a message or collision signal or silence, then c) new packets are injected into a station, if any, and ﬁnally d) a state transition occurs in a station. A state transition depends on the state at the end of the previous round, the feedback from the channel in this round, and the packets injected in this round; it occurs as follows. If packets have been injected in this round then they are enqueued into the local queue. If the station has just transmitted successfully in this round, then the transmitted packet is discarded and a new pending packet is obtained by dequeuing the local queue, unless it is empty. Finally, a message for the next round is prepared, if any will be attempted to be transmitted. 6

text: simultaneous

text: transmission.

text: A

text: channel

text: is

text: with

text: jamming

text: and

text: without

text: collision

text: detection:

text: a

text: void

text: round

text: is

text: perceived

text: as

text: silence,

text: and

text: the

text: stations

text: cannot

text: distinguish

text: which

text: of

text: the

text: following

text: possible

text: causes

text: makes

text: the

text: round

text: void,

text: that

text: is,

text: either

text: no

text: message

text: is

text: transmitted

text: or

text: there

text: is

text: a

text: collision

text: or

text: the

text: round

text: is

text: jammed.

text: A

text: channel

text: is

text: with

text: jamming

text: and

text: with

text: collision

text: detection:

text: a

text: void

text: round

text: is

text: either

text: perceived

text: as

text: silence,

text: which

text: means

text: there

text: is

text: no

text: transmission,

text: or

text: as

text: a

text: collision,

text: which

text: means

text: that

text: either

text: there

text: are

text: multiple

text: simultaneous

text: transmissions

text: or

text: the

text: round

text: is

text: jammed.

text: Adversarial

text: model

text: of

text: packet

text: injection.

text: We

text: use

text: the

text: general

text: leaky-bucket

text: adversarial

text: model,

text: as

text: considered

text: in

text: An

text: adversary

text: is

text: determined

text: by

text: injection

text: rate

text: and

text: burstiness.

text: Let

text: a

text: real

text: number

text: ρ

text: satisfy

text: ρ

text: and

text: b

text: be

text: a

text: non-negative

text: integer;

text: the

text: leaky-bucket

text: adversary

text: of

text: type

text: (ρ,

text: b)

text: may

text: inject

text: at

text: most

text: ρt+b

text: packets

text: into

text: any

text: set

text: of

text: stations

text: in

text: every

text: contiguous

text: segment

text: of

text: t

text: rounds.

text: An

text: adversary

text: is

text: said

text: to

text: be

text: of

text: injection

text: rate

text: ρ

text: when

text: it

text: is

text: of

text: type

text: (ρ,

text: b),

text: for

text: some

text: b.

text: Burstiness

text: means

text: the

text: maximum

text: number

text: of

text: packets

text: that

text: can

text: be

text: injected

text: in

text: one

text: round.

text: The

text: adversary

text: of

text: type

text: (ρ,

text: b)

text: has

text: burstiness

text: b

text: Knowledge.

text: A

text: property

text: of

text: a

text: system

text: is

text: said

text: to

text: be

text: known

text: when

text: it

text: can

text: be

text: referred

text: to

text: explicitly

text: in

text: a

text: code

text: of

text: a

text: communication

text: algorithm.

text: We

text: assume

text: throughout

text: that

text: the

text: number

text: of

text: stations

text: n

text: is

text: known

text: to

text: the

text: stations.

text: Each

text: station

text: has

text: a

text: unique

text: integer

text: name

text: in

text: n

text: which

text: it

text: knows.

text: When

text: a

text: station

text: needs

text: to

text: be

text: distinguished

text: in

text: a

text: communication

text: algorithm,

text: for

text: example

text: to

text: be

text: the

text: ﬁrst

text: one

text: to

text: transmit

text: in

text: an

text: execution,

text: then

text: it

text: is

text: always

text: the

text: station

text: with

text: name

text: Deﬁnition

text: of

text: deterministic

text: distributed

text: broadcast

text: algorithms.

text: Broadcast

text: algorithms

text: con-

text: trol

text: timings

text: of

text: transmissions

text: by

text: individual

text: stations.

text: All

text: the

text: stations

text: start

text: simultaneously

text: at

text: the

text: same

text: round.

text: The

text: local

text: queues

text: at

text: stations

text: are

text: under

text: the

text: FIFO

text: discipline,

text: which

text: minimizes

text: packet

text: latency.

text: A

text: packet

text: is

text: never

text: dropped

text: by

text: a

text: station,

text: unless

text: it

text: was

text: heard

text: on

text: the

text: channel.

text: A

text: state

text: of

text: a

text: station

text: is

text: determined

text: by

text: the

text: private

text: values

text: of

text: variables

text: occurring

text: in

text: the

text: code

text: of

text: the

text: algorithm

text: and

text: the

text: number

text: of

text: outstanding

text: packets

text: in

text: its

text: queue

text: that

text: still

text: need

text: to

text: be

text: transmitted.

text: A

text: state

text: transition

text: is

text: a

text: change

text: of

text: state

text: in

text: one

text: round.

text: An

text: execution

text: of

text: a

text: algorithm

text: is

text: a

text: sequence

text: of

text: events

text: occurring

text: at

text: consecutive

text: rounds.

text: An

text: event

text: in

text: a

text: round

text: comprises

text: the

text: following

text: actions

text: at

text: any

text: station

text: in

text: the

text: given

text: order:

text: a)

text: a

text: station

text: either

text: transmits

text: a

text: message

text: or

text: pauses,

text: accordingly

text: to

text: its

text: state,

text: b)

text: a

text: station

text: receives

text: a

text: feedback

text: from

text: the

text: channel,

text: in

text: the

text: form

text: of

text: either

text: hearing

text: a

text: message

text: or

text: collision

text: signal

text: or

text: silence,

text: then

text: c)

text: new

text: packets

text: are

text: injected

text: into

text: a

text: station,

text: if

text: any,

text: and

text: ﬁnally

text: d)

text: a

text: state

text: transition

text: occurs

text: in

text: a

text: station.

text: A

text: state

text: transition

text: depends

text: on

text: the

text: state

text: at

text: the

text: end

text: of

text: the

text: previous

text: round,

text: the

text: feedback

text: from

text: the

text: channel

text: in

text: this

text: round,

text: and

text: the

text: packets

text: injected

text: in

text: this

text: round;

text: it

text: occurs

text: as

text: follows.

text: If

text: packets

text: have

text: been

text: injected

text: in

text: this

text: round

text: then

text: they

text: are

text: enqueued

text: into

text: the

text: local

text: queue.

text: If

text: the

text: station

text: has

text: just

text: transmitted

text: successfully

text: in

text: this

text: round,

text: then

text: the

text: transmitted

text: packet

text: is

text: discarded

text: and

text: a

text: new

text: pending

text: packet

text: is

text: obtained

text: by

text: dequeuing

text: the

text: local

text: queue,

text: unless

text: it

text: is

text: empty.

text: Finally,

text: a

text: message

text: for

text: the

text: next

text: round

text: is

text: prepared,

text: if

text: any

text: will

text: be

text: attempted

text: to

text: be

text: transmitted.


text: BPS/CFT, QQ-CHARACTERS, GAUGE ORIGAMI 13 3. Partition function of spiked instantons In this section we deﬁne the statistical mechanical model. The random variables are the strings of Young diagrams and the complex Boltzmann weights are rational functions of the complex numbers (58), (61). The deﬁnition might look ﬁrst a bit artiﬁcial. Its origin is geometric. Namely, in [Ne3] the moduli space of spiked instantons × × M(k,n(cid:126)) is introduced, with n(cid:126) = (n ) ∈ . It has an action of the group H = ∈ U(n ) A A 6 A 6 A U(1)3. The ﬁxed points of the maximal torus T are in one-to-one correspondence ε H with the strings of partitions described below. The Boltzmann weight is simply λ the localization contribution to the integral of 1 over M(k,n(cid:126)), multiplied by qk. This contribution is the product of the weights of the -action on the virtual tangent space T H to , which is the diﬀerence of the kernel and the cokernel of the linearization of M(k,n(cid:126)) the equations deﬁning at the ﬁxed point. The kernel is always a complex vector M(k,n(cid:126)) space, henceforth it is naturally oriented and the product of weights is well-deﬁned. The cokernel (the obstruction space) is only a real vector space, hence the product of the weights depends on the choice of its orientation. In what follows we specify the choice of the orientation with the help of the choice of the order on and . The 4 6 resulting measure will not depend on this choice. (cid:16) (cid:17) The basic local model is a statistical ensemble. The random variables are the strings ∈ (79) λ = λ(A(cid:88),α) ∈ ∈ ΛN A 6,α [n ] A of (cf. (60)) n = #N ∈ A A 6 ∈ partitions λ(A,α) Λ. In other words, the conﬁguration space is (80) ΛN . (cid:88) (cid:88) (cid:88) Deﬁne, cf. (5): n n A A (81) N (β) = eβaA,α , K (β) = eβcA,α((cid:3)) , A A ∈ α=1 α=1 (cid:3) λ(A,α) with − − (82) c ((cid:3)) = a + ε (i 1) + ε (j 1), for (cid:3) = (i,j) A,α A,α a b and (cf. (74)) ∗ ∗ − ∗ (83) T = N K + q N K P K K A A A A (cid:88)A A A A A Let [nA] | | (84) k = K (0) = λ(A,α) A A α=1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: BPS/CFT,

text: QQ-CHARACTERS,

text: GAUGE

text: ORIGAMI

label: section

text: Partition

font: OBRZTK+Kp-Medium

text: function

text: of

text: spiked

text: instantons

text: In

text: this

text: section

text: we

text: deﬁne

text: the

text: statistical

text: mechanical

text: model.

text: The

text: random

text: variables

text: are

text: the

text: strings

text: of

text: Young

text: diagrams

text: and

text: the

text: complex

text: Boltzmann

text: weights

text: are

text: rational

text: functions

text: of

text: the

text: complex

text: numbers

text: The

text: deﬁnition

text: might

text: look

text: ﬁrst

text: a

text: bit

text: artiﬁcial.

text: Its

text: origin

text: is

text: geometric.

text: Namely,

text: in

text: the

text: moduli

text: space

text: of

text: spiked

text: instantons

font: VHIEBS+Kp--M-Sy-Regular

font: SIEOTS+Kp--M-Italic

text: is

text: introduced,

text: with

font: JSVGPJ+Kp-Regular

text: (n

text: It

text: has

text: an

text: action

text: of

text: the

text: group

text: H

font: PGBFMU+Sf-Kp-Regular

text: U(n

text: A

text: A

text: A

text: A

text: The

text: ﬁxed

text: points

text: of

text: the

text: maximal

text: torus

text: T

text: are

text: in

text: one-to-one

text: correspondence

text: ε

text: H

text: with

text: the

text: strings

text: of

text: partitions

text: described

text: below.

text: The

text: Boltzmann

text: weight

text: is

text: simply

text: λ

text: the

text: localization

text: contribution

text: to

text: the

text: integral

text: of

text: over

text: multiplied

text: by

text: qk.

text: This

text: contribution

text: is

text: the

text: product

text: of

text: the

text: weights

text: of

text: the

text: -action

text: on

text: the

text: virtual

text: tangent

text: space

text: T

text: H

text: to

text: which

text: is

text: the

text: diﬀerence

text: of

text: the

text: kernel

text: and

text: the

text: cokernel

text: of

text: the

text: linearization

text: of

text: the

text: equations

text: deﬁning

text: at

text: the

text: ﬁxed

text: point.

text: The

text: kernel

text: is

text: always

text: a

text: complex

text: vector

text: space,

text: henceforth

text: it

text: is

text: naturally

text: oriented

text: and

text: the

text: product

text: of

text: weights

text: is

text: well-deﬁned.

text: The

text: cokernel

text: (the

text: obstruction

text: space)

text: is

text: only

text: a

text: real

text: vector

text: space,

text: hence

text: the

text: product

text: of

text: the

text: weights

text: depends

text: on

text: the

text: choice

text: of

text: its

text: orientation.

text: In

text: what

text: follows

text: we

text: specify

text: the

text: choice

text: of

text: the

text: orientation

text: with

text: the

text: help

text: of

text: the

text: choice

text: of

text: the

text: order

text: on

text: and

text: The

text: resulting

text: measure

text: will

text: not

text: depend

text: on

text: this

text: choice.

text: The

text: basic

text: local

text: model

text: is

text: a

text: statistical

text: ensemble.

text: The

text: random

text: variables

text: are

text: the

text: strings

text: λ

text: ΛN

text: A

text: [n

text: A

text: of

text: (cf.

text: n

text: #N

text: A

text: A

text: partitions

text: λ(A,α)

text: Λ.

text: In

text: other

text: words,

text: the

text: conﬁguration

text: space

text: is

text: ΛN

text: Deﬁne,

text: cf.

text: n

text: n

text: A

text: A

text: N

text: (β)

text: eβaA,α

text: K

text: (β)

text: A

text: A

text: λ(A,α)

text: with

text: c

text: a

text: ε

text: (i

text: ε

text: (j

text: for

text: (i,j)

text: A,α

text: A,α

text: a

text: b

text: and

text: (cf.

text: T

text: N

text: K

text: q

text: N

text: K

text: P

text: K

text: K

text: A

text: A

text: A

text: A

text: A

text: A

text: A

text: A

text: Let

text: [nA]

text: k

text: K

text: λ(A,α)

text: A

text: A

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: BPS/CFT, QQ-CHARACTERS, GAUGE ORIGAMI 15 (cid:88) (cid:88) { } where we used (86), (87), (67), and qa¯qb¯qA = 1 fo∞r A¯ = a¯,b¯ . Deﬁne, Z Z (93) inst = Z = qk inst ∈ λ k λ ΛN k=0 Z The partition function inst is the T -equivariant integral of 1 over the virtual fun- H damental cycle of the moduli space of spiked instantons [Ne3]. The latter is the space of solutions to certain quadratic matrix equations, generalizing the ADHM equations × † ∈ [ADHM], on four complex matrices , their Hermitian conjugates , , and k k B × × ∈ B a 4 a a twelve rectangular matrices , of sizes and , , and their Hermitian I ,J n k k n A 6 A A A A conjugates. The deﬁnition (90) stems from the equivariant localization. The strings of partitions are the -ﬁxed points. The matrices of the construction [Ne3] λ T (B ,I ,J ) H a A A obey, for such a ﬁxed point: ∈ ∈ (94) [B ,B ] = 0, a,b 4, J = 0, A 6 a b A the vectors | (cid:105) − − (95) i,j;α;ab = Bi 1Bj 1I (N ) a b ab ab,α ∈ ≤ ≤ with α [n ], 1 j λ(ab,α) forming the basis of the vector space K, N being the ab ab,α eigenspace of action on the framing space (see [Ne3] for the notations and more T N explanations). ab (cid:88) (cid:88)(cid:16) ab (cid:17) The equivariant weights of the matrices contribute ∗ ∗ ∗ (96) T = q KK + K N + q KN + ∈ a (cid:88)∈ A A A a 4 A 6 with (97) K = K ∈ A A 6 while the equivariant weights of the equations they obey, and the symmetries one  (cid:88)  (cid:88) (cid:88) divides by, contribute (withthe minus sign)         ∗ ∗ (98) − T = 1 + q q KK + q K N ∈ c 4 ∈ ∈ a¯ A c 3 A 6 a¯ A¯ Moreover, the part is deﬁned canonically by using the complex structure of the T + space of matrices . The − part is deﬁned non-canonically, as the expression (Ba,IA,JA) T ∗ (98) does not respect the symmetry between ’s. The real (i.e. such that ) ∗ (cid:112) qa χ = χ character T− + T− is deﬁned canonically. This subtlety has to do with the real, as opposed to complex, nature of the equations deﬁning the spiked instantons [Ne3]. So, ∗ (cid:15)[T−] may have a sign ambiguity, as (cid:15)[T− + T−]. Also, (cid:15)[T−] and (cid:15)[T ] separately + may vanish, as some of the weights in (96) and (98) may vanish. It is easy to show − − that formally − . One simply uses (75) several times. The details (cid:15)[T T ] = (cid:15)[ T ] + λ of the choice of the sign will be clariﬁed elsewhere (it uses the residue deﬁnition of ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: BPS/CFT,

text: QQ-CHARACTERS,

text: GAUGE

text: ORIGAMI

text: where

text: we

text: used

text: and

text: qa¯qb¯qA

text: fo∞r

text: A¯

text: a¯,b¯

text: Deﬁne,

text: Z

text: Z

text: inst

text: Z

text: qk

font: RNVALM+Kp--M-Regular

text: inst

text: λ

text: k

text: λ

text: ΛN

font: VHZIAE+Kp-Expert-Regular

text: Z

text: The

text: partition

text: function

text: inst

text: is

text: the

text: T

text: -equivariant

text: integral

text: of

text: over

text: the

text: virtual

text: fun-

text: H

text: damental

text: cycle

text: of

text: the

text: moduli

text: space

text: of

text: spiked

text: instantons

text: The

text: latter

text: is

text: the

text: space

text: of

text: solutions

text: to

text: certain

text: quadratic

text: matrix

text: equations,

text: generalizing

text: the

text: ADHM

text: equations

text: [ADHM],

text: on

text: four

text: complex

text: matrices

text: their

text: Hermitian

text: conjugates

text: and

text: k

text: k

text: B

text: B

text: a

text: a

text: a

text: twelve

text: rectangular

text: matrices

text: of

text: sizes

text: and

text: and

text: their

text: Hermitian

text: I

text: ,J

text: n

text: k

text: k

text: n

text: A

text: A

text: A

text: A

text: A

text: conjugates.

text: The

text: deﬁnition

text: stems

text: from

text: the

text: equivariant

text: localization.

text: The

text: strings

text: of

text: partitions

text: are

text: the

text: -ﬁxed

text: points.

text: The

text: matrices

text: of

text: the

text: construction

text: λ

text: T

text: (B

text: ,I

text: ,J

text: H

text: a

text: A

text: A

text: obey,

text: for

text: such

text: a

text: ﬁxed

text: point:

text: [B

text: ,B

text: a,b

text: J

text: A

text: a

text: b

text: A

text: the

text: vectors

text: i,j;α;ab

text: Bi

text: (N

text: a

text: b

text: ab

text: ab,α

text: with

text: α

text: [n

text: j

text: λ(ab,α)

text: forming

text: the

text: basis

text: of

text: the

text: vector

text: space

text: K,

text: N

text: being

text: the

text: ab

text: ab,α

text: eigenspace

text: of

text: action

text: on

text: the

text: framing

text: space

text: (see

text: for

text: the

text: notations

text: and

text: more

text: T

text: N

text: explanations).

text: ab

text: ab

text: The

text: equivariant

text: weights

text: of

text: the

text: matrices

text: contribute

text: T

text: q

text: KK

text: K

text: N

text: q

text: KN

text: a

text: A

text: A

text: A

text: a

text: A

text: with

text: K

text: K

text: A

text: A

text: while

text: the

text: equivariant

text: weights

text: of

text: the

text: equations

text: they

text: obey,

text: and

text: the

text: symmetries

text: one

text: divides

text: by,

text: contribute

text: (withthe

text: minus

text: sign)

text: T

text: q

text: q

text: KK

text: q

text: K

text: N

text: c

text: a¯

text: A

text: c

text: A

text: a¯

text: A¯

text: Moreover,

text: the

text: part

text: is

text: deﬁned

text: canonically

text: by

text: using

text: the

text: complex

text: structure

text: of

text: the

text: T

text: space

text: of

text: matrices

text: The

text: part

text: is

text: deﬁned

text: non-canonically,

text: as

text: the

text: expression

text: (Ba,IA,JA)

text: T

text: does

text: not

text: respect

text: the

text: symmetry

text: between

text: ’s.

text: The

text: real

text: (i.e.

text: such

text: that

text: qa

text: χ

text: χ

text: character

text: T−

text: T−

text: is

text: deﬁned

text: canonically.

text: This

text: subtlety

text: has

text: to

text: do

text: with

text: the

text: real,

text: as

text: opposed

text: to

text: complex,

text: nature

text: of

text: the

text: equations

text: deﬁning

text: the

text: spiked

text: instantons

text: So,

text: may

text: have

text: a

text: sign

text: ambiguity,

text: as

text: T−].

text: Also,

text: and

text: separately

text: may

text: vanish,

text: as

text: some

text: of

text: the

text: weights

text: in

text: and

text: may

text: vanish.

text: It

text: is

text: easy

text: to

text: show

text: that

text: formally

text: One

text: simply

text: uses

text: several

text: times.

text: The

text: details

text: T

text: T

text: λ

text: of

text: the

text: choice

text: of

text: the

text: sign

text: will

text: be

text: clariﬁed

text: elsewhere

text: (it

text: uses

text: the

text: residue

text: deﬁnition

text: of

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: BPS/CFT, QQ-CHARACTERS, GAUGE ORIGAMI 19 (cid:112) from the domain , giving Re(x),Re(y) > 0 (cid:16) (cid:17) 2π/y (118) Γ (x;y) = , 1 y yx Γ x • (cid:89)(cid:89) (cid:16)y (cid:17) nA nA¯ − (119) Zcpreorsts,A(aA,aA¯,ε¯) = aA,α aA¯,β + εA¯ α=1 β=1 In [AGT] another norm(cid:89)alizati(cid:89)on for th(cid:16)e perturbative prefac(cid:17)tor is used: the second line in (112) would read, in our notation, as − − Γ 1 a a + ε ; ε ,ε ≤ ≤ ∈ 2 A,α A,β a¯ a b 1 α<β nA a¯ A¯ ∈ This normalization makes explicit the symmetry between a¯ A¯, however the gauge invariance, i.e. the Weyl symmetry of acting on is partly broken. U(nAZ) aA,α Unlike the instanton partition function inst the perturbative factor does depend on the choice of the order on which is used in the deﬁnition of . This 4 m = ε A ϕ(A) dependence will be analyzed elsewhere. ⊂ When the equivariant parameters a,ε¯ are rationally dependent, the torus T˜ T H H they generate is strictly smaller than . Accordingly, the ﬁxed points on the moduli T H space of spiked instantons need not be isolated, and the formula (103) is used. It can be further localized to the set of torus-ﬁxed points on , which are relatively M (n ) k A well-understood in the case [I, IY, L]. We shall encAounter these complications n = 1 A when(cid:48) ×dea(cid:48)(cid:48)ling with gauge theories on C2/Γ spaces, (cid:48)or o(cid:48)(cid:48)n⊂the complex surfaces in the C4/Γ Γ spaces, with ﬁnite SU(2) subgroups Γ, Γ , Γ SU(2) of D or E type. Here is the main fact about the partition fu(cid:88)nction of spiked instantons: the com- Z pactness theorem proven in [Ne3] implies deﬁned by (a,ε¯) spiked Z (120) (a,ε¯) = W spiked λ λ (cid:88) has no singularities in the variables: n 1 A (121) x = a A A,α n A α=1 with ﬁxed − (122) a˜ = a x A,α A,α A ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: BPS/CFT,

text: QQ-CHARACTERS,

text: GAUGE

text: ORIGAMI

font: GEZZNO+Kp--M-Ex-Regular

text: from

text: the

text: domain

text: giving

text: Re(x),Re(y)

text: Γ

text: (x;y)

text: y

text: yx

text: Γ

text: x

text: nA¯

text: Zcpreorsts,A(aA,aA¯,ε¯)

text: aA,α

text: aA¯,β

text: εA¯

text: In

text: [AGT]

text: another

text: for

text: perturbative

text: is

text: used:

text: the

text: second

text: line

text: in

text: would

text: read,

text: in

text: our

text: notation,

text: as

text: Γ

text: a

text: a

text: ε

text: ε

text: ,ε

text: A,α

text: A,β

text: a¯

text: a

text: b

text: α<β

text: a¯

text: A¯

text: This

text: normalization

text: makes

text: explicit

text: the

text: symmetry

text: between

text: a¯

text: A¯,

text: however

text: the

text: gauge

text: invariance,

text: i.e.

text: the

text: Weyl

text: symmetry

text: of

text: acting

text: on

text: is

text: partly

text: broken.

text: U(nAZ)

text: aA,α

text: Unlike

text: the

text: instanton

text: partition

text: function

text: inst

text: the

text: perturbative

text: factor

text: does

text: depend

text: on

text: the

text: choice

text: of

text: the

text: order

text: on

text: which

text: is

text: used

text: in

text: the

text: deﬁnition

text: of

text: This

text: m

text: ε

text: A

text: ϕ(A)

text: dependence

text: will

text: be

text: analyzed

text: elsewhere.

text: When

text: the

text: equivariant

text: parameters

text: a,ε¯

text: are

text: rationally

text: dependent,

text: the

text: torus

text: T˜

text: T

text: H

text: H

text: they

text: generate

text: is

text: strictly

text: smaller

text: than

text: Accordingly,

text: the

text: ﬁxed

text: points

text: on

text: the

text: moduli

text: T

text: H

text: space

text: of

text: spiked

text: instantons

text: need

text: not

text: be

text: isolated,

text: and

text: the

text: formula

text: is

text: used.

text: It

text: can

text: be

text: further

text: localized

text: to

text: the

text: set

text: of

text: torus-ﬁxed

text: points

text: on

text: which

text: are

text: relatively

text: M

text: (n

text: k

text: A

text: well-understood

text: in

text: the

text: case

text: [I,

text: IY,

text: L].

text: We

text: shall

text: encAounter

text: these

text: complications

text: n

text: A

text: with

text: gauge

text: theories

text: on

text: spaces,

text: complex

text: surfaces

text: in

text: the

text: Γ

text: spaces,

text: with

text: ﬁnite

text: subgroups

text: Γ,

text: Γ

text: Γ

text: of

text: D

text: or

text: E

text: type.

text: Here

text: is

text: the

text: main

text: fact

text: about

text: the

text: partition

text: of

text: spiked

text: instantons:

text: the

text: com-

text: Z

text: pactness

text: theorem

text: proven

text: in

text: implies

text: deﬁned

text: by

text: (a,ε¯)

text: spiked

text: Z

text: (a,ε¯)

text: W

text: spiked

text: λ

text: λ

text: has

text: no

text: singularities

text: in

text: the

text: variables:

text: n

text: A

text: x

text: a

text: A

text: A,α

text: n

text: A

text: with

text: ﬁxed

text: a˜

text: a

text: x

text: A,α

text: A,α

text: A

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: BPS/CFT, QQ-CHARACTERS, GAUGE ORIGAMI 23 (cid:48) ∈ (cid:48)(cid:48) ∈ ∈ ∨ with Γ (cid:48), Γ (cid:48)(cid:48), Γ . The irreducible representations of Γ are the h h ρ γ γ ab tensor products R L ⊗ (cid:48) ⊗ (cid:48)(cid:48) (145) = R (cid:48) R (cid:48)(cid:48) $ ν i i (cid:48) (cid:48)(cid:48) ∈ ∨ (cid:48) ∈ (cid:48)(cid:48) ∈ (cid:48) (cid:48)(cid:48) labelled by $ = (ν,i ,i ), where $ Γ , i Vert (cid:48), i Vert (cid:48)(cid:48), and R , R ab γ γ are the irreps of Γ (cid:48), Γ (cid:48)(cid:48), respectively. Again, with the choice (144) of Γ the γ γ only non-trivial Chan-Paton spaces are and . The choice of the Chan- N N 12 34 Paton representation in this case amounts to the choice of multiplicity ρ CP spaces , i.e. the dimension vectors N ,N 12,$ 34,$ (146) (cid:17) n = dimN , w = dimN , $ 12,$ $ 34,$ (cid:48) (cid:48)(cid:48) ∈ ∨ for Γ . The centralizer $ = (ν,i ,i ) × × (147) HΓ = U(1) (cid:48) (cid:48)(cid:48) U(n ) U(w ) γ ,γ $ $ ∈ ∨ Γ  $  ⊂ where U(1) (cid:48) (cid:48)(cid:48) U(1)3 consists of diagonal matrices of the form: γ ,γ  √ ε  − · (148) e 1ϑ 12 −√− · ∈ SU(4), e 1ϑ 1 2 × × Deﬁne (cf. (60), (133), (142)), for Γ = Γ Γ (cid:48) Γ (cid:48)(cid:48): ab γ γ (cid:70) (cid:70) (cid:116) − (149) NΓ = N+Γ NΓ (cid:48) − (cid:48)(cid:48) − with N+ = Ni ,+, N = Ni , , and Γ (cid:48)∈ (cid:48) Γ Γ (cid:48)(cid:48)∈ (cid:48)(cid:48) Γ i Ver(cid:71)t i Ver(cid:110)t (cid:111) γ γ (150) (cid:48) (cid:48) (cid:48)(cid:48) | ∈ ∨ (cid:48)(cid:48) ∈ ∈ NiΓ,+ = (cid:71) [nν,i(cid:48),i(cid:48)(cid:48)] = (ν(cid:110) ,i ,i ,α) ν Γab, i Vertγ(cid:48)(cid:48), α [nν,i(cid:48),i(cid:48)(cid:48)] (cid:111), ν∈Γ∨ ,i(cid:48)(cid:48)∈Vert (cid:48)(cid:48) (cid:48)(cid:48) − ab γ (cid:48) (cid:48)(cid:48) | ∈ ∨ (cid:48) ∈ ∈ NiΓ , = [wν,i(cid:48),i(cid:48)(cid:48)] = (ν,i ,i ,β) ν Γab, i Vertγ(cid:48), β [wν,i(cid:48),i(cid:48)(cid:48)] ν∈Γ∨ ,i(cid:48)∈Vert (cid:48) ab γ N K In what follows the expressions (cid:88), etc. are promoted to , etc. which are ⊗ N K A A A A valued in Γ , i.e. they are the formal linear combinations: K[T ] K[ ] HΓ ⊗ R (151) n L w,$ w $ ∈ ∨ ∈ ∨ Γ w THΓ , $ R where are the characters of , and are the irreducible representations of Γ. Lw THΓ $ T ∈ ⊗ Likewise, the “tangent space” character is promoted to Γ . T K[T ] K[ ] A A HΓ ##LTLine## ##LTLine##

text: BPS/CFT,

text: QQ-CHARACTERS,

text: GAUGE

text: ORIGAMI

label: list

text: with

text: Γ

text: Γ

text: Γ

text: The

text: irreducible

text: representations

text: of

text: Γ

text: are

text: the

text: h

text: h

text: ρ

text: γ

text: γ

text: ab

text: tensor

text: products

text: R

text: L

text: R

text: R

text: ν

text: i

text: i

text: labelled

text: by

text: (ν,i

text: ,i

text: where

text: Γ

text: i

text: Vert

text: i

text: Vert

text: and

text: R

text: R

text: ab

text: γ

text: γ

text: are

text: the

text: irreps

text: of

text: Γ

text: Γ

text: respectively.

text: Again,

text: with

text: the

text: choice

text: of

text: Γ

text: the

text: γ

text: γ

text: only

text: non-trivial

text: Chan-Paton

text: spaces

text: are

text: and

text: The

text: choice

text: of

text: the

text: Chan-

text: N

text: N

text: Paton

text: representation

text: in

text: this

text: case

text: amounts

text: to

text: the

text: choice

text: of

text: multiplicity

text: ρ

text: CP

text: spaces

text: i.e.

text: the

text: dimension

text: vectors

text: N

text: ,N

text: n

text: dimN

text: w

text: dimN

text: for

text: Γ

text: The

text: centralizer

text: (ν,i

text: ,i

text: HΓ

text: U(n

text: U(w

text: γ

text: ,γ

text: Γ

text: where

text: consists

text: of

text: diagonal

text: matrices

text: of

text: the

text: form:

text: γ

text: ,γ

text: ε

text: e

text: 1ϑ

text: e

text: 1ϑ

text: Deﬁne

text: (cf.

text: for

text: Γ

text: Γ

text: Γ

text: Γ

text: ab

text: γ

text: γ

text: NΓ

text: N+Γ

text: NΓ

text: with

text: N+

text: Ni

text: N

text: Ni

text: and

text: Γ

text: Γ

text: Γ

text: Γ

text: i

text: i

text: γ

text: γ

text: NiΓ,+

text: ,i

text: ,i

text: ,α)

text: ν

text: Γab,

text: i

text: α

text: ν∈Γ∨

text: ab

text: γ

text: NiΓ

text: (ν,i

text: ,i

text: ,β)

text: ν

text: Γab,

text: i

text: β

text: ν∈Γ∨

text: ab

text: γ

text: N

text: K

text: In

text: what

text: follows

text: the

text: expressions

text: etc.

text: are

text: promoted

text: to

text: etc.

text: which

text: are

text: N

text: K

text: A

text: A

text: A

text: A

text: valued

text: in

text: Γ

text: i.e.

text: they

text: are

text: the

text: formal

text: linear

text: combinations:

text: K[T

text: K[

text: HΓ

text: R

text: n

text: L

text: w,$

text: w

text: Γ

text: w

text: THΓ

text: R

text: where

text: are

text: the

text: characters

text: of

text: and

text: are

text: the

text: irreducible

text: representations

text: of

text: Γ.

text: Lw

text: THΓ

text: T

text: Likewise,

text: the

text: “tangent

text: space”

text: character

text: is

text: promoted

text: to

text: Γ

text: T

text: K[T

text: K[

text: A

text: A

text: HΓ

text: ##LTLine##

text: ##LTLine##


text: BPS/CFT, QQ-CHARACTERS, GAUGE ORIGAMI 27 (cid:32) (cid:33) (cid:89) where the projected double gamma (172) Γ2,Γab νx ;; ρy(cid:48)(cid:48),,yρ(cid:48)(cid:48)(cid:48)(cid:48) ∼ ≥ (x + y(cid:48)(i − 1) + y(cid:48)(cid:48)(j − 1))δΓ∨ab(ν+ρ(cid:48)(i−1)+ρ(cid:48)(cid:48)(j−1)) i,j 1 can be easily expressed in terms of the ordinary Γ ’s, • 2 (cid:32) (cid:33) (cid:89) (cid:89) (cid:89) (173) − Zfpoelrdt,a|bc,Γab(aab,aac,ρ,ε¯) =(cid:32) ν,ν(cid:48)∈Γ∨ab α∈(cid:33)[nab,(cid:89)ν]β∈[nac,ν(cid:48)] Γ1,Γab aab,νν,α− νa(cid:48)a+c,νρ(cid:48),aβ ++ρεac + εc ;; ρεaa where ∞ (174) Γ1,Γab νx ;; ρy ∼ (x + y(i − 1))δΓ∨ab(ν+ρ(i−1)) i=1 can be easily expressed in terms of the ordinary gamma-functions, • (cid:89) (cid:89) (cid:89) (cid:16) (cid:17) (175) − ∨ − (cid:48)− Zcpreorsts,A,Γab(aA,aA¯,ρ,ε¯) = ν,ν(cid:48)∈Γ∨ab α∈[nA,ν]β∈[nB,ν(cid:48)] aA,ν,α aA¯,ν(cid:48),β + εA¯ δΓab(ν ν ρA) × Fix Γ , of or type. Let Γ Γ Γ . The irreps of Γ are labelled by γ D E = ab ∈ ∨ ∈ ab γ the pairs $ = (ν,i), ν Γab,i Vertγ. Fix the discrete data: t→he dimension vectors n = (n$)$∈Γ∨, w = (w$)$∈Γ∨, and the two characters ρl,ρr : Γab U(1). The orbifold gauge origami in this case depends on the following continuous data: (1) Two complex numbers , and . ε ,ε ε = ε + ε 1 2 1 2 ∈ ∈ − (2) Two sets of Coulomb parameters: a = (a ) CN+Γ, b = (b ) CNΓ ∈ ∈ ν,i,α∈ ∈ ν,i,β (176) a C, α [n ], b C, β [w ] ν,i,α | ν| ,i ν,i,β ν,i (3) The string q = (q ) ∈Γ∨ of Γ fugacities: $ $ ∈ | | (177) q C, q < 1 $ $ → The geometric action Γ deﬁnes the following three representations: SU(4) ≡ L ≡ L L ⊗ (178) C1 , C1 − , C2 = − 2 , 1 ρ +ρ 2 ρ ρ 34 ρ l r l r l which obey ⊗ ⊗ R (179) C1 C1 Λ2C2 = , P1 P2 P 34 0 the trivial representation. Write , with: = 4 12 34 P − − L P − − − L (180) 12 = 1 q1C11 q2C12 + eβε 2ρ , 34 = 1 q 12 C234 + q 1 −2ρ . l l ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: BPS/CFT,

text: QQ-CHARACTERS,

text: GAUGE

text: ORIGAMI

text: where

text: the

text: projected

text: double

text: gamma

text: νx

text: (x

text: i,j

text: can

text: be

text: easily

text: expressed

text: in

text: terms

text: of

text: the

text: ordinary

text: Γ

text: ’s,

text: Zfpoelrdt,a|bc,Γab(aab,aac,ρ,ε¯)

text: aab,νν,α−

text: ++ρεac

text: εc

text: ρεaa

text: where

text: νx

text: ρy

text: (x

text: y(i

text: can

text: be

text: easily

text: expressed

text: in

text: terms

text: of

text: the

text: ordinary

text: gamma-functions,

text: Zcpreorsts,A,Γab(aA,aA¯,ρ,ε¯)

text: aA,ν,α

text: εA¯

text: δΓab(ν

text: ν

text: ρA)

text: Fix

text: Γ

text: of

text: or

text: type.

text: Let

text: Γ

text: Γ

text: Γ

text: The

text: irreps

text: of

text: Γ

text: are

text: labelled

text: by

text: γ

text: D

text: E

text: ab

text: ab

text: γ

text: the

text: pairs

text: (ν,i),

text: ν

text: Γab,i

text: Vertγ.

text: Fix

text: the

text: discrete

text: data:

text: t→he

text: dimension

text: vectors

text: n

text: (n$)$∈Γ∨,

text: w

text: (w$)$∈Γ∨,

text: and

text: the

text: two

text: characters

text: ρl,ρr

text: Γab

text: The

text: orbifold

text: gauge

text: origami

text: in

text: this

text: case

text: depends

text: on

text: the

text: following

text: continuous

text: data:

text: Two

text: complex

text: numbers

text: and

text: ε

text: ,ε

text: ε

text: ε

text: ε

text: Two

text: sets

text: of

text: Coulomb

text: parameters:

text: a

text: (a

text: CN+Γ,

text: b

text: (b

text: CNΓ

text: ν,i,α∈

text: ν,i,β

text: a

text: C,

text: α

text: [n

text: b

text: C,

text: β

text: [w

text: ν,i,α

text: ν|

text: ,i

text: ν,i,β

text: ν,i

text: The

text: string

text: q

text: (q

text: ∈Γ∨

text: of

text: Γ

text: fugacities:

text: q

text: C,

text: q

text: The

text: geometric

text: action

text: Γ

text: deﬁnes

text: the

text: following

text: three

text: representations:

text: L

text: L

text: L

text: ρ

text: +ρ

text: ρ

text: ρ

text: ρ

text: l

text: r

text: l

text: r

text: l

text: which

text: obey

text: R

text: P

text: the

text: trivial

text: representation.

text: Write

text: with:

text: P

text: L

text: P

text: L

text: eβε

text: 2ρ

text: q

text: q

text: −2ρ

text: l

text: l

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 28 NIKITA NEKRASOV (cid:88) (cid:88) (cid:88) (cid:88) Finally, deﬁne N R W R (181) = eβa$,α , = eβb$,α˜ $ $ ∈ ∨ ∈ ∈ ∨ ∈ $ Γ α [n$] $ Γ α˜ [w$] • The random variables × in the Γ-orbifold gauge origami model were deﬁned in λ (cid:17)ab ale(cid:17) (cid:17) (153). The statistical weight of × is an integral over the product of Nakajima- λab ale (cid:0) (cid:1) Young varieties: X ∈ (182) λab×ale = ∈ ∨ ∈ ∈ Yiγ µν,i,α˜ , µν,i,α˜ Λiγ (cid:88)ν Γab i Vertγ (cid:88)α˜ [wν,i] Deﬁne K − − L ⊗ (183) = eβaν,i,αq1i 1q2j 1 ν+ρ (i+j−2)+ρ (i−j) Ri , ∈ ∨ ∈ ∈ ∈ l r ν Γab,i Vertγ,α [nν,i](i,j) λ(i,(cid:36),α) (cid:88) T N K∗ N ∗K L − P KK∗ T R (184) = + q = 12 2ρ 12 12,$ $ l ∈ ∨ Γ $ (cid:88) (cid:88) (cid:16) so that, in particular T N K∗ N ∗ K − K K∗ (185) = (cid:48) (cid:48) + q (cid:48) (cid:48) (cid:48) (cid:48) (cid:17) 12,ν,0 ∈ (cid:48)∈ ∨ ν+ν ,i ν ,i 2ρl+ν ,i ν+ν ,i ν+ν ,i ν ,i i Vertγ ν KΓab K∗ K K∗ K K∗ +q (cid:48) (cid:48) + q (cid:48) − (cid:48) + q (cid:48) (cid:48) . 1 ν+ν ,i ρ +ρ +ν ,i 2 ν+ν ,i ρ ρ +ν ,i ν+ν ,i 2ρ +ν ,i (cid:88) (cid:88) (cid:88) (cid:88)l r (cid:16) l r (cid:17) l Deﬁne: V − L ⊗ (186) = ∈ ∈ ∨ ∈ ≥ eβbν,i,α˜q n2 Ch V˜ii,n(µν(cid:48),i(cid:48),α˜) ν−nρl R˜i i,˜i Vertγ ν Γab α˜ [wν,i] n 0 (cid:88) T WV∗ − W∗VL − P VV∗ T R (187) = + q 1 − = 34 2ρ 34 34,$ $ l ∈ ∨ Γ $ N W K V T T ⊗ We view as the Γ -valued linear combinations of Chern , , , , , K[T ] K( ) 12 34 X HΓ P − P − characters of vector bundles over λ × , as well as 1 = 1 q1C11, 2 = 1 q2C12. The measure (89) dressed with a paabratleial perturbative contribution, the orbifold ver-   (cid:90) sion of (175), is generalized t(cid:89)o  (cid:104) (cid:105)           Z − R T R T (188) Γpe,crrtosszλab×ale = ∈ ∨ qk$ X (cid:15) [ 0] λab×ale + [L0 0] λab×ale , $ Γ λab×ale ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: NIKITA

text: NEKRASOV

text: Finally,

text: deﬁne

text: N

text: R

text: W

text: R

text: eβa$,α

text: eβb$,α˜

text: Γ

text: α

text: [n$]

text: Γ

text: α˜

text: [w$]

text: The

text: random

text: variables

text: in

text: the

text: Γ-orbifold

text: gauge

text: origami

text: model

text: were

text: deﬁned

text: in

text: λ

text: The

text: statistical

text: weight

text: of

text: is

text: an

text: integral

text: over

text: the

text: product

text: of

text: Nakajima-

text: λab

text: ale

text: Young

text: varieties:

text: X

text: λab×ale

text: Yiγ

text: µν,i,α˜

text: µν,i,α˜

text: Λiγ

text: Γab

text: i

text: Vertγ

text: [wν,i]

text: Deﬁne

text: K

text: L

text: ν+ρ

text: (i−j)

text: Ri

text: l

text: r

text: ν

text: Γab,i

text: Vertγ,α

text: [nν,i](i,j)

text: T

text: N

text: K∗

text: N

text: ∗K

text: L

text: P

text: KK∗

text: T

text: R

text: q

text: 2ρ

text: l

text: Γ

text: so

text: that,

text: in

text: particular

text: T

text: N

text: K∗

text: N

text: K

text: K

text: K∗

text: q

text: ν+ν

text: ,i

text: ν

text: ,i

text: ,i

text: ν+ν

text: ,i

text: ν+ν

text: ,i

text: ν

text: ,i

text: i

text: Vertγ

text: ν

text: KΓab

text: K∗

text: K

text: K∗

text: K

text: K∗

text: +q

text: q

text: q

text: ν+ν

text: ,i

text: ρ

text: +ρ

text: +ν

text: ,i

text: ν+ν

text: ,i

text: ρ

text: ρ

text: +ν

text: ,i

text: ν+ν

text: ,i

text: 2ρ

text: +ν

text: ,i

text: r

text: l

text: r

text: l

text: Deﬁne:

text: V

text: L

text: eβbν,i,α˜q

text: Ch

text: ν−nρl

text: R˜i

text: i,˜i

text: Vertγ

text: ν

text: Γab

text: α˜

text: [wν,i]

text: n

text: T

text: WV∗

text: W∗VL

text: P

text: VV∗

text: T

text: R

text: q

text: 2ρ

text: l

text: Γ

text: N

text: W

text: K

text: V

text: T

text: T

text: We

text: view

text: as

text: the

text: Γ

text: -valued

text: linear

text: combinations

text: of

text: Chern

text: K[T

text: K(

text: X

text: HΓ

text: P

text: P

text: characters

text: of

text: vector

text: bundles

text: over

text: λ

text: as

text: well

text: as

text: The

text: measure

text: dressed

text: with

text: a

text: paabratleial

text: perturbative

text: contribution,

text: the

text: orbifold

text: ver-

text: sion

text: of

text: is

text: generalized

text: Z

text: R

text: T

text: R

text: T

text: Γpe,crrtosszλab×ale

text: qk$

text: X

text: λab×ale

text: λab×ale

text: Γ

text: λab×ale

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: BPS/CFT, QQ-CHARACTERS, GAUGE ORIGAMI 9 (cid:16) (cid:17) ∈ where vi,α ZV≥ertγ for each (i,α), i.e. 0 (43) vi,α = vi,α ∈ , ˜i ˜i Vert γ and (44) ∈ δ = (δ ) i i,j j Vert γ We deﬁne the fundamental Nakajima variety (45) Mi (v) = M (v,δ ) γ γ i The Eq. (42) explains the importance of the fundamental Nakajima varieties. × The Nakajima varietie(cid:16)s Mγ(v,w) (cid:17)with(cid:16) the choice (31) ha(cid:17)v∈e a× holomorphic C - symmetry (its compact subgroup U(1) acts by an isometry): u C acts via · (46) u B , B˜ , I , J = u B , u B˜ , u I , u J e e i i e e i i (cid:71) Deﬁne Nakajima-Young variety Yi (µ) to be the connected component of the ﬁxed point γ set: × (47) Mi (v)C = Yi (µ) γ γ ∈ µ(cid:16)Λi [v] (cid:17) γ with × (48) Λi [v] = π Mi (v)C γ (cid:71)0 γ ∈ denoting the set of connected components. We deﬁne the sets Λi for i Vert : γ γ (49) Λi = Λi [v] γ γ ∈ v ZV≥ertγ ∈ 0 For µ Λi [v] we deﬁne: γ | | ∈ (50) µ = v ZV≥ertγ 0 Each Nakajima-Young variety Yi (µ) carries a set of vector bundles: γ −→ (51) V i (µ) (cid:88) Yi (µ) ∈ ≥ j,n γ where j Vert , n 0, and γ B (52) V i (µ) = I(C) . j,n p ∈P j p [γ], (cid:96) =n i(cid:77) p∈ The stability condition (34) implies, for any j Vert : γ ∞ (53) V = V i j j,n n=0 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: BPS/CFT,

text: QQ-CHARACTERS,

text: GAUGE

text: ORIGAMI

text: where

text: vi,α

text: ZV≥ertγ

text: for

text: each

text: (i,α),

text: i.e.

text: vi,α

text: vi,α

text: ˜i

text: ˜i

text: Vert

text: γ

text: and

text: δ

text: (δ

text: i

text: i,j

text: j

text: Vert

text: γ

text: We

text: deﬁne

text: the

text: fundamental

text: Nakajima

text: variety

text: Mi

text: (v)

text: M

text: (v,δ

text: γ

text: γ

text: i

text: The

text: Eq.

text: explains

text: the

text: importance

text: of

text: the

text: fundamental

text: Nakajima

text: varieties.

text: The

text: Nakajima

text: Mγ(v,w)

text: the

text: choice

text: a×

text: holomorphic

text: C

text: symmetry

text: (its

text: compact

text: subgroup

text: acts

text: by

text: an

text: isometry):

text: u

text: C

text: acts

text: via

text: u

text: B

text: B˜

text: I

text: J

text: u

text: B

text: u

text: B˜

text: u

text: I

text: u

text: J

text: e

text: e

text: i

text: i

text: e

text: e

text: i

text: i

text: Deﬁne

text: Nakajima-Young

text: variety

text: Yi

text: (µ)

text: to

text: be

text: the

text: connected

text: component

text: of

text: the

text: ﬁxed

text: point

text: γ

text: set:

text: Mi

text: (v)C

text: Yi

text: (µ)

text: γ

text: γ

text: [v]

text: γ

text: with

text: Λi

text: [v]

text: π

text: Mi

text: (v)C

text: γ

text: γ

text: denoting

text: the

text: set

text: of

text: connected

text: components.

text: We

text: deﬁne

text: the

text: sets

text: Λi

text: for

text: i

text: Vert

text: γ

text: γ

text: Λi

text: Λi

text: [v]

text: γ

text: γ

text: v

text: ZV≥ertγ

text: For

text: µ

text: Λi

text: [v]

text: we

text: deﬁne:

text: γ

text: µ

text: v

text: ZV≥ertγ

text: Each

text: Nakajima-Young

text: variety

text: Yi

text: (µ)

text: carries

text: a

text: set

text: of

text: vector

text: bundles:

text: γ

text: V

text: i

text: (µ)

text: Yi

text: (µ)

text: j,n

text: γ

text: where

text: j

text: Vert

text: n

text: and

text: γ

text: B

text: V

text: i

text: (µ)

text: I(C)

text: j,n

text: p

text: ∈P

text: j

text: p

text: [γ],

text: =n

text: p∈

text: The

text: stability

text: condition

text: implies,

text: for

text: any

text: j

text: Vert

text: γ

text: V

text: V

text: i

text: j

text: j,n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 10 NIKITA NEKRASOV ≡ It is easy to show that J 0 on all Yi (v;µ), and V i = Cδ . Let us clarify the origin of γ × j,0 i,j the direct sum decomposition (53). The C -invariance of the G (v)-orbit of (B ,B˜ ,I,J) γ e e means that the transformation (46) can be compensated by an element ∈ : (g (u)) j j Vert γ (54) − − − gt(e)(u)Begs(e)(u) 1 = u Be , gs(e)(s)B˜egt((cid:16)1e)(u) = u B˜e , (cid:17) gi(u)I = u I , Jgi(u) 1 = u J Then − ⊂ (55) V i = Ker g (u) un+1 V j,n j j are obviously mutually orthogonal for diﬀerent n’s. The ranks νi (µ) = rkV i (µ) are (cid:88) j,n j,n important local invariants of Yi (µ). By deﬁnition: γ ∞ (56) νi (µ) = v j,n j n=0 T The K-theory class of the tangent bundle to Yi (µ) can be expressed in terms of (cid:104) (cid:105) (cid:104) (cid:105) Yi (µ) γ γ those of i : V j,n (cid:88) (cid:104) (cid:16) (cid:17) (cid:16) (cid:17)(cid:105) T = V i Yi (µ) i,0 γ ⊕ + (cid:88) Ho(cid:104)m V i(cid:16) ,V i (cid:17) Ho(cid:16)m V i ,V(cid:17)(cid:105)i (57) ≥ ∈ t(e),n s(e),n+1 s(e),n t(e),n+1 n 0,e Edge γ − ⊕ Hom V i ,V i Hom V i ,V i . ≥(cid:98) ∈ j,n j,n j,n j,n+2 n 0,j Vert γ { } { } Remark. In the case of γ = A , where Edge = e , Vert = 0 , s(e) = t(e) = 0, the 0 γ γ fundamental Nakajima variety is the Hilbert scheme of v points on C2, a.k.a. the moduli space of noncommutative U(1) instantons on R4, while the Nakajima-Young varieties are the connected components of the so-called graded Hilbert scheme of v points. To specify the basic local model data we ﬁx: (1) The string (58) ∈ ε¯ = (ε ) a a 4 of complex numbers which sum to zero: 4 (59) (cid:71) ε1 + ε2 + ε3 + ε4 = 0 ≥ ∈ (2) The string of non-negative integers , . Let n¯ 6 n 0 A 6 A ≈ { | ∈ ∈ } (60) N = [n ] (A,α) A 6,α [n ] . ∈ A A A 6 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: NIKITA

text: NEKRASOV

text: It

text: is

text: easy

text: to

text: show

text: that

text: J

text: on

text: all

text: Yi

text: (v;µ),

text: and

text: V

text: i

text: Cδ

font: BYMFCZ+Kp--M-Syb-Regular

text: Let

text: us

text: clarify

text: the

text: origin

text: of

text: γ

text: i,j

text: the

text: direct

text: sum

text: decomposition

text: The

text: C

text: -invariance

text: of

text: the

text: G

text: (v)-orbit

text: of

text: (B

text: ,B˜

text: ,I,J)

text: γ

text: e

text: e

text: means

text: that

text: the

text: transformation

text: can

text: be

text: compensated

text: by

text: an

text: element

text: (g

text: (u))

text: j

text: j

text: Vert

text: γ

text: gt(e)(u)Begs(e)(u)

text: u

text: Be

text: u

text: B˜e

text: gi(u)I

text: u

text: I

text: Jgi(u)

text: u

text: J

text: Then

text: V

text: i

text: Ker

text: g

text: (u)

text: V

text: j,n

text: j

text: j

text: are

text: obviously

text: mutually

text: orthogonal

text: for

text: diﬀerent

text: n’s.

text: The

text: ranks

text: νi

text: (µ)

text: rkV

text: i

text: (µ)

text: are

text: j,n

text: j,n

text: important

text: local

text: invariants

text: of

text: Yi

text: (µ).

text: By

text: deﬁnition:

text: γ

text: νi

text: (µ)

text: v

text: j,n

text: j

text: T

text: The

text: K-theory

text: class

text: of

text: the

text: tangent

text: bundle

text: to

text: Yi

text: (µ)

text: can

text: be

text: expressed

text: in

text: terms

text: of

text: Yi

text: (µ)

text: γ

text: γ

text: those

text: of

text: i

text: V

text: j,n

text: T

text: V

text: i

text: Yi

text: (µ)

text: γ

text: V

text: ,V

text: i

text: V

text: i

text: t(e),n

text: s(e),n

text: n

text: Edge

text: γ

text: Hom

text: V

text: i

text: ,V

text: i

text: Hom

text: V

text: i

text: ,V

text: i

text: j,n

text: j,n

text: j,n

text: n

text: Vert

text: γ

text: Remark.

text: In

text: the

text: case

text: of

text: γ

text: A

text: where

text: Edge

text: e

text: Vert

text: s(e)

text: t(e)

text: the

text: γ

text: γ

text: fundamental

text: Nakajima

text: variety

text: is

text: the

text: Hilbert

text: scheme

text: of

text: v

text: points

text: on

text: a.k.a.

text: the

text: moduli

text: space

text: of

text: noncommutative

text: instantons

text: on

text: while

text: the

text: Nakajima-Young

text: varieties

text: are

text: the

text: connected

text: components

text: of

text: the

text: so-called

text: graded

text: Hilbert

text: scheme

text: of

text: v

text: points.

text: To

text: specify

text: the

text: basic

text: local

text: model

text: data

text: we

text: ﬁx:

text: The

text: string

text: ε¯

text: (ε

text: a

text: a

text: of

text: complex

text: numbers

text: which

text: sum

text: to

text: zero:

text: ε1

text: ε2

text: ε3

text: ε4

text: The

text: string

text: of

text: non-negative

text: integers

text: Let

text: n¯

text: n

text: A

text: A

text: N

text: [n

text: (A,α)

text: A

text: [n

text: A

text: A

text: A

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∗ Network patterns in exponentially growing 2D bioﬁlms Cameron Zachreson,1 Xinhui Yap,1 Erin S. Gloag,1,1 Raz Shimoni,1 Cynthia B. Whitchurch,1 and Milos Toth1 (Dated: May 29, 2020) Anisotropic collective patterns occur frequently in the morphogenesis of 2D bioﬁlms. These pat- terns are often attributed to growth regulation mechanisms and diﬀerentiation based on gradients of diﬀusing nutrients and signalling molecules. Here, we employ a model of bacterial growth dynamics to show that even in the absence of growth regulation or diﬀerentiation, conﬁnement by an enclosing medium such as agar can itself lead to stable pattern formation over time scales that are employed in experiments. The underlying mechanism relies on path formation through physical deformation of the enclosing environment. PACS numbers: 87.18.Fx, 87.17.Jj, 87.18.Gh In surface-associated bacterial colonies, growth reg- a) b) ulation caused by a diﬀusion-limited nutrient supply has been suggested as a primary mechanism of pattern formation, resulting in branched, locally anisotropic mor- phologies [1, 2]. However, diﬀusion-limited growth does not tell the whole story. Mechanical processes are known to play essential roles in morphogenesis [3], and we show edge interior here that deformation of the enclosing environment by moving bacteria can lead to the emergence of persistent, c) d) stable, anisotropic network patterns such as those in 0.20 edge Fig. 1(a,b) even under conditions of exponential colony interior growth. Furthermore, we present strong evidence that 0.15 model in Pseudomonas aeruginosa, well-studied trail follow- P(kg) 0.10 e) ing mechanisms involving the deposition of extracellular 0.05 polymeric substances (EPSs, or “slime”) cannot produce f) coverslip these patterns in the absence of such mechanical eﬀects. 0.00 -0.5 0.0 0.5k 1.0 1.5x10-3 substratum g Interstitial bioﬁlms form when bacteria are introduced g) to the space between two apposed surfaces and are con- strained to a quasi-2D arrangement. If one surface is a hydrogel such as agar or gellan gum [4, 6], the bacteria FIG. 1. (a, b) Phase-contrast images of the edge and inte- have access to nutrients diﬀusing through this medium rior (respectively) of an expanding P. aeruginosa interstitial [7]. Here we consider such a situation, where nutrient bioﬁlm [4]. Each image is frame 500 from a total of 1000 used to make Supplemental Movies S1 and S2 [5]. Binary masks of depletion is negligible and the bacterial growth rate is the cells produced by the image segmentation algorithm are not retarded in the colony interior. This assertion is sup- shown in red. (c) Histograms of the probability P for a cell ported by histograms of individual growth rates we ob- to be growing at rate k , as calculated from the movies cor- g tained from of the edge and interior of an expanding P. responding to the colony edge (a, solid bars in c) and interior aerugionsa interstitial bioﬁlm [Fig. 1(a,b), Supplemen- (b, dashed bars in c). The dashed line represents the growth tal Movies S1, S2 [5] respectively]. The histograms show rate used in our simulations. (d-g) Schematic illustrations of that growth rates measured in the colony interior and the the processes comprising our model of bacterial behavior. colony edge are approximately equivalent [Fig. 1(c)], and nutrient depletion therefore cannot be used to explain the network morphology seen in Fig. 1(a,b), characterized by creted by the moving bacteria [10], a phenomenon that dense trails of bacteria and voids of zero density. has also been suggested to result in trail-following be- Previously, Gloag et al. observed that these bacte- havior [11, 12]. To investigate the relative importance of ria can deform the soft enclosing material through which these two processes in the emergence of the observed net- they move, and conﬁnement in the resulting ‘furrows’ work morphology, we carried out simulations of motile appears to contribute to network pattern formation [4]. bacteria that interact with the hydrogel environment. However, P. aeruginosa and many other surface-motile The behavioral rules implemented in our simulations are bacteria [8] move through the extension and retraction illustrated in Fig. 1(d-g). Each simulation was initiated of type IV pili (T4P) [9], which have increased binding with a single motile, growing cell, and terminated after × aﬃnity to extracellular polymeric substances (EPS) se- 12 cell division cycles (t = 1.37 105 s). Our results f ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Network

label: title

text: patterns

text: in

text: exponentially

text: growing

text: bioﬁlms

text: Cameron

label: author

text: Xinhui

text: Erin

text: S.

text: Raz

text: Cynthia

text: B.

text: and

text: Milos

text: (Dated:

text: May

label: date

text: Anisotropic

label: abstract

text: collective

text: patterns

text: occur

text: frequently

text: in

text: the

text: morphogenesis

text: of

text: bioﬁlms.

text: These

text: pat-

text: terns

text: are

text: often

text: attributed

text: to

text: growth

text: regulation

text: mechanisms

text: and

text: diﬀerentiation

text: based

text: on

text: gradients

text: of

text: diﬀusing

text: nutrients

text: and

text: signalling

text: molecules.

text: Here,

text: we

text: employ

text: a

text: model

text: of

text: bacterial

text: growth

text: dynamics

text: to

text: show

text: that

text: even

text: in

text: the

text: absence

text: of

text: growth

text: regulation

text: or

text: diﬀerentiation,

text: conﬁnement

text: by

text: an

text: enclosing

text: medium

text: such

text: as

text: agar

text: can

text: itself

text: lead

text: to

text: stable

text: pattern

text: formation

text: over

text: time

text: scales

text: that

text: are

text: employed

text: in

text: experiments.

text: The

text: underlying

text: mechanism

text: relies

text: on

text: path

text: formation

text: through

text: physical

text: deformation

text: of

text: the

text: enclosing

text: environment.

text: PACS

text: numbers:

text: In

text: surface-associated

text: bacterial

text: colonies,

text: growth

text: reg-

text: a)

text: b)

text: ulation

text: caused

text: by

text: a

text: diﬀusion-limited

text: nutrient

text: supply

text: has

text: been

text: suggested

text: as

text: a

text: primary

text: mechanism

text: of

text: pattern

text: formation,

text: resulting

text: in

text: branched,

text: locally

text: anisotropic

text: mor-

text: phologies

text: However,

text: diﬀusion-limited

text: growth

text: does

text: not

text: tell

text: the

text: whole

text: story.

text: Mechanical

text: processes

text: are

text: known

text: to

text: play

text: essential

text: roles

text: in

text: morphogenesis

text: and

text: we

text: show

text: edge

text: interior

text: here

text: that

text: deformation

text: of

text: the

text: enclosing

text: environment

text: by

text: moving

text: bacteria

text: can

text: lead

text: to

text: the

text: emergence

text: of

text: persistent,

text: c)

text: d)

text: stable,

text: anisotropic

text: network

text: patterns

text: such

text: as

text: those

text: in

text: edge

text: Fig.

text: even

text: under

text: conditions

text: of

text: exponential

text: colony

text: interior

text: growth.

text: Furthermore,

text: we

text: present

text: strong

text: evidence

text: that

text: model

text: in

text: Pseudomonas

text: aeruginosa,

text: well-studied

text: trail

text: follow-

text: P(kg)

text: e)

text: ing

text: mechanisms

text: involving

text: the

text: deposition

text: of

text: extracellular

text: polymeric

text: substances

text: (EPSs,

text: or

text: “slime”)

text: cannot

text: produce

text: f)

text: coverslip

text: these

text: patterns

text: in

text: the

text: absence

text: of

text: such

text: mechanical

text: eﬀects.

text: substratum

text: g

text: Interstitial

text: bioﬁlms

text: form

text: when

text: bacteria

text: are

text: introduced

text: g)

text: to

text: the

text: space

text: between

text: two

text: apposed

text: surfaces

text: and

text: are

text: con-

text: strained

text: to

text: a

text: arrangement.

text: If

text: one

text: surface

text: is

text: a

text: hydrogel

text: such

text: as

text: agar

text: or

text: gellan

text: gum

text: the

text: bacteria

text: FIG.

text: (a,

text: b)

text: Phase-contrast

text: images

text: of

text: the

text: edge

text: and

text: inte-

text: have

text: access

text: to

text: nutrients

text: diﬀusing

text: through

text: this

text: medium

text: rior

text: (respectively)

text: of

text: an

text: expanding

text: P.

text: aeruginosa

text: interstitial

text: Here

text: we

text: consider

text: such

text: a

text: situation,

text: where

text: nutrient

text: bioﬁlm

text: Each

text: image

text: is

text: frame

text: from

text: a

text: total

text: of

text: used

text: to

text: make

text: Supplemental

text: Movies

text: and

text: Binary

text: masks

text: of

text: depletion

text: is

text: negligible

text: and

text: the

text: bacterial

text: growth

text: rate

text: is

text: the

text: cells

text: produced

text: by

text: the

text: image

text: segmentation

text: algorithm

text: are

text: not

text: retarded

text: in

text: the

text: colony

text: interior.

text: This

text: assertion

text: is

text: sup-

text: shown

text: in

text: red.

text: (c)

text: Histograms

text: of

text: the

text: probability

text: P

text: for

text: a

text: cell

text: ported

text: by

text: histograms

text: of

text: individual

text: growth

text: rates

text: we

text: ob-

text: to

text: be

text: growing

text: at

text: rate

text: k

text: as

text: calculated

text: from

text: the

text: movies

text: cor-

text: g

text: tained

text: from

text: of

text: the

text: edge

text: and

text: interior

text: of

text: an

text: expanding

text: P.

text: responding

text: to

text: the

text: colony

text: edge

text: (a,

text: solid

text: bars

text: in

text: c)

text: and

text: interior

text: aerugionsa

text: interstitial

text: bioﬁlm

text: [Fig.

text: Supplemen-

text: (b,

text: dashed

text: bars

text: in

text: c).

text: The

text: dashed

text: line

text: represents

text: the

text: growth

text: tal

text: Movies

text: respectively].

text: The

text: histograms

text: show

text: rate

text: used

text: in

text: our

text: simulations.

text: (d-g)

text: Schematic

text: illustrations

text: of

text: that

text: growth

text: rates

text: measured

text: in

text: the

text: colony

text: interior

text: and

text: the

text: the

text: processes

text: comprising

text: our

text: model

text: of

text: bacterial

text: behavior.

text: colony

text: edge

text: are

text: approximately

text: equivalent

text: [Fig.

text: and

text: nutrient

text: depletion

text: therefore

text: cannot

text: be

text: used

text: to

text: explain

text: the

text: network

text: morphology

text: seen

text: in

text: Fig.

text: characterized

text: by

text: creted

text: by

text: the

text: moving

text: bacteria

text: a

text: phenomenon

text: that

text: dense

text: trails

text: of

text: bacteria

text: and

text: voids

text: of

text: zero

text: density.

text: has

text: also

text: been

text: suggested

text: to

text: result

text: in

text: trail-following

text: be-

text: Previously,

text: Gloag

text: et

text: al.

text: observed

text: that

text: these

text: bacte-

text: havior

text: To

text: investigate

text: the

text: relative

text: importance

text: of

text: ria

text: can

text: deform

text: the

text: soft

text: enclosing

text: material

text: through

text: which

text: these

text: two

text: processes

text: in

text: the

text: emergence

text: of

text: the

text: observed

text: net-

text: they

text: move,

text: and

text: conﬁnement

text: in

text: the

text: resulting

text: ‘furrows’

text: work

text: morphology,

text: we

text: carried

text: out

text: simulations

text: of

text: motile

text: appears

text: to

text: contribute

text: to

text: network

text: pattern

text: formation

text: bacteria

text: that

text: interact

text: with

text: the

text: hydrogel

text: environment.

text: However,

text: P.

text: aeruginosa

text: and

text: many

text: other

text: surface-motile

text: The

text: behavioral

text: rules

text: implemented

text: in

text: our

text: simulations

text: are

text: bacteria

text: move

text: through

text: the

text: extension

text: and

text: retraction

text: illustrated

text: in

text: Fig.

text: Each

text: simulation

text: was

text: initiated

text: of

text: type

text: IV

text: pili

text: which

text: have

text: increased

text: binding

text: with

text: a

text: single

text: motile,

text: growing

text: cell,

text: and

text: terminated

text: after

text: aﬃnity

text: to

text: extracellular

text: polymeric

text: substances

text: (EPS)

text: se-

text: cell

text: division

text: cycles

text: (t

text: s).

text: Our

text: results

text: f

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##