text: 26 ALLEN KNUTSON Since (i + 1, j) is crucial, the box (i + 1, j + 1) to its right is crossed out from above, so the entire second column of R is crossed out. We learned before that the top left corner (i, j) of R is crossed out. But the bottom left corner (f−1(j), j) is not (since it contains a dot); go up from it inside the diagram to ﬁnd an essential box (r, j). (It will automatically be crucial, (cid:48) (cid:48) otherwise [r, j] would contain a crucial interval [r , j] with r > r, but this would then give a lower essential box inside R and contradict the choice of r.) (cid:96) If there were dots to the right of R in rows [i + 1, f−1(j) − 1], they would cross ou→t more of R’s left column, and we would have r > i + 1. The interval [r, j] wouldn’t be X -safe i j (cid:3) unless r = j. But then [i + 1, j] wouldn’t be crucial; it would split as [i + 1, j − 1] [j, j]. → Proposition 3.13. The safe sweep Ψ (Π ) is again a positroid variety, Π (cid:48). i j J J ∩ L→et r be the rank bound on [i + 1, j] in the deﬁnition of Π . Then Π = Π (cid:48) X ≤ and ⊆ ∩ J J J [i+1,j] r X (Π ) Π (cid:48) X ≤ . i j J J [i,j−1] r → Proof. To apply proposition 3.7, we conﬁrm that Π (cid:48) is X -invariant, and Π isn’t. J i j J ◦ Let R again denote the rectangle with rows [i, f−1(j)] and columns [j, f(i)], and R the subrectangle missing the outer rows and columns. We know the following about the (cid:48) ◦ diagrams of J and J in R and R : ◦ (1) The diagrams agree on R , where (by the proof of lemma 3.12) they consist of entire ◦ columns of R . ◦ (2) The J diagram contains the column segment immediately to the left of R , and not (cid:48) the one immediately to the right. In J the opposite is true. (cid:48) (3) The J (resp. J ) diagram doesn’t contain the row segment immediately above (resp. ◦ below) R . ◦ (cid:48) (4) The row segment below (resp. above) R in the diagram of J (resp. J ) is a continu- ◦ ation of the columns in R . (cid:48) The rank conditions of J and J agree except on R (and do agree on the top row and right column). By (4) above, the only possible essent→ial conditions of J(cid:48) inside R are on the top→row, so on an interval [i, s], and any su→ch is X -invariant. Hence Π (cid:48) is deﬁned by i j J -invariant conditions, and is thus -invariant. X X i j i j Similarly, the only possible essential boxes inside R of→J are in the second row, (i + 1, s), ≥ s j. None of those with s > j can be crucial, or else X would be unsafe for Π . Hence ∩ i j J Π = Π (cid:48) → X ≤ w→here r is the rank bound→on [i + 1, j→] in the deﬁnition of Π , and J J [i+1,j] r J ∩ ⊆ ∩ ∩ X Π = X (Π (cid:48) X ≤ ) X Π (cid:48) X X ≤ = Π (cid:48) X ≤ . i j J i j J [i+1,j] r i j J i j [i+1,j] r J [i,j−1] r by proposition 3→.6 and lemma 3.8. If Π were X -invariant, then we would have J i j ⊆ ∩ ∩ ∩ ∪ Π Π (cid:48) X ≤ X ≤ = Π (cid:48) (X ≤ X ≤ ) J J [i+1,j] r [i,j−1] r J [i+1,j−1] r−1 [i,j] r ∩ ∪ ∩ = (Π (cid:48) X ≤ ) (Π (cid:48) X ≤ ) as sets J [i+1,j−1] r−1 J [i,j] r

text: ALLEN

text: KNUTSON

text: Since

text: (i

text: j)

text: is

text: crucial,

text: the

text: box

text: (i

text: j

text: to

text: its

text: right

text: is

text: crossed

text: out

text: from

text: above,

text: so

text: the

text: entire

text: second

text: column

text: of

text: R

text: is

text: crossed

text: out.

text: We

text: learned

text: before

text: that

text: the

text: top

text: left

text: corner

text: (i,

text: j)

text: of

text: R

text: is

text: crossed

text: out.

text: But

text: the

text: bottom

text: left

text: corner

text: j)

text: is

text: not

text: (since

text: it

text: contains

text: a

text: dot);

text: go

text: up

text: from

text: it

text: inside

text: the

text: diagram

text: to

text: ﬁnd

text: an

text: essential

text: box

text: (r,

text: j).

text: (It

text: will

text: automatically

text: be

text: crucial,

text: otherwise

text: [r,

text: j]

text: would

text: contain

text: a

text: crucial

text: interval

text: [r

text: j]

text: with

text: r

text: r,

text: but

text: this

text: would

text: then

text: give

text: a

text: lower

text: essential

text: box

text: inside

text: R

text: and

text: contradict

text: the

text: choice

text: of

text: r.)

text: If

text: there

text: were

text: dots

text: to

text: the

text: right

text: of

text: R

text: in

text: rows

text: [i

text: they

text: would

text: cross

text: ou→t

text: more

text: of

text: R’s

text: left

text: column,

text: and

text: we

text: would

text: have

text: r

text: i

text: The

text: interval

text: [r,

text: j]

text: wouldn’t

text: be

text: X

text: -safe

text: i

text: j

text: unless

text: r

text: j.

text: But

text: then

text: [i

text: j]

text: wouldn’t

text: be

text: crucial;

text: it

text: would

text: split

text: as

text: [i

text: j

text: [j,

text: j].

text: Proposition

text: The

text: safe

text: sweep

text: Ψ

text: (Π

text: is

text: again

text: a

text: positroid

text: variety,

text: Π

text: i

text: j

text: J

text: J

text: L→et

text: r

text: be

text: the

text: rank

text: bound

text: on

text: [i

text: j]

text: in

text: the

text: deﬁnition

text: of

text: Π

text: Then

text: Π

text: Π

text: X

text: and

text: J

text: J

text: J

text: r

text: X

text: (Π

text: Π

text: X

text: i

text: j

text: J

text: J

text: r

text: Proof.

text: To

text: apply

text: proposition

text: we

text: conﬁrm

text: that

text: Π

text: is

text: X

text: -invariant,

text: and

text: Π

text: isn’t.

text: J

text: i

text: j

text: J

text: Let

text: R

text: again

text: denote

text: the

text: rectangle

text: with

text: rows

text: [i,

text: and

text: columns

text: [j,

text: f(i)],

text: and

text: R

text: the

text: subrectangle

text: missing

text: the

text: outer

text: rows

text: and

text: columns.

text: We

text: know

text: the

text: following

text: about

text: the

text: diagrams

text: of

text: J

text: and

text: J

text: in

text: R

text: and

text: R

text: The

text: diagrams

text: agree

text: on

text: R

text: where

text: (by

text: the

text: proof

text: of

text: lemma

text: they

text: consist

text: of

text: entire

text: columns

text: of

text: R

text: The

text: J

text: diagram

text: contains

text: the

text: column

text: segment

text: immediately

text: to

text: the

text: left

text: of

text: R

text: and

text: not

text: the

text: one

text: immediately

text: to

text: the

text: right.

text: In

text: J

text: the

text: opposite

text: is

text: true.

text: The

text: J

text: (resp.

text: J

text: diagram

text: doesn’t

text: contain

text: the

text: row

text: segment

text: immediately

text: above

text: (resp.

text: below)

text: R

text: The

text: row

text: segment

text: below

text: (resp.

text: above)

text: R

text: in

text: the

text: diagram

text: of

text: J

text: (resp.

text: J

text: is

text: a

text: continu-

text: ation

text: of

text: the

text: columns

text: in

text: R

text: The

text: rank

text: conditions

text: of

text: J

text: and

text: J

text: agree

text: except

text: on

text: R

text: (and

text: do

text: agree

text: on

text: the

text: top

text: row

text: and

text: right

text: column).

text: By

text: above,

text: the

text: only

text: possible

text: essent→ial

text: conditions

text: of

text: inside

text: R

text: are

text: on

text: the

text: top→row,

text: so

text: on

text: an

text: interval

text: [i,

text: s],

text: and

text: any

text: su→ch

text: is

text: X

text: -invariant.

text: Hence

text: Π

text: is

text: deﬁned

text: by

text: i

text: j

text: J

text: -invariant

text: conditions,

text: and

text: is

text: thus

text: -invariant.

text: X

text: X

text: i

text: j

text: i

text: j

text: Similarly,

text: the

text: only

text: possible

text: essential

text: boxes

text: inside

text: R

text: of→J

text: are

text: in

text: the

text: second

text: row,

text: (i

text: s),

text: s

text: j.

text: of

text: those

text: with

text: s

text: j

text: can

text: be

text: crucial,

text: or

text: else

text: X

text: would

text: be

text: unsafe

text: for

text: Π

text: Hence

text: i

text: j

text: J

text: Π

text: Π

text: X

text: w→here

text: r

text: is

text: the

text: rank

text: bound→on

text: [i

text: j→]

text: in

text: the

text: deﬁnition

text: of

text: Π

text: and

text: J

text: J

text: r

text: J

text: X

text: Π

text: X

text: (Π

text: X

text: X

text: Π

text: X

text: X

text: Π

text: X

text: i

text: j

text: J

text: i

text: j

text: J

text: r

text: i

text: j

text: J

text: i

text: j

text: r

text: J

text: r

text: by

text: proposition

text: and

text: lemma

text: If

text: Π

text: were

text: X

text: -invariant,

text: then

text: we

text: would

text: have

text: J

text: i

text: j

text: Π

text: Π

text: X

text: X

text: Π

text: (X

text: X

text: J

text: J

text: r

text: r

text: J

text: [i,j]

text: r

text: (Π

text: X

text: (Π

text: X

text: as

text: sets

text: J

text: J

text: [i,j]

text: r


text: 6 ALLEN KNUTSON → If f = f(P) for an IP pipe dream using m distinct letters, then X Π has at most m + 1 ⊆ i j f components.4 The intersection of any set(cid:20)S C o(cid:21)f these(cid:88)components is again an interval positroid (cid:91) variety Π . In particular, as K-classes, f(S) → [Π ] = [X Π ] = Π (cid:48) = (−1)|S|−1 [Π ]. f i j f f f(S) (cid:48)∈ ⊆ (cid:54) ∅ f C S C, S= The precise version of the theorem (enumerating the components in C) will be theorem A 3.15, which also includes the extension to K (Gr ( n)). T k ≤ Given an IP pipe dream P, and a box (i, j), i j, deﬁne (as in ﬁgure 2) the slice s(P, i, j) of P at (i, j) as the data of the labels on • ∪ ≤ ≤ ∪ ≤ the South edges of {(m, m) : m < i} {(i, m) : i m j} {(i−1, m) : j < m n} • the East edges of (i, j) and {(m, n) : m < i}. FIGURE 2. An n = 6 example of a slice at (3, 5). The slice is the thick blue edges and the (unpictured) labels thereon. Not every labeling s of these edges arises from an IP pipe dream; we spell out the § § conditions in . To each “viable” slice s, we associate in a partial permutation f(s). For now, it sufﬁces to mention that f(s(P, n, n)) = f(P), and Π = Xλ(P). f(s(P,1,1)) (cid:48) Given a slice s, we can consider what tiles can be placed at (i, j), making new slices s at (i, j − 1) (or at (i − 1, n) if j = i). Theorem 1.4. Let s be a slice at (i, j), and Π the associated interval positroid variety (deﬁned § (cid:48) f(s) in ). The shift (i, j) is safe for f(s). Let {s } be the set of viable slices arising from a tile at (i, j). → (cid:0) (cid:1) (1) If the South and East labels of (i, j) in s are not both zero, then Π is X -invariant. (cid:48) (cid:48) (cid:0) (cid:1)f(s) i j There is a unique s , and its f(s ) is unchanged from f(s). (a) If the labels are equal but not 0, forcing the a = 0 elbows tile, then f(s) i = j. (cid:54) (b) If the labels are distinct, forcing the crossing tile, then f(s) i = j (and is undeﬁned if the East label is 0). (2) If the South and East labels of (i, j) in s are both 0, then the various {Π (cid:48) } are the sweep f(s ) (for the equivariant tile) and the components of the shift (for the other possible tiles). § 4I thank Mathias Lederer for this observation. The important case m = 1 is explored in . ##LTLine##

label: paragraph

font: AJRIYF+URWPalladioL-Roma

text: ALLEN

text: KNUTSON

text: If

font: PELFSH+URWPalladioL-Ital

text: f

text: f(P)

text: for

text: an

text: IP

text: pipe

text: dream

text: using

text: m

text: distinct

text: letters,

text: then

text: X

font: unknown

text: Π

text: has

text: at

text: most

text: m

text: i

text: j

text: f

text: The

text: intersection

text: of

text: any

text: C

text: is

text: again

text: an

text: interval

text: positroid

text: variety

text: Π

text: In

text: particular,

text: as

text: K-classes,

text: f(S)

text: [Π

text: [X

text: Π

text: Π

text: [Π

text: f

text: i

text: j

text: f

text: f

text: f(S)

text: f

text: C

text: S

text: C,

text: S=

text: The

text: precise

text: version

text: of

text: the

text: theorem

text: (enumerating

text: the

text: components

text: in

text: C)

text: will

text: be

text: theorem

text: A

text: which

text: also

text: includes

text: the

text: extension

text: to

text: K

text: (Gr

text: n)).

text: T

text: k

text: Given

text: an

text: IP

text: pipe

text: dream

text: P,

text: and

text: a

text: box

text: (i,

text: j),

text: i

text: j,

text: deﬁne

text: (as

text: in

text: ﬁgure

text: the

text: slice

text: s(P,

text: i,

text: j)

text: of

text: P

text: at

text: (i,

text: j)

text: as

text: the

text: data

text: of

text: the

text: labels

text: on

text: the

text: South

text: edges

text: of

text: {(m,

text: m)

text: m

text: i}

text: {(i,

text: m)

text: i

text: m

text: j}

text: m)

text: j

text: m

text: n}

text: the

text: East

text: edges

text: of

text: (i,

text: j)

text: and

text: {(m,

text: n)

text: m

text: i}.

text: FIGURE

text: An

text: n

text: example

text: of

text: a

text: slice

text: at

text: The

text: slice

text: is

text: the

text: thick

text: blue

text: edges

text: and

text: the

text: (unpictured)

text: labels

text: thereon.

text: Not

text: every

text: labeling

text: s

text: of

text: these

text: edges

text: arises

text: from

text: an

text: IP

text: pipe

text: dream;

text: we

text: spell

text: out

text: the

text: conditions

text: in

text: To

text: each

text: “viable”

text: slice

text: s,

text: we

text: associate

text: in

text: a

text: partial

text: permutation

text: f(s).

text: For

text: now,

text: it

text: sufﬁces

text: to

text: mention

text: that

text: f(s(P,

text: n,

text: n))

text: f(P),

text: and

text: Π

text: Xλ(P).

text: Given

text: a

text: slice

text: s,

text: we

text: can

text: consider

text: what

text: tiles

text: can

text: be

text: placed

text: at

text: (i,

text: j),

text: making

text: new

text: slices

text: s

text: at

text: (i,

text: j

text: (or

text: at

text: (i

text: n)

text: if

text: j

text: i).

text: Theorem

text: Let

text: s

text: be

text: a

text: slice

text: at

text: (i,

text: j),

text: and

text: Π

text: the

text: associated

text: interval

text: positroid

text: variety

text: (deﬁned

text: f(s)

text: in

text: The

text: shift

text: (i,

text: j)

text: is

text: safe

text: for

text: f(s).

text: Let

text: {s

text: be

text: the

text: set

text: of

text: viable

text: slices

text: arising

text: from

text: a

text: tile

text: at

text: (i,

text: j).

text: If

text: the

text: South

text: and

text: East

text: labels

text: of

text: (i,

text: j)

text: in

text: s

text: are

text: not

text: both

text: zero,

text: then

text: Π

text: is

text: X

text: -invariant.

text: i

text: j

text: There

text: is

text: a

text: unique

text: s

text: and

text: its

text: f(s

text: is

text: unchanged

text: from

text: f(s).

text: (a)

text: If

text: the

text: labels

text: are

text: equal

text: but

text: not

text: forcing

text: the

text: a

text: elbows

text: tile,

text: then

text: f(s)

text: i

text: j.

text: (b)

text: If

text: the

text: labels

text: are

text: distinct,

text: forcing

text: the

text: crossing

text: tile,

text: then

text: f(s)

text: i

text: j

text: (and

text: is

text: undeﬁned

text: if

text: the

text: East

text: label

text: is

text: If

text: the

text: South

text: and

text: East

text: labels

text: of

text: (i,

text: j)

text: in

text: s

text: are

text: both

text: then

text: the

text: various

text: {Π

text: are

text: the

text: sweep

text: f(s

text: (for

text: the

text: equivariant

text: tile)

text: and

text: the

text: components

text: of

text: the

text: shift

text: (for

text: the

text: other

text: possible

text: tiles).

text: thank

text: Mathias

text: Lederer

text: for

text: this

text: observation.

text: The

text: important

text: case

text: m

text: is

text: explored

text: in

text: ##LTLine##


text: 12 FRANCESCO GRANDE AND RAMAN SANYAL R Proposition 4.2. If V ⊂ d be a point conﬁguration of Theta rank 1, then Gen(V ) ≤ 2. Proof. From Theorem 1.1 we infer that the points V are in convex position and the polytope (cid:26) (cid:27) P = conv(V ) is 2-level. We may assume that the conﬁguration is spanning and hence up to aﬃne equivalence, the polytope is given by P = p ∈ Rd : −0 ≤ pi ≤ 1 for i = 1, . . . , d δ ≤ (cid:96) (p) ≤ δ+ for j = 1, . . . , n j j j − for unique linear functions (cid:96) (x) and δ < δ+. In particular, V ⊂ {0, 1}d. We claim that I(V ) j j j is generated by the quadrics − x (x − 1) for 1 ≤ i ≤ d, ((cid:96) (x) − δ )((cid:96) (x) − δ+) for 1 ≤ j ≤ n. i i j j j j The vanishing locus U is a smooth and real subset of {0, 1}d. Thus, the polynomials span a real ± radical ideal. Now, every vertex v ∈ V ⊆ {0, 1}d satisﬁes (cid:96) (v) = δ . Hence V ⊆ U. Conversely, j j (cid:3) every u ∈ U is a vertex of P and hence U ⊆ V . The following example illustrates the fact that degree of generation is invariant under projective transformations while Theta rank is not. Example 8. To see that generation in degrees ≤ 2 is necessary for Theta rank 1 but not suﬃ- cient, consider the planar point conﬁguration V = {(1, 0), (0, 1), (2, 0), (0, 2)}. The conﬁguration is clearly not 2-level and hence not Theta 1, however the vanishing ideal I(V ) is generated by x x and (x + x − 1)(x + x − 2) which implies Gen(V ) ≤ 2. 1 2 1 2 1 2 (2,0) (1,0) (0,0) (1,0) (2,0) The vanishing ideals of base conﬁgurations are easy to write down explicitly. Proposition 4.3. Let M = (E, B) be a matroid of rank r. The vanishing ideal for V is M generated by x2 − x for all e ∈ E, (cid:96) (x) − r, xC for all circuits C ⊂ E. e e E Proof. Any solution to the ﬁrst two sets of equations is of the form 1 for some B ⊆ E with B |B| = r. For the last set of equations, we note that (1 )C = 0 for all circuits C if and only if B B does not contain a circuit. This is equivalent to B ∈ B. Arguments similar to those used in the (cid:3) proof of Proposition 4.2 show that the polynomials generate a real radical ideal. Let us write MGen for the class of matroids M with Gen(V ) ≤ k. The previous proposition is a k M little deceiving in the sense that it suggests a direct connection between the size of circuits and the degree of generation. This is not quite true. Indeed, let G = K \e be the complete graph on 4 4 vertices minus an edge. Then M(G) has a circuit of cardinality 4 but M(G) ∈ MLev ⊆ MGen by 2 2 Theorem 3.9 and Proposition 4.2. The main result of this section is that for base conﬁgurations the condition of Proposition 4.2 is also suﬃcient. ##LTFigure## ##LTLine## ##LTLine##

text: FRANCESCO

text: GRANDE

text: AND

text: RAMAN

text: SANYAL

text: R

text: Proposition

text: If

text: V

text: d

text: be

text: a

text: point

text: conﬁguration

text: of

text: Theta

text: rank

text: then

text: Gen(V

text: Proof.

text: From

text: Theorem

text: we

text: infer

text: that

text: the

text: points

text: V

text: are

text: in

text: convex

text: position

text: and

text: the

text: polytope

text: P

text: conv(V

text: is

text: We

text: may

text: assume

text: that

text: the

text: conﬁguration

text: is

text: spanning

text: and

text: hence

text: up

text: to

text: aﬃne

text: equivalence,

text: the

text: polytope

text: is

text: given

text: by

text: P

text: p

text: Rd

text: −0

text: pi

text: for

text: i

text: d

text: δ

text: (p)

text: δ+

text: for

text: j

text: n

text: j

text: j

text: j

text: for

text: unique

text: linear

text: functions

text: (x)

text: and

text: δ

text: δ+.

text: In

text: particular,

text: V

text: We

text: claim

text: that

text: I(V

text: j

text: j

text: j

text: is

text: generated

text: by

text: the

text: quadrics

text: x

text: (x

text: for

text: i

text: d,

text: (x)

text: δ

text: (x)

text: δ+)

text: for

text: j

text: n.

text: i

text: i

text: j

text: j

text: j

text: j

text: The

text: vanishing

text: locus

text: U

text: is

text: a

text: smooth

text: and

text: real

text: subset

text: of

text: Thus,

text: the

text: polynomials

text: span

text: a

text: real

text: radical

text: ideal.

text: Now,

text: every

text: vertex

text: v

text: V

text: satisﬁes

text: (v)

text: δ

text: Hence

text: V

text: U.

text: Conversely,

text: j

text: j

text: every

text: u

text: U

text: is

text: a

text: vertex

text: of

text: P

text: and

text: hence

text: U

text: V

text: The

text: following

text: example

text: illustrates

text: the

text: fact

text: that

text: degree

text: of

text: generation

text: is

text: invariant

text: under

text: projective

text: transformations

text: while

text: Theta

text: rank

text: is

text: not.

text: Example

text: To

text: see

text: that

text: generation

text: in

text: degrees

text: is

text: necessary

text: for

text: Theta

text: rank

text: but

text: not

text: suﬃ-

text: cient,

text: consider

text: the

text: planar

text: point

text: conﬁguration

text: V

text: The

text: conﬁguration

text: is

text: clearly

text: not

text: and

text: hence

text: not

text: Theta

text: however

text: the

text: vanishing

text: ideal

text: I(V

text: is

text: generated

text: by

text: x

text: x

text: and

text: (x

text: x

text: x

text: which

text: implies

text: Gen(V

text: The

text: vanishing

text: ideals

text: of

text: base

text: conﬁgurations

text: are

text: easy

text: to

text: write

text: down

text: explicitly.

text: Proposition

text: Let

text: M

text: (E,

text: B)

text: be

text: a

text: matroid

text: of

text: rank

text: r.

text: The

text: vanishing

text: ideal

text: for

text: V

text: is

text: M

text: generated

text: by

text: x

text: for

text: all

text: e

text: E,

text: (x)

text: r,

text: xC

text: for

text: all

text: circuits

text: C

text: E.

text: e

text: e

text: E

text: Proof.

text: Any

text: solution

text: to

text: the

text: ﬁrst

text: two

text: sets

text: of

text: equations

text: is

text: of

text: the

text: form

text: for

text: some

text: B

text: E

text: with

text: B

text: |B|

text: r.

text: For

text: the

text: last

text: set

text: of

text: equations,

text: we

text: note

text: that

text: )C

text: for

text: all

text: circuits

text: C

text: if

text: and

text: only

text: if

text: B

text: B

text: does

text: not

text: contain

text: a

text: circuit.

text: This

text: is

text: equivalent

text: to

text: B

text: B.

text: Arguments

text: similar

text: to

text: those

text: used

text: in

text: the

text: proof

text: of

text: Proposition

text: show

text: that

text: the

text: polynomials

text: generate

text: a

text: real

text: radical

text: ideal.

text: Let

text: us

text: write

text: MGen

text: for

text: the

text: class

text: of

text: matroids

text: M

text: with

text: Gen(V

text: k.

text: The

text: previous

text: proposition

text: is

text: a

text: k

text: M

text: little

text: deceiving

text: in

text: the

text: sense

text: that

text: it

text: suggests

text: a

text: direct

text: connection

text: between

text: the

text: size

text: of

text: circuits

text: and

text: the

text: degree

text: of

text: generation.

text: This

text: is

text: not

text: quite

text: true.

text: Indeed,

text: let

text: G

text: K

text: \e

text: be

text: the

text: complete

text: graph

text: on

text: vertices

text: minus

text: an

text: edge.

text: Then

text: M(G)

text: has

text: a

text: circuit

text: of

text: cardinality

text: but

text: M(G)

text: MLev

text: MGen

text: by

text: Theorem

text: and

text: Proposition

text: The

text: main

text: result

text: of

text: this

text: section

text: is

text: that

text: for

text: base

text: conﬁgurations

text: the

text: condition

text: of

text: Proposition

text: is

text: also

text: suﬃcient.

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##


text: 16 FRANCESCO GRANDE AND RAMAN SANYAL A consequence of Theorem 3.9 is that a graph G is 2-level if and only if G does not have K as 4 a minor. In order to give a characterization of k-level graphs in terms of forbidden minors, we ﬁrst need to view K from a diﬀerent angle. 4 Deﬁnition 5.1. The cone over a graph G = (V, E) with apex w (cid:54)∈ V is the graph cone(G) = (V ∪ {w}, E ∪ {wv : v ∈ V }). Let us denote by C the n-cycle. Thus, we can view K as the cone over C . As in the previous n 4 3 section, we only need to consider graphic matroids M(G) which are connected. In terms of graph theory these correspond exactly to biconnected graphs. For a ﬂacet F let us denote by V ⊆ V the vertices covered by F . F Proposition 5.2. Let G = (V, E) be a biconnected graph and F ⊂ E a ﬂacet with |E\F | ≥ 2. Then G| is a vertex-induced subgraph. F Proof. By contradiction, suppose that e ∈ E\F is an edge with both endpoints in V . Since F F (cid:3) is a ﬂacet, G/F is a biconnected graph with loop e. This contradicts |E\F | ≥ 2. The deﬁnition of ﬂacets requires the graph G/F to be biconnected. This, in turn, implies that G| \ is connected. Let us write C(F ) := {uv ∈ E : u ∈ V , v (cid:54)∈ V } for the induced cut. E F F F (cid:48) Moreover, let us write F := E \ (F ∪ C(F )). The next result allows us to ﬁnd minors G of G (cid:48) with Lev(G ) = Lev(G). Lemma 5.3. Let G be a biconnected graph and F a k-level ﬂacet. Then F is a k-level ﬂacet of the graph G/F . Proof. Let H = G/F . It follows from the deﬁnition of ﬂacets, that G| is connected and thus F H/F = G/(F ∪F ) = U| | is biconnected. Moreover H| = G| is biconnected and therefore C(F) ,1 F F F is a ﬂacet of H. For the levelness of F , observe that it cannot be bigger than k. Let T ⊂ E be a spanning tree 1 such that the restriction to the connected graph G| \ is also a spanning tree. In particular, E F |T ∩ F | is minimal among all spanning trees. It now suﬃces to show that there is a sequence of 1 spanning trees T , T , . . . , T ⊂ E with |T ∩ F | = |T ∩ F | + i − 1 for all i = 1, . . . , k and such 1 2 k i 1 that T ∩ F = T ∩ F for all i, j. The contractions T /F then show that F is at least k-level for i j i H. If T ∩ F is not a spanning tree for G| , then pick e ∈ F \ T such that e connects two connected i F i components of (V , T ∩ F ). Since T is a spanning tree, there is a cycle in T ∪ e that uses at F i i i least one cut edge f ∈ C(F ) ∩ T . Hence T = (T \ e) ∪ f is the new spanning tree with the i i+1 i (cid:3) desired properties. The contraction of F in G gives a graph with vertices V ∪ {w}, where w results from the F contraction of F . Proposition 5.4. Let G = (V, E) be a simple, biconnected graph and let w be a vertex such that the set of edges F of G − w is a ﬂacet. Then F is k-level if and only if deg(w) = k. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FRANCESCO

text: GRANDE

text: AND

text: RAMAN

text: SANYAL

text: A

text: consequence

text: of

text: Theorem

text: is

text: that

text: a

text: graph

text: G

text: is

text: if

text: and

text: only

text: if

text: G

text: does

text: not

text: have

text: K

text: as

text: a

text: minor.

text: In

text: order

text: to

text: give

text: a

text: characterization

text: of

text: k-level

text: graphs

text: in

text: terms

text: of

text: forbidden

text: minors,

text: we

text: ﬁrst

text: need

text: to

text: view

text: K

text: from

text: a

text: diﬀerent

text: angle.

text: Deﬁnition

text: The

text: cone

text: over

text: a

text: graph

text: G

text: (V,

text: E)

text: with

text: apex

text: w

text: V

text: is

text: the

text: graph

text: cone(G)

text: (V

text: {w},

text: E

text: {wv

text: v

text: V

text: Let

text: us

text: denote

text: by

text: C

text: the

text: n-cycle.

text: Thus,

text: we

text: can

text: view

text: K

text: as

text: the

text: cone

text: over

text: C

text: As

text: in

text: the

text: previous

text: n

text: section,

text: we

text: only

text: need

text: to

text: consider

text: graphic

text: matroids

text: M(G)

text: which

text: are

text: connected.

text: In

text: terms

text: of

text: graph

text: theory

text: these

text: correspond

text: exactly

text: to

text: biconnected

text: graphs.

text: For

text: a

text: ﬂacet

text: F

text: let

text: us

text: denote

text: by

text: V

text: V

text: the

text: vertices

text: covered

text: by

text: F

text: F

text: Proposition

text: Let

text: G

text: (V,

text: E)

text: be

text: a

text: biconnected

text: graph

text: and

text: F

text: E

text: a

text: ﬂacet

text: with

text: |E\F

text: Then

text: G|

text: is

text: a

text: vertex-induced

text: subgraph.

text: F

text: Proof.

text: By

text: contradiction,

text: suppose

text: that

text: e

text: E\F

text: is

text: an

text: edge

text: with

text: both

text: endpoints

text: in

text: V

text: Since

text: F

text: F

text: is

text: a

text: ﬂacet,

text: G/F

text: is

text: a

text: biconnected

text: graph

text: with

text: loop

text: e.

text: This

text: contradicts

text: |E\F

text: The

text: deﬁnition

text: of

text: ﬂacets

text: requires

text: the

text: graph

text: G/F

text: to

text: be

text: biconnected.

text: This,

text: in

text: turn,

text: implies

text: that

text: G|

text: is

text: connected.

text: Let

text: us

text: write

text: C(F

text: {uv

text: E

text: u

text: V

text: v

text: V

text: for

text: the

text: induced

text: cut.

text: E

text: F

text: F

text: F

text: Moreover,

text: let

text: us

text: write

text: F

text: E

text: (F

text: C(F

text: The

text: next

text: result

text: allows

text: us

text: to

text: ﬁnd

text: minors

text: G

text: of

text: G

text: with

text: Lev(G

text: Lev(G).

text: Lemma

text: Let

text: G

text: be

text: a

text: biconnected

text: graph

text: and

text: F

text: a

text: k-level

text: ﬂacet.

text: Then

text: F

text: is

text: a

text: k-level

text: ﬂacet

text: of

text: the

text: graph

text: G/F

text: Proof.

text: Let

text: H

text: G/F

text: It

text: follows

text: from

text: the

text: deﬁnition

text: of

text: ﬂacets,

text: that

text: G|

text: is

text: connected

text: and

text: thus

text: F

text: H/F

text: G/(F

text: ∪F

text: U|

text: is

text: biconnected.

text: Moreover

text: H|

text: G|

text: is

text: biconnected

text: and

text: therefore

text: C(F)

text: F

text: F

text: F

text: is

text: a

text: ﬂacet

text: of

text: H.

text: For

text: the

text: levelness

text: of

text: F

text: observe

text: that

text: it

text: cannot

text: be

text: bigger

text: than

text: k.

text: Let

text: T

text: E

text: be

text: a

text: spanning

text: tree

text: such

text: that

text: the

text: restriction

text: to

text: the

text: connected

text: graph

text: G|

text: is

text: also

text: a

text: spanning

text: tree.

text: In

text: particular,

text: E

text: F

text: |T

text: F

text: is

text: minimal

text: among

text: all

text: spanning

text: trees.

text: It

text: now

text: suﬃces

text: to

text: show

text: that

text: there

text: is

text: a

text: sequence

text: of

text: spanning

text: trees

text: T

text: T

text: T

text: E

text: with

text: |T

text: F

text: |T

text: F

text: i

text: for

text: all

text: i

text: k

text: and

text: such

text: k

text: i

text: that

text: T

text: F

text: T

text: F

text: for

text: all

text: i,

text: j.

text: The

text: contractions

text: T

text: /F

text: then

text: show

text: that

text: F

text: is

text: at

text: least

text: k-level

text: for

text: i

text: j

text: i

text: H.

text: If

text: T

text: F

text: is

text: not

text: a

text: spanning

text: tree

text: for

text: G|

text: then

text: pick

text: e

text: F

text: T

text: such

text: that

text: e

text: connects

text: two

text: connected

text: i

text: F

text: i

text: components

text: of

text: (V

text: T

text: F

text: Since

text: T

text: is

text: a

text: spanning

text: tree,

text: there

text: is

text: a

text: cycle

text: in

text: T

text: e

text: that

text: uses

text: at

text: F

text: i

text: i

text: i

text: least

text: one

text: cut

text: edge

text: f

text: C(F

text: T

text: Hence

text: T

text: (T

text: e)

text: f

text: is

text: the

text: new

text: spanning

text: tree

text: with

text: the

text: i

text: i

text: desired

text: properties.

text: The

text: contraction

text: of

text: F

text: in

text: G

text: gives

text: a

text: graph

text: with

text: vertices

text: V

text: {w},

text: where

text: w

text: results

text: from

text: the

text: F

text: contraction

text: of

text: F

text: Proposition

text: Let

text: G

text: (V,

text: E)

text: be

text: a

text: simple,

text: biconnected

text: graph

text: and

text: let

text: w

text: be

text: a

text: vertex

text: such

text: that

text: the

text: set

text: of

text: edges

text: F

text: of

text: G

text: w

text: is

text: a

text: ﬂacet.

text: Then

text: F

text: is

text: k-level

text: if

text: and

text: only

text: if

text: deg(w)

text: k.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 24 FRANCESCO GRANDE AND RAMAN SANYAL [Die90] Reinhard Diestel, Graph decompositions. A study in inﬁnite graph theory, Oxford Science Publications, Oxford University Press, New York, 1990. [Dir67] Gabriel A. Dirac, Minimally 2-connected graphs, J. Reine Angew. Math. 228 (1967), 204–216. [Edm70] Jack Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), Gordon and Breach, New York, 1970, pp. 69–87. [FS05] Eva Maria Feichtner and Bernd Sturmfels, Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.) 62 (2005), no. 4, 437–468. [GLPT12] Joa˜o Gouveia, Monique Laurent, Pablo A. Parrilo, and Rekha Thomas, A new semideﬁnite program- ming hierarchy for cycles in binary matroids and cuts in graphs, Math. Program. 133 (2012), no. 1-2, Ser. A, 203–225. MR 2921097 [GPT10] Joa˜o Gouveia, Pablo A. Parrilo, and Rekha R. Thomas, Theta bodies for polynomial ideals, SIAM J. Optim. 20 (2010), no. 4, 2097–2118. [GPT13] , Lifts of convex sets and cone factorizations, Math. Oper. Res. 38 (2013), no. 2, 248–264. [GRT13] Joa˜o Gouveia, Richard Z. Robinson, and Rekha R. Thomas, Polytopes of minimum positive semideﬁnite rank, Discrete Comput. Geom. 50 (2013), no. 3, 679–699. [GS] Daniel R. Grayson and Michael E. Stillman, Macaulay2, a software system for research in algebraic geometry, Available at http://www.math.uiuc.edu/Macaulay2. [Kim10] Sangwook Kim, Flag enumerations of matroid base polytopes, J. Combin. Theory Ser. A 117 (2010), no. 7, 928–942. [McM76] Peter McMullen, Constructions for projectively unique polytopes, Discrete Math. 14 (1976), no. 4, 347–358. [Oxl89] James G. Oxley, The regular matroids with no 5-wheel minor, J. Combin. Theory Ser. B 46 (1989), no. 3, 292–305. [Oxl11] , Matroid theory, second ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. [Plu68] Michael D. Plummer, On minimal blocks, Trans. Amer. Math. Soc. 134 (1968), 85–94. [RS04] Neil Robertson and Paul D. Seymour, Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B 92 (2004), no. 2, 325–357. [SWZ09] Raman Sanyal, Axel Werner, and Gu¨nter M. Ziegler, On Kalai’s conjectures concerning centrally symmetric polytopes, Discrete Comput. Geom. 41 (2009), no. 2, 183–198. [Sch03] Alexander Schrijver, Combinatorial optimization. Polyhedra and eﬃciency. Vol. B, Algorithms and Combinatorics, vol. 24, Springer-Verlag, Berlin, 2003. [Sul06] Seth Sullivant, Compressed polytopes and statistical disclosure limitation, Tohoku Math. J. (2) 58 (2006), no. 3, 433–445. Fachbereich Mathematik und Informatik, Freie Universita¨t Berlin, Berlin, Germany { } Email address: fgrande,sanyal @math.fu-berlin.de ##LTLine## ##LTLine##

text: FRANCESCO

text: GRANDE

text: AND

text: RAMAN

text: SANYAL

label: reference

text: Reinhard

text: Diestel,

text: Graph

text: decompositions.

text: A

text: study

text: in

text: inﬁnite

text: graph

text: theory,

text: Oxford

text: Science

text: Publications,

text: Oxford

text: University

text: Press,

text: New

text: York,

text: Gabriel

text: A.

text: Dirac,

text: Minimally

text: graphs,

text: J.

text: Reine

text: Angew.

text: Math.

text: Jack

text: Edmonds,

text: Submodular

text: functions,

text: matroids,

text: and

text: certain

text: polyhedra,

text: Combinatorial

text: Structures

text: and

text: their

text: Applications

text: (Proc.

text: Calgary

text: Internat.

text: Conf.,

text: Calgary,

text: Alta.,

text: Gordon

text: and

text: Breach,

text: New

text: York,

text: pp.

text: Eva

text: Maria

text: Feichtner

text: and

text: Bernd

text: Sturmfels,

text: Matroid

text: polytopes,

text: nested

text: sets

text: and

text: Bergman

text: fans,

text: Port.

text: Math.

text: (N.S.)

text: no.

text: Joa˜o

text: Gouveia,

text: Monique

text: Laurent,

text: Pablo

text: A.

text: Parrilo,

text: and

text: Rekha

text: Thomas,

text: A

text: new

text: semideﬁnite

text: program-

text: ming

text: hierarchy

text: for

text: cycles

text: in

text: binary

text: matroids

text: and

text: cuts

text: in

text: graphs,

text: Math.

text: Program.

text: no.

text: Ser.

text: A,

text: MR

text: Joa˜o

text: Gouveia,

text: Pablo

text: A.

text: Parrilo,

text: and

text: Rekha

text: R.

text: Thomas,

text: Theta

text: bodies

text: for

text: polynomial

text: ideals,

text: SIAM

text: J.

text: Optim.

text: no.

text: Lifts

text: of

text: convex

text: sets

text: and

text: cone

text: factorizations,

text: Math.

text: Oper.

text: Res.

text: no.

text: Joa˜o

text: Gouveia,

text: Richard

text: Z.

text: Robinson,

text: and

text: Rekha

text: R.

text: Thomas,

text: Polytopes

text: of

text: minimum

text: positive

text: semideﬁnite

text: rank,

text: Discrete

text: Comput.

text: Geom.

text: no.

text: [GS]

text: Daniel

text: R.

text: Grayson

text: and

text: Michael

text: E.

text: Stillman,

text: a

text: software

text: system

text: for

text: research

text: in

text: algebraic

text: geometry,

text: Available

text: at

text: Sangwook

text: Kim,

text: Flag

text: enumerations

text: of

text: matroid

text: base

text: polytopes,

text: J.

text: Combin.

text: Theory

text: Ser.

text: A

text: no.

text: Peter

text: McMullen,

text: Constructions

text: for

text: projectively

text: unique

text: polytopes,

text: Discrete

text: Math.

text: no.

text: James

text: G.

text: Oxley,

text: The

text: regular

text: matroids

text: with

text: no

text: minor,

text: J.

text: Combin.

text: Theory

text: Ser.

text: B

text: no.

text: Matroid

text: theory,

text: second

text: ed.,

text: Oxford

text: Graduate

text: Texts

text: in

text: Mathematics,

text: vol.

text: Oxford

text: University

text: Press,

text: Oxford,

text: Michael

text: D.

text: Plummer,

text: On

text: minimal

text: blocks,

text: Trans.

text: Amer.

text: Math.

text: Soc.

text: Neil

text: Robertson

text: and

text: Paul

text: D.

text: Seymour,

text: Graph

text: minors.

text: XX.

text: Wagner’s

text: conjecture,

text: J.

text: Combin.

text: Theory

text: Ser.

text: B

text: no.

text: Raman

text: Sanyal,

text: Axel

text: Werner,

text: and

text: Gu¨nter

text: M.

text: Ziegler,

text: On

text: Kalai’s

text: conjectures

text: concerning

text: centrally

text: symmetric

text: polytopes,

text: Discrete

text: Comput.

text: Geom.

text: no.

text: Alexander

text: Schrijver,

text: Combinatorial

text: optimization.

text: Polyhedra

text: and

text: eﬃciency.

text: Vol.

text: B,

text: Algorithms

text: and

text: Combinatorics,

text: vol.

text: Springer-Verlag,

text: Berlin,

text: Seth

text: Sullivant,

text: Compressed

text: polytopes

text: and

text: statistical

text: disclosure

text: limitation,

text: Tohoku

text: Math.

text: J.

text: no.

text: Fachbereich

text: Mathematik

text: und

text: Informatik,

text: Freie

text: Universita¨t

text: Berlin,

text: Berlin,

text: Germany

text: Email

text: address:

text: fgrande,sanyal

text: @math.fu-berlin.de

text: ##LTLine##

text: ##LTLine##


text: 4 FRANCESCO GRANDE AND RAMAN SANYAL (cid:81) (cid:80) Proof. For a monomial xα, let τ = {i : α > 0} be its support. Over the set of 0/1-points it i follows that xα and xτ := ∈ x represent the same function. Hence, we can assume that f i τ i R is of the form f(x) = ⊆ c xτ for some c ∈ , τ ⊆ [n]. Moreover c∅ = f(0) (cid:54)= 0 and τ [n] τ τ (cid:48) without loss of generality we can assume c∅ = 1. A(cid:88)ny point v ∈ V is of the form v = 1 for σ ∅ some (cid:54)= σ ⊆ [n] and we calculate 0 = f(v) = c . τ ∅⊆ ⊆ τ σ It follows that c satisﬁes the deﬁning conditions of the M¨obius function of the Boolean lattice τ | | (cid:3) and hence equals c = (−1) τ for all τ ⊆ [n]. In particular c (cid:54)= 0 which ﬁnishes the proof. τ [n] We now introduce the combinatorial point conﬁgurations that are our main object of study. Matroids and their combinatorial theory are a vast subject and we refer the reader to the book by Oxley [Oxl11] for further information. (cid:0) (cid:1) Deﬁnition 2.5. A matroid of rank k is a pair M = (E, B) consisting of a ﬁnite ground set E ∅ and a collection of bases (cid:54)= B ⊆ E satisfying the basis exchange axiom: for B , B ∈ B and k 1 2 x ∈ B \ B there is y ∈ B \ B such that (B \ x) ∪ y ∈ B. 1 2 2 1 1 A set I ⊆ E is independent if I ⊆ B for some B ∈ B. The rank of X, denoted by rank (X), M is the cardinality of the largest independent subset contained in X. The circuits of M are the inclusion-minimal dependent subsets. An element e is called a loop if {e} is a circuit. We say that e, f ∈ E are parallel if {e, f} is a circuit. A parallel class H ⊆ E is the equivalence class of elements parallel to each other. The class H is non-trivial if |H| > 1. A matroid is simple if it does not contain loops or parallel elements. A ﬂat of a matroid is a set F ⊆ E such that rank(F ) < rank(F ∪ e) for all e ∈ E \ F . A particular class of matroids that we will consider are the graphic matroids. To a graph G = (V, E) we associate the matroid M(G) = (E, B). The bases are exactly the spanning forests of G. The running example for this section is the following. Example 1. Let G be the graph 4 2 3 1 The graphic matroid M = M(G) has ground set E = {1, 2, 3, 4}, rank(M) = 2, and bases B(G) = {12, 13, 14, 23, 24}. ∗ ∗ The dual matroid M of the matroid M = (E, B) is the matroid deﬁned by the pair (E, B ) ∗ ∗ where B = {E \B : B ∈ B}. A coloop of M is an element which is a loop of M . Equivalently it is an element which appears in every basis of M. If e ∈ E is not a coloop, we deﬁne the deletion as M \ e := (E \ e, {B ∈ B : e (cid:54)∈ B}). If e is a coloop, then the bases of M \ e are {B \ e : B ∈ B}. Dually, if e ∈ E is not a loop, we deﬁne the contraction as M/e := (E \ e, {B \ e : e ∈ B ∈ B}). These operations can be extended to subsets X ⊆ E and we write M \ X and M/X, respectively. We also deﬁne the restriction of ∗ ∗ M to a subset X ⊆ E as M| := M \ (E\X). Note that (M \ X) = M /X. A minor of M is X ##LTFigure## ##LTLine##

text: FRANCESCO

text: GRANDE

text: AND

text: RAMAN

text: SANYAL

text: Proof.

text: For

text: a

text: monomial

text: xα,

text: let

text: τ

text: {i

text: α

text: be

text: its

text: support.

text: Over

text: the

text: set

text: of

text: it

text: i

text: follows

text: that

text: xα

text: and

text: xτ

text: x

text: represent

text: the

text: same

text: function.

text: Hence,

text: we

text: can

text: assume

text: that

text: f

text: i

text: τ

text: i

text: R

text: is

text: of

text: the

text: form

text: f(x)

text: c

text: xτ

text: for

text: some

text: c

text: τ

text: [n].

text: Moreover

text: c∅

text: and

text: τ

text: [n]

text: τ

text: τ

text: without

text: loss

text: of

text: generality

text: we

text: can

text: assume

text: c∅

text: point

text: v

text: V

text: is

text: of

text: the

text: form

text: v

text: for

text: σ

text: some

text: σ

text: [n]

text: and

text: we

text: calculate

text: f(v)

text: c

text: τ

text: τ

text: σ

text: It

text: follows

text: that

text: c

text: satisﬁes

text: the

text: deﬁning

text: conditions

text: of

text: the

text: M¨obius

text: function

text: of

text: the

text: Boolean

text: lattice

text: τ

text: and

text: hence

text: equals

text: c

text: τ

text: for

text: all

text: τ

text: [n].

text: In

text: particular

text: c

text: which

text: ﬁnishes

text: the

text: proof.

text: τ

text: [n]

text: We

text: now

text: introduce

text: the

text: combinatorial

text: point

text: conﬁgurations

text: that

text: are

text: our

text: main

text: object

text: of

text: study.

text: Matroids

text: and

text: their

text: combinatorial

text: theory

text: are

text: a

text: vast

text: subject

text: and

text: we

text: refer

text: the

text: reader

text: to

text: the

text: book

text: by

text: Oxley

text: for

text: further

text: information.

text: Deﬁnition

text: A

text: matroid

text: of

text: rank

text: k

text: is

text: a

text: pair

text: M

text: (E,

text: B)

text: consisting

text: of

text: a

text: ﬁnite

text: ground

text: set

text: E

text: and

text: a

text: collection

text: of

text: bases

text: B

text: E

text: satisfying

text: the

text: basis

text: exchange

text: axiom:

text: for

text: B

text: B

text: B

text: and

text: k

text: x

text: B

text: B

text: there

text: is

text: y

text: B

text: B

text: such

text: that

text: (B

text: x)

text: y

text: B.

text: A

text: set

text: I

text: E

text: is

text: independent

text: if

text: I

text: B

text: for

text: some

text: B

text: B.

text: The

text: rank

text: of

text: X,

text: denoted

text: by

text: rank

text: (X),

text: M

text: is

text: the

text: cardinality

text: of

text: the

text: largest

text: independent

text: subset

text: contained

text: in

text: X.

text: The

text: circuits

text: of

text: M

text: are

text: the

text: inclusion-minimal

text: dependent

text: subsets.

text: An

text: element

text: e

text: is

text: called

text: a

text: loop

text: if

text: {e}

text: is

text: a

text: circuit.

text: We

text: say

text: that

text: e,

text: f

text: E

text: are

text: parallel

text: if

text: {e,

text: f}

text: is

text: a

text: circuit.

text: A

text: parallel

text: class

text: H

text: E

text: is

text: the

text: equivalence

text: class

text: of

text: elements

text: parallel

text: to

text: each

text: other.

text: The

text: class

text: H

text: is

text: non-trivial

text: if

text: |H|

text: A

text: matroid

text: is

text: simple

text: if

text: it

text: does

text: not

text: contain

text: loops

text: or

text: parallel

text: elements.

text: A

text: ﬂat

text: of

text: a

text: matroid

text: is

text: a

text: set

text: F

text: E

text: such

text: that

text: rank(F

text: rank(F

text: e)

text: for

text: all

text: e

text: E

text: F

text: A

text: particular

text: class

text: of

text: matroids

text: that

text: we

text: will

text: consider

text: are

text: the

text: graphic

text: matroids.

text: To

text: a

text: graph

text: G

text: (V,

text: E)

text: we

text: associate

text: the

text: matroid

text: M(G)

text: (E,

text: B).

text: The

text: bases

text: are

text: exactly

text: the

text: spanning

text: forests

text: of

text: G.

text: The

text: running

text: example

text: for

text: this

text: section

text: is

text: the

text: following.

text: Example

text: Let

text: G

text: be

text: the

text: graph

text: The

text: graphic

text: matroid

text: M

text: M(G)

text: has

text: ground

text: set

text: E

text: rank(M)

text: and

text: bases

text: B(G)

text: The

text: dual

text: matroid

text: M

text: of

text: the

text: matroid

text: M

text: (E,

text: B)

text: is

text: the

text: matroid

text: deﬁned

text: by

text: the

text: pair

text: (E,

text: B

text: where

text: B

text: {E

text: \B

text: B

text: B}.

text: A

text: coloop

text: of

text: M

text: is

text: an

text: element

text: which

text: is

text: a

text: loop

text: of

text: M

text: Equivalently

text: it

text: is

text: an

text: element

text: which

text: appears

text: in

text: every

text: basis

text: of

text: M.

text: If

text: e

text: E

text: is

text: not

text: a

text: coloop,

text: we

text: deﬁne

text: the

text: deletion

text: as

text: M

text: e

text: (E

text: e,

text: {B

text: B

text: e

text: B}).

text: If

text: e

text: is

text: a

text: coloop,

text: then

text: the

text: bases

text: of

text: M

text: e

text: are

text: {B

text: e

text: B

text: B}.

text: Dually,

text: if

text: e

text: E

text: is

text: not

text: a

text: loop,

text: we

text: deﬁne

text: the

text: contraction

text: as

text: M/e

text: (E

text: e,

text: {B

text: e

text: e

text: B

text: B}).

text: These

text: operations

text: can

text: be

text: extended

text: to

text: subsets

text: X

text: E

text: and

text: we

text: write

text: M

text: X

text: and

text: M/X,

text: respectively.

text: We

text: also

text: deﬁne

text: the

text: restriction

text: of

text: M

text: to

text: a

text: subset

text: X

text: E

text: as

text: M|

text: M

text: (E\X).

text: Note

text: that

text: (M

text: X)

text: M

text: /X.

text: A

text: minor

text: of

text: M

text: is

text: X

text: ##LTFigure##

text: ##LTLine##


text: 6 FRANCESCO GRANDE AND RAMAN SANYAL (1,1,0,0) 3 2 ⊕ 4 1 (0,1,1,0) (0,1,0,1) 2 4 ⊕ (1,0,1,0) (1,0,0,1) 1 3 The 5 bases correspond to the vertices of P . We considered the subset {3, 4} whose associated M face M(G) |{ } × M(G) /{3, 4} is the quadrilateral facet of the polytope, and the subset {1, 2} 3,4 whose associated face M(G) |{ } × M(G) /{1, 2} is the vertex (1, 1, 0, 0). 1,2 We deﬁne the following families of matroids: MLev := {M matroid : Lev(V ) ≤ k}, and k M MTh := {M matroid : Th(V ) ≤ k}. k M We will say that a matroid M is of Theta rank or level k if the corresponding base conﬁguration V is. Now combining Proposition 2.8 with Lemma 2.3 proves the main theorem of this section. M Theorem 2.9. The classes MTh and MLev are closed under taking minors. k k Proof. Using Proposition 2.8 repeatedly on one-element sets shows that for every minor N of M there is a supporting hyperplane such that V ∩ H is aﬃnely isomorphic to V . Lemma 2.3 M N (cid:3) assures us that Th(V ) ≤ Th(V ). N M Let us analogously deﬁne the classes GTh and GLev of graphic matroids of Theta rank and levelness k k bounded by k. These are also closed under taking minors and the Robertson–Seymour’s theorem ([RS04]) asserts that there is a ﬁnite list of excluded minors characterizing each class. In the remainder of the section we will recall the facet-deﬁning hyperplanes of V which will M also show that all faces of V correspond to direct sums of minors. The facial structure of V M M has been of interest originally in combinatorial optimization [Edm70] (see also [Sch03, Ch. 40]) and later in geometric combinatorics and tropical geometry [AK06, FS05, Kim10]. Theorem 2.10. Let M = (E, B) be a connected matroid. For every facet U ⊂ V there is a M ∅ ∅ unique (cid:54)= S ⊂ E such that U = V ∩ H (S). Conversely, a subset (cid:54)= S ⊂ E gives rise to M M a facet if and only if (i) S is a ﬂat such that M| as well as M/S are connected; S (ii) S = E \ e for some e ∈ E such that M| as well as M/S are connected. S In [FS05] the subsets S in (i) were called ﬂacets and we stick to this name. In our study of the Theta rank and the levelness of base conﬁgurations, the following asserts that we will only need to consider ﬂacets. For brevity, a k-level ﬂacet refers to a ﬂacet whose corresponding facet is k-level. Proposition 2.11. Let M be a connected matroid and S = E \ e. Then (cid:96) (x) takes 2 values S on V and hence is 1-sos. M ##LTFigure## ##LTLine## ##LTLine## ##LTLine##

text: FRANCESCO

text: GRANDE

text: AND

text: RAMAN

text: SANYAL

font: default

text: The

text: bases

text: correspond

text: to

text: the

text: vertices

text: of

text: P

text: We

text: considered

text: the

text: subset

text: whose

text: associated

text: M

text: face

text: M(G)

text: M(G)

text: is

text: the

text: quadrilateral

text: facet

text: of

text: the

text: polytope,

text: and

text: the

text: subset

text: whose

text: associated

text: face

text: M(G)

text: M(G)

text: is

text: the

text: vertex

text: We

text: deﬁne

text: the

text: following

text: families

text: of

text: matroids:

text: MLev

text: {M

text: matroid

text: Lev(V

text: k},

text: and

text: k

text: M

text: MTh

text: {M

text: matroid

text: Th(V

text: k}.

text: k

text: M

text: We

text: will

text: say

text: that

text: a

text: matroid

text: M

text: is

text: of

text: Theta

text: rank

text: or

text: level

text: k

text: if

text: the

text: corresponding

text: base

text: conﬁguration

text: V

text: is.

text: Now

text: combining

text: Proposition

text: with

text: Lemma

text: proves

text: the

text: main

text: theorem

text: of

text: this

text: section.

text: M

text: Theorem

text: The

text: classes

text: MTh

text: and

text: MLev

text: are

text: closed

text: under

text: taking

text: minors.

text: k

text: k

text: Proof.

text: Using

text: Proposition

text: repeatedly

text: on

text: one-element

text: sets

text: shows

text: that

text: for

text: every

text: minor

text: N

text: of

text: M

text: there

text: is

text: a

text: supporting

text: hyperplane

text: such

text: that

text: V

text: H

text: is

text: aﬃnely

text: isomorphic

text: to

text: V

text: Lemma

text: M

text: N

text: assures

text: us

text: that

text: Th(V

text: Th(V

text: N

text: M

text: Let

text: us

text: analogously

text: deﬁne

text: the

text: classes

text: GTh

text: and

text: GLev

text: of

text: graphic

text: matroids

text: of

text: Theta

text: rank

text: and

text: levelness

text: k

text: k

text: bounded

text: by

text: k.

text: These

text: are

text: also

text: closed

text: under

text: taking

text: minors

text: and

text: the

text: Robertson–Seymour’s

text: theorem

text: asserts

text: that

text: there

text: is

text: a

text: ﬁnite

text: list

text: of

text: excluded

text: minors

text: characterizing

text: each

text: class.

text: In

text: the

text: remainder

text: of

text: the

text: section

text: we

text: will

text: recall

text: the

text: facet-deﬁning

text: hyperplanes

text: of

text: V

text: which

text: will

text: M

text: also

text: show

text: that

text: all

text: faces

text: of

text: V

text: correspond

text: to

text: direct

text: sums

text: of

text: minors.

text: The

text: facial

text: structure

text: of

text: V

text: M

text: M

text: has

text: been

text: of

text: interest

text: originally

text: in

text: combinatorial

text: optimization

text: (see

text: also

text: Ch.

text: and

text: later

text: in

text: geometric

text: combinatorics

text: and

text: tropical

text: geometry

text: Theorem

text: Let

text: M

text: (E,

text: B)

text: be

text: a

text: connected

text: matroid.

text: For

text: every

text: facet

text: U

text: V

text: there

text: is

text: a

text: M

text: unique

text: S

text: E

text: such

text: that

text: U

text: V

text: H

text: (S).

text: Conversely,

text: a

text: subset

text: S

text: E

text: gives

text: rise

text: to

text: M

text: M

text: a

text: facet

text: if

text: and

text: only

text: if

text: (i)

text: S

text: is

text: a

text: ﬂat

text: such

text: that

text: M|

text: as

text: well

text: as

text: M/S

text: are

text: connected;

text: S

text: (ii)

text: S

text: E

text: e

text: for

text: some

text: e

text: E

text: such

text: that

text: M|

text: as

text: well

text: as

text: M/S

text: are

text: connected.

text: S

text: In

text: the

text: subsets

text: S

text: in

text: (i)

text: were

text: called

text: ﬂacets

text: and

text: we

text: stick

text: to

text: this

text: name.

text: In

text: our

text: study

text: of

text: the

text: Theta

text: rank

text: and

text: the

text: levelness

text: of

text: base

text: conﬁgurations,

text: the

text: following

text: asserts

text: that

text: we

text: will

text: only

text: need

text: to

text: consider

text: ﬂacets.

text: For

text: brevity,

text: a

text: k-level

text: ﬂacet

text: refers

text: to

text: a

text: ﬂacet

text: whose

text: corresponding

text: facet

text: is

text: k-level.

text: Proposition

text: Let

text: M

text: be

text: a

text: connected

text: matroid

text: and

text: S

text: E

text: e.

text: Then

text: (x)

text: takes

text: values

text: S

text: on

text: V

text: and

text: hence

text: is

text: M

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 2 ] m a) R PHENIX Data hydro model f [ side e 5 Au Au 200GeV Au Au 200GeV d d Au 200GeV d Au 200GeV si R STAR Data Au Au 200GeV STAR Preliminary d Au 200GeV 0 ] b) R c) R m out long f [ g 5 n o Rl , ut o R 0 0 5 0 5 N1/3 N1/3 part part FIG. 1. The HBT radii R (panel a)), R (panel b)), and R (panel c)) for d-Au and Au-Au collisions at 200GeV for side out long diﬀerent centralities (plotted as function of N1/3 ). The experimental data of the PHENIX collaboration are represented using part circles (Au-Au) [16] and up-triangles (d-Au) [5], the Au-Au data of the STAR collaboration using open squares [17], and the preliminary d-Au data of the STAR collaboration using crosses [18]. The results of the hydrodynamic model are shown using diamonds (d-Au) and solid squares (Au-Au [19]). formula and no corrections for such interactions are per- given centrality class, for 350MeV< k⊥ < 450MeV. The formed when ﬁtting the Gaussian formula to the corre- calculation reproduces rather well the experimental data lation function. The correlation function is constructed of the PHENIX collaboration for d-Au collisions. The in the longitudinal comoving system for pion pairs with preliminary STAR collaboration results for R in d-Au | | o rapidity y < 1. The details of the procedure for the are below the PHENIX results. The systematic uncer- hydrodynamic evolution and for the construction of the tainty of the ﬁtted results for the hydrodynamic calcu- HBT correlation function in the event-by-event hydrody- lation is estimated by varying the range of the ﬁt from | | namic model can be found in [2, 19]. q < 0.1GeV to 0.2GeV, the variation of the extracted In a given average transverse pair momentum k⊥ bin, radii is smaller than 10%. the dependence of the correlation function C(q, k⊥) on the relative momentum q is decomposed into three com- ponents, ql along the beam axis, qo along the pair trans- The calculated radii for Au-Au collisions are system- verse momentum k⊥ in the local comoving system, and qs atically below the experimental values. The deviation orthogonal to the ﬁrst two directions. The Bertsch-Pratt is not reduced by lowering the freeze-out temperature to formula is ﬁtted in 3-dimensions 140MeV. The result shows that the hydrodynamic model can describe only partly the dependence of the HBT radii C(q, k⊥) = 1 + λe−Ro2qo2−Rs2qs2−Rl2ql2 , (2.2) on the system size and the centrality of the collisions. It may indicate that the ﬂow proﬁle generated in the hy- drodynamic simulation with Glauber model initial con- where the extracted parameters R are the three ditions is only approximate or that contributions of the o,s,l HBT radii [20]. pre-equilibrium ﬂow or rescattering stage are noticeable In Fig. 1 is shown the dependence of the HBT radii [21]. Other eﬀects could be also be important for the on the average number of participant nucleons for the interferometry in small systems [22]. ##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## ##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## ##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## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: m

text: a)

text: R

text: PHENIX

text: Data

text: hydro

text: model

text: f

text: side

text: e

text: Au

text: Au

text: Au

text: Au

text: d

text: d

text: Au

text: d

text: Au

text: si

text: R

text: STAR

text: Data

text: Au

text: Au

text: STAR

text: Preliminary

text: d

text: Au

text: b)

text: R

text: c)

text: R

text: m

text: out

text: long

text: f

text: g

text: n

text: o

text: Rl

text: ut

text: o

text: R

text: part

text: part

text: FIG.

text: The

text: HBT

text: radii

text: R

text: (panel

text: a)),

text: R

text: (panel

text: b)),

text: and

text: R

text: (panel

text: c))

text: for

text: d-Au

text: and

text: Au-Au

text: collisions

text: at

text: for

text: side

text: out

text: long

text: diﬀerent

text: centralities

text: (plotted

text: as

text: function

text: of

text: The

text: experimental

text: data

text: of

text: the

text: PHENIX

text: collaboration

text: are

text: represented

text: using

text: part

text: circles

text: (Au-Au)

text: and

text: up-triangles

text: (d-Au)

text: the

text: Au-Au

text: data

text: of

text: the

text: STAR

text: collaboration

text: using

text: open

text: squares

text: and

text: the

text: preliminary

text: d-Au

text: data

text: of

text: the

text: STAR

text: collaboration

text: using

text: crosses

text: The

text: results

text: of

text: the

text: hydrodynamic

text: model

text: are

text: shown

text: using

text: diamonds

text: (d-Au)

text: and

text: solid

text: squares

text: (Au-Au

text: formula

text: and

text: no

text: corrections

text: for

text: such

text: interactions

text: are

text: per-

text: given

text: centrality

text: class,

text: for

text: k⊥

text: The

text: formed

text: when

text: ﬁtting

text: the

text: Gaussian

text: formula

text: to

text: the

text: corre-

text: calculation

text: reproduces

text: rather

text: well

text: the

text: experimental

text: data

text: lation

text: function.

text: The

text: correlation

text: function

text: is

text: constructed

text: of

text: the

text: PHENIX

text: collaboration

text: for

text: d-Au

text: collisions.

text: The

text: in

text: the

text: longitudinal

text: comoving

text: system

text: for

text: pion

text: pairs

text: with

text: preliminary

text: STAR

text: collaboration

text: results

text: for

text: R

text: in

text: d-Au

text: o

text: rapidity

text: y

text: The

text: details

text: of

text: the

text: procedure

text: for

text: the

text: are

text: below

text: the

text: PHENIX

text: results.

text: The

text: systematic

text: uncer-

text: hydrodynamic

text: evolution

text: and

text: for

text: the

text: construction

text: of

text: the

text: tainty

text: of

text: the

text: ﬁtted

text: results

text: for

text: the

text: hydrodynamic

text: calcu-

text: HBT

text: correlation

text: function

text: in

text: the

text: event-by-event

text: hydrody-

text: lation

text: is

text: estimated

text: by

text: varying

text: the

text: range

text: of

text: the

text: ﬁt

text: from

text: namic

text: model

text: can

text: be

text: found

text: in

text: q

text: to

text: the

text: variation

text: of

text: the

text: extracted

text: In

text: a

text: given

text: average

text: transverse

text: pair

text: momentum

text: k⊥

text: bin,

text: radii

text: is

text: smaller

text: than

text: the

text: dependence

text: of

text: the

text: correlation

text: function

text: C(q,

text: k⊥)

text: on

text: the

text: relative

text: momentum

text: q

text: is

text: decomposed

text: into

text: three

text: com-

text: ponents,

text: ql

text: along

text: the

text: beam

text: axis,

text: qo

text: along

text: the

text: pair

text: trans-

text: The

text: calculated

text: radii

text: for

text: Au-Au

text: collisions

text: are

text: system-

text: verse

text: momentum

text: k⊥

text: in

text: the

text: local

text: comoving

text: system,

text: and

text: qs

text: atically

text: below

text: the

text: experimental

text: values.

text: The

text: deviation

text: orthogonal

text: to

text: the

text: ﬁrst

text: two

text: directions.

text: The

text: Bertsch-Pratt

text: is

text: not

text: reduced

text: by

text: lowering

text: the

text: freeze-out

text: temperature

text: to

text: formula

text: is

text: ﬁtted

text: in

text: The

text: result

text: shows

text: that

text: the

text: hydrodynamic

text: model

text: can

text: describe

text: only

text: partly

text: the

text: dependence

text: of

text: the

text: HBT

text: radii

text: C(q,

text: k⊥)

text: on

text: the

text: system

text: size

text: and

text: the

text: centrality

text: of

text: the

text: collisions.

text: It

text: may

text: indicate

text: that

text: the

text: ﬂow

text: proﬁle

text: generated

text: in

text: the

text: hy-

text: drodynamic

text: simulation

text: with

text: Glauber

text: model

text: initial

text: con-

text: where

text: the

text: extracted

text: parameters

text: R

text: are

text: the

text: three

text: ditions

text: is

text: only

text: approximate

text: or

text: that

text: contributions

text: of

text: the

text: o,s,l

text: HBT

text: radii

text: pre-equilibrium

text: ﬂow

text: or

text: rescattering

text: stage

text: are

text: noticeable

text: In

text: Fig.

text: is

text: shown

text: the

text: dependence

text: of

text: the

text: HBT

text: radii

text: Other

text: eﬀects

text: could

text: be

text: also

text: be

text: important

text: for

text: the

text: on

text: the

text: average

text: number

text: of

text: participant

text: nucleons

text: for

text: the

text: interferometry

text: in

text: small

text: systems

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##

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##

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##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Generation and detection of a sub-Poissonian atom number distribution ∗ in a one-dimensional optical lattice † † J.-B. B´eguin, E. M. Bookjans, S. L. Christensen, H. L. Sørensen, J. H. Mu¨ller, J. Appel, and E. S. Polzik ‡ § (Dated: May 26, 2020) We demonstrate preparation and detection of an atom number distribution in a one-dimensional − atomic lattice with the variance 14 dB below the Poissonian noise level. A mesoscopic ensemble containing a few thousand atoms is trapped in the evanescent ﬁeld of a nanoﬁber. The atom number is measured through dual-color homodyne interferometry with a pW-power shot noise limited probe. Strong coupling of the evanescent probe guided by the nanoﬁber allows for a real-time measurement ± with a precision of 8 atoms on an ensemble of some 103 atoms in a one-dimensional trap. The method is very well suited for generating collective atomic entangled or spin-squeezed states via a quantum non-demolition measurement as well as for tomography of exotic atomic states in a one-dimensional lattice. PACS numbers: 42.50.Ct, 37.10.Jk, 42.50.Ex Keywords: Quantum Optics, Fano factor, Nanoﬁber, QND measurement Atoms trapped in an optical lattice are a well-pursued quantum gate implementations based on collective Ry- platform for the realization of a quantum simulator and dberg excitations [52, 53] or atomic Bragg mirrors [54]. quantum information processing devices [37]. In addi- For these and other applications it is desirable to have a tion, mesoscopic ensembles of periodically well-separated probing and preparation method at hand which not only atoms strongly coupled to light are an excellent arrange- is minimally-destructive but also widely tunable in band- ment for quantum metrology and sensing applications width. Ideally, it should enable monitoring dynamics on using collective atomic state entanglement [38]. diﬀerent timescales and to outrun the inﬂuence of any decoherence not caused by the measurement itself. While The recent spectacular progress with cold atoms trapped impressive atom number resolution has been reported for in the evanescent ﬁeld emanating from a tapered opti- atomic ensembles inhomogeneously coupled to an opti- cal nanoﬁber with a sub-wavelength diameter [39–42] cal cavity mode [55] and for ensembles trapped inside oﬀers a realistic and promising implementation of a one- a low-noise magneto-optical trap [56], we demonstrate dimensional (1D) optical lattice eﬃciently coupled to a a fast single-pass atom number measurement method single well-deﬁned light mode. Together with the ma- that is readily adapted to diﬀerent measurement and ture technology of interconnecting optical ﬁbers, atomic preparation tasks in 1D ensembles. ensembles trapped around nanoﬁbers have the potential to play an integral part in the construction of complex In this work, we realize the ﬁrst real-time, minimally- quantum networks. Photons propagating in a ﬁber con- destructive detection of atoms with sub-Poissonian sen- nect hybrid quantum systems by interacting with various sitivity in a 1D nanoﬁber lattice trap. Due to the guid- realizations of quantum systems, such as solid state sys- ing of the probe light by the nanoﬁber, the optical depth tems and atoms, through strong light-matter coupling at N σ/A achieves maximal values for a given atom number at nano-tapered ﬁber nodes [43, 44]. N as the light beam cross section A becomes compara- at An eﬃcient quantum interface between light and col- ble to the atomic cross section. The minimally destruc- lective degrees of freedom of an atomic ensemble re- tive measurement is achieved by balancing the phase in- quires a high optical depth and a measurement sensitiv- formation obtained from atoms against the measurement ity limited by the shot noise of light and the projection back action, combined with quantum noise limited sen- noise of atoms [45]. Under these conditions a quantum sitivity for both probe photons and atoms. Through a non-demolition (QND) measurement of atomic popu- continuous shot noise limited measurement of the atom lation diﬀerences has been used for the generation of induced phase shift of light, we resolve and prepare an spin squeezed [46], entangled states to improve atomic atom number distribution of the ensemble with a min- − clocks [47, 48] and magnetometers [49, 50]. In addition, imum Fano factor (∆N )2/N of 14 dB. The reduc- at at optical probing of atoms in one-dimensional lattices with tion of the atom number noise compared to the Poisson sub-Poissonan precision has been proposed as a valuable distribution is ultimately limited only by probe induced measurement tool for strongly correlated systems [51]. stochastic loss of atoms [57–59]. The absolute number The preparation of ensembles with narrow atom num- of atoms in the lattice trap is calibrated accurately via ber distribution in atom traps and the knowledge of its a robust experimental method based on optical pump- statistics in real-time is also a well-recognized goal for ing [60]. Finally, we show that the achieved light-atom

text: Generation

label: title

text: and

text: detection

text: of

text: a

text: sub-Poissonian

text: atom

text: number

text: distribution

text: in

text: a

text: one-dimensional

text: optical

text: lattice

text: J.-B.

label: author

text: B´eguin,

text: E.

text: M.

text: Bookjans,

text: S.

text: L.

text: Christensen,

text: H.

text: L.

text: Sørensen,

text: J.

text: H.

text: Mu¨ller,

text: J.

text: Appel,

text: and

text: E.

text: S.

text: Polzik

text: (Dated:

text: May

label: date

text: We

label: abstract

text: demonstrate

text: preparation

text: and

text: detection

text: of

text: an

text: atom

text: number

text: distribution

text: in

text: a

text: one-dimensional

text: atomic

text: lattice

text: with

text: the

text: variance

text: dB

text: below

text: the

text: Poissonian

text: noise

text: level.

text: A

text: mesoscopic

text: ensemble

text: containing

text: a

text: few

text: thousand

text: atoms

text: is

text: trapped

text: in

text: the

text: evanescent

text: ﬁeld

text: of

text: a

text: nanoﬁber.

text: The

text: atom

text: number

text: is

text: measured

text: through

text: dual-color

text: homodyne

text: interferometry

text: with

text: a

text: pW-power

text: shot

text: noise

text: limited

text: probe.

text: Strong

text: coupling

text: of

text: the

text: evanescent

text: probe

text: guided

text: by

text: the

text: nanoﬁber

text: allows

text: for

text: a

text: real-time

text: measurement

text: with

text: a

text: precision

text: of

text: atoms

text: on

text: an

text: ensemble

text: of

text: some

text: atoms

text: in

text: a

text: one-dimensional

text: trap.

text: The

text: method

text: is

text: very

text: well

text: suited

text: for

text: generating

text: collective

text: atomic

text: entangled

text: or

text: spin-squeezed

text: states

text: via

text: a

text: quantum

text: non-demolition

text: measurement

text: as

text: well

text: as

text: for

text: tomography

text: of

text: exotic

text: atomic

text: states

text: in

text: a

text: one-dimensional

text: lattice.

text: PACS

text: numbers:

text: Keywords:

text: Quantum

text: Optics,

text: Fano

text: factor,

text: Nanoﬁber,

text: QND

text: measurement

text: Atoms

text: trapped

text: in

text: an

text: optical

text: lattice

text: are

text: a

text: well-pursued

text: quantum

text: gate

text: implementations

text: based

text: on

text: collective

text: Ry-

text: platform

text: for

text: the

text: realization

text: of

text: a

text: quantum

text: simulator

text: and

text: dberg

text: excitations

text: or

text: atomic

text: Bragg

text: mirrors

text: quantum

text: information

text: processing

text: devices

text: In

text: addi-

text: For

text: these

text: and

text: other

text: applications

text: it

text: is

text: desirable

text: to

text: have

text: a

text: tion,

text: mesoscopic

text: ensembles

text: of

text: periodically

text: well-separated

text: probing

text: and

text: preparation

text: method

text: at

text: hand

text: which

text: not

text: only

text: atoms

text: strongly

text: coupled

text: to

text: light

text: are

text: an

text: excellent

text: arrange-

text: is

text: minimally-destructive

text: but

text: also

text: widely

text: tunable

text: in

text: band-

text: ment

text: for

text: quantum

text: metrology

text: and

text: sensing

text: applications

text: width.

text: Ideally,

text: it

text: should

text: enable

text: monitoring

text: dynamics

text: on

text: using

text: collective

text: atomic

text: state

text: entanglement

text: diﬀerent

text: timescales

text: and

text: to

text: outrun

text: the

text: inﬂuence

text: of

text: any

text: decoherence

text: not

text: caused

text: by

text: the

text: measurement

text: itself.

text: While

text: The

text: recent

text: spectacular

text: progress

text: with

text: cold

text: atoms

text: trapped

text: impressive

text: atom

text: number

text: resolution

text: has

text: been

text: reported

text: for

text: in

text: the

text: evanescent

text: ﬁeld

text: emanating

text: from

text: a

text: tapered

text: opti-

text: atomic

text: ensembles

text: inhomogeneously

text: coupled

text: to

text: an

text: opti-

text: cal

text: nanoﬁber

text: with

text: a

text: sub-wavelength

text: diameter

text: cal

text: cavity

text: mode

text: and

text: for

text: ensembles

text: trapped

text: inside

text: oﬀers

text: a

text: realistic

text: and

text: promising

text: implementation

text: of

text: a

text: one-

text: a

text: low-noise

text: magneto-optical

text: trap

text: we

text: demonstrate

text: dimensional

text: optical

text: lattice

text: eﬃciently

text: coupled

text: to

text: a

text: a

text: fast

text: single-pass

text: atom

text: number

text: measurement

text: method

text: single

text: well-deﬁned

text: light

text: mode.

text: Together

text: with

text: the

text: ma-

text: that

text: is

text: readily

text: adapted

text: to

text: diﬀerent

text: measurement

text: and

text: ture

text: technology

text: of

text: interconnecting

text: optical

text: ﬁbers,

text: atomic

text: preparation

text: tasks

text: in

text: ensembles.

text: ensembles

text: trapped

text: around

text: nanoﬁbers

text: have

text: the

text: potential

text: to

text: play

text: an

text: integral

text: part

text: in

text: the

text: construction

text: of

text: complex

text: In

text: this

text: work,

text: we

text: realize

text: the

text: ﬁrst

text: real-time,

text: minimally-

text: quantum

text: networks.

text: Photons

text: propagating

text: in

text: a

text: ﬁber

text: con-

text: destructive

text: detection

text: of

text: atoms

text: with

text: sub-Poissonian

text: sen-

text: nect

text: hybrid

text: quantum

text: systems

text: by

text: interacting

text: with

text: various

text: sitivity

text: in

text: a

text: nanoﬁber

text: lattice

text: trap.

text: Due

text: to

text: the

text: guid-

text: realizations

text: of

text: quantum

text: systems,

text: such

text: as

text: solid

text: state

text: sys-

text: ing

text: of

text: the

text: probe

text: light

text: by

text: the

text: nanoﬁber,

text: the

text: optical

text: depth

text: tems

text: and

text: atoms,

text: through

text: strong

text: light-matter

text: coupling

text: at

text: N

text: σ/A

text: achieves

text: maximal

text: values

text: for

text: a

text: given

text: atom

text: number

text: at

text: nano-tapered

text: ﬁber

text: nodes

text: N

text: as

text: the

text: light

text: beam

text: cross

text: section

text: A

text: becomes

text: compara-

text: at

text: An

text: eﬃcient

text: quantum

text: interface

text: between

text: light

text: and

text: col-

text: ble

text: to

text: the

text: atomic

text: cross

text: section.

text: The

text: minimally

text: destruc-

text: lective

text: degrees

text: of

text: freedom

text: of

text: an

text: atomic

text: ensemble

text: re-

text: tive

text: measurement

text: is

text: achieved

text: by

text: balancing

text: the

text: phase

text: in-

text: quires

text: a

text: high

text: optical

text: depth

text: and

text: a

text: measurement

text: sensitiv-

text: formation

text: obtained

text: from

text: atoms

text: against

text: the

text: measurement

text: ity

text: limited

text: by

text: the

text: shot

text: noise

text: of

text: light

text: and

text: the

text: projection

text: back

text: action,

text: combined

text: with

text: quantum

text: noise

text: limited

text: sen-

text: noise

text: of

text: atoms

text: Under

text: these

text: conditions

text: a

text: quantum

text: sitivity

text: for

text: both

text: probe

text: photons

text: and

text: atoms.

text: Through

text: a

text: non-demolition

text: (QND)

text: measurement

text: of

text: atomic

text: popu-

text: continuous

text: shot

text: noise

text: limited

text: measurement

text: of

text: the

text: atom

text: lation

text: diﬀerences

text: has

text: been

text: used

text: for

text: the

text: generation

text: of

text: induced

text: phase

text: shift

text: of

text: light,

text: we

text: resolve

text: and

text: prepare

text: an

text: spin

text: squeezed

text: entangled

text: states

text: to

text: improve

text: atomic

text: atom

text: number

text: distribution

text: of

text: the

text: ensemble

text: with

text: a

text: min-

text: clocks

text: and

text: magnetometers

text: In

text: addition,

text: imum

text: Fano

text: factor

text: (∆N

text: of

text: dB.

text: The

text: reduc-

text: at

text: at

text: optical

text: probing

text: of

text: atoms

text: in

text: one-dimensional

text: lattices

text: with

text: tion

text: of

text: the

text: atom

text: number

text: noise

text: compared

text: to

text: the

text: Poisson

text: sub-Poissonan

text: precision

text: has

text: been

text: proposed

text: as

text: a

text: valuable

text: distribution

text: is

text: ultimately

text: limited

text: only

text: by

text: probe

text: induced

text: measurement

text: tool

text: for

text: strongly

text: correlated

text: systems

text: stochastic

text: loss

text: of

text: atoms

text: The

text: absolute

text: number

text: The

text: preparation

text: of

text: ensembles

text: with

text: narrow

text: atom

text: num-

text: of

text: atoms

text: in

text: the

text: lattice

text: trap

text: is

text: calibrated

text: accurately

text: via

text: ber

text: distribution

text: in

text: atom

text: traps

text: and

text: the

text: knowledge

text: of

text: its

text: a

text: robust

text: experimental

text: method

text: based

text: on

text: optical

text: pump-

text: statistics

text: in

text: real-time

text: is

text: also

text: a

text: well-recognized

text: goal

text: for

text: ing

text: Finally,

text: we

text: show

text: that

text: the

text: achieved

text: light-atom