Deza M.M., Laurent M. Geometry of Cuts and Metrics

374

Chapter

24.

Recognition of Hypercube Embeddable Metrics

Proof. Let

y'

E

K'\K

be labeled by

y'.

Then, by

Lemma

24.4.5 and

the

triangle

inequality applied to

C,C',Y',

we

obtain

that

2k

:S

I C,0,C' I

:S

4k. Moreover,

3k

IC,0,y

t

l I(C,0,C'),0,(C',0,Y')1 implying

that

21(Y' \ C

t

) n

(C

\

C')I

=

IC,0,C'1

2k.

Therefore,

IC,0,C'1

=

2k

for, otherwise,

IC

\

C'I

~

IKt \

KI

which

yields:

M

:S

IK'I

IK

n

K'I

+ IKt \

KI

:S

4k

+

2.

I

Lemma

24.4.S.

There are

at

most

M distinct M -cliques.

Proof.

Let KI,

...

,

KN

be

the

distinct M-cliques

with

respective centers

Ct,

...

,

CN and suppose

that

1'1

> AI. Then, there exists a set C such

that

IC,0,Cil

= k

for all i

1,

...

,1'1

(since, by Lemma 24.4.7,

we

have a 2k-valued equidistant

metric on

CI,

...

,CN).

We

claim

that

IC,0,XI

2k

for all x E

V;

this implies

that

2kd'::;rc

is

hypercube embeddable, contradicting our assumption

that

G

i¢.

9k.

First,

suppose

that

x belongs to some M-clique

Ki.

Then,

IC,0,XI

:S

I

C,0,C

i

I +

I

Ci,0,X

I =

2k

and

3k

=

IX,0,C

j

l

:S

IX,0,CI

+

IC,0,CI

=

IX,0,CI

+ k, which

shows

that

IC,0,XI

= 2k. Suppose now

that

x

i¢.

UtI

K;.

Then,

IX,0,CI

:S

IX,0,Cil

+

IC

i

,0,CI

= 4k.

On

the

other hand,

3k

IX,0,Cil

I (X,0,C),0,(C,0,C

i

)

I

yielding

21(X

\

C)

n (C; \

C)I

IX,0,Cj

2k. Henceforth,

IX

,0,CI

=

2k

for,

otherwise,

IX

\

CI

~

M.

I

Lemma

24.4.9.

Let

K

be

an

M·clique

and let x E V \

K.

Then, x is adjacent

to

at

most

three points

of

K.

Proo/.

If

x is adjacent to 4 points

of

K

then

their labeling sets together

with

the

center C

of

K provide a hypercube embedding for

the

metric ant3k(2H5). This

cannot be, since

3k

<

sh(2k15)

(indeed,

sh(2k1

5

))

~

~m

=

1fk

> 3; recall

Proposition 7.2.6).

I

Lemma

24.4.10.

Every

transversal is a clique

and

maximal

transversals are

pairwise disjoint.

Proof.

Suppose

that

x,

y, z are distinct points

of

a transversal L such

that

y

is

adjacent to x

and

z and

x,

z are not adjacent. Let K f

K'

be M-cliques

containing respectively

x

and

y and let C, C' be their centers.

We

obtain

a

contradiction by applying

the

pentagonal inequality to

X,

Z,

C',

Y, C (assigning

1 to

X,

Z, C

t

and

-1

to

Y,

C).

Suppose now

that

and

L2

are nondisjoint maximal transversals. Let x E

L1

nL2,

yELl

\L2

and

z E L2

\L1,

let

K,

K'

be M -cliques containing respectively

x

and

y,

with

centers C

and

C

'

.

We

have a contradiction by applying

the

pentagonal inequality to

Y,

Z,

C,X,C'

(assigning 1 to Y, Z, C

and

-1

to

X,

C

'

).

I

Proposition

24.4.11.

The order

of

congruence

of

the class

1ik

is

less

than

or

equal to

(3M2R+

R+

2M2)(M

+ 1).

24.5 Metrics with Restricted Extremal

Graph

375

Proof. Let G =

(V,

E)

be a graph such

that

G[U]

E

11k

for all U

~

V

with

lUI::;

N(M

+

1)

where N

3M

2

R+ R+

2M2;

we

show

that

G E

11k.

The

only

thing

to verify is

that

G E

:Fk,

as G satisfies obviously (i)-(vi) (since

N(M

+

1)

is large enough).

In

particular,

we

have

that

IV

\

Vol

::;

R,

IVII

::;

M2

and

IViI

::;

3M

2

R.

Let L

I

,

...

,

Lp

denote the maximal transversals

that

are disjoint from

Vi

(Le., having no node adjacent to a node of V \

Vo);

we

have

that

p

~

1 (else

we

are done since

IVI

::;

N(M

+

1)

as

Vo

~

V

2

).

Let

V*

be a subset

of

V

containing

(V

\

Vo)

U

VI

U

Vi

and meeting every M-clique

of

G

in

M points.

Then,

IV*

I

::;

N.

Finally, set

V**

V*

U

UiE[

L

i

, where I consists

of

the

indices

i E [1,p] for which

LinV*

i 0

and

Li

~

V*.

Obviously, III

::;

IV*I

which implies

that

IV**I

::;

N(M

+ 1).

Therefore, G[V**] E

11k

and, thus,

we

have an embedding x E V**

f--+

X

~

fl*

in some hypercube

H(fl*)

for the distance 2kd

O

[v

••

j'

We

now indicate how to

extend this embedding to the whole graph

G.

Let

fl.

(i

E [1,p] \ I) be disjoint sets, disjoint from

fl*,

and

each having

cardinality

k. For each M-clique K n V** of G[V**],

we

let C

K

denote its center.

I t remains

to

label the nodes of V \ V**. A node x E V \

V**

belongs to a unique

At-clique

K

and

the

(unique) maximal transversal containing x

is

Li

for some

i E [1,p] \

I.

We

then

label x by the set X

:=

CK U

fl

i

.

We have to verify

that

this gives a correct labeling, i.e.,

that,

for y E V labeled by

Y,

IX

6YI

=

2k

if

x, y are adjacent

and

IX

6YI

= 4k otherwise.

Suppose first

that

x,

yare

not adjacent.

If

y E V**,

then

IC

K

6YI

=

3k

(by

Lemma

24.4.5) which gives IX

6YI

= 4k.

If

Y E V \ V**,

then

y

is

labeled

by CK'

U

flj

where

K'

i K

and

i i

j,

which gives again

IX6YI

=

4k

since

ICK6CK'I

2k

(by Lemma 24.4.7).

Suppose now

that

x,

y are adjacent.

If

y E K n V**

then

IY

6C

KI

k

and, thus,

IX6YI

= 2k.

If

y E K \

V**

then

Y =

CK

U

flj

with i i j (else

x, y E

Li

n

K),

which yields again

that

IX

6YI

=

2k.

~ow,

if y

if.

K

then

y E

Li

since {x, y} is transversal. This implies

that

y

if.

V··

(as i

if.

[l,pJ). Let

K'

be the

M-dique

containing

y.

Then, Y = C

K

, U

fli

and, thus, IX

6YI

ICK6CK,I

2k. I

24.5

Metrics

with

Restricted

Extremal

Graph

let d be a metric

on

V

n

.

Given distinct

i,j

E V

n

,

the

pair

ij

is said to be extremal

for d if there does not exist k E

Vn

\

{i,j}

such

that

d(i, k) =

d(i,j)

+ d(j, k)

or

d(j, k)

d(i,j)

+ d(i, k).

Then,

the

extremal graph

of

d is defined as the subgraph of

Kn

formed by the set

of extremal edges of

d.

The

notion of extremal graph

turns

out

to be useful when

studying the metrics

that

can be decomposed as a nonnegative (integer)

sum

of

cut

semimetrics. Assertion (i) in Theorem 24.5.1 was proved by Papernov

[1976J

and

(ii) by Karzanov

[1985].

376

Chapter

24.

Recognition of

Hypercube

Embeddable

Metrics

Theorem

24.5.1.

Let

d

be

a

metric

on

Vn

whose

extremal

graph is

either

K

4

,

or

Os,

or

a

union

of

two

st

ars

3.

Then,

(i)

d is iI-embeddable, i.e.,

dE

CUT

n

•

(ii) d is hypercube embeddable

if

and only

if

d satisfies the

parity

condition

(24.1.1).

Note

that

it

suffices

to

show

Theorem

24.5.1 (ii), as

it

implies (i).

The

proof

that

we present below was given by Schrijver [1991].

It

is

shorter

than

Karzanov's

original proof,

but

it

is nonconstructive.

Karzanov's

proof

yields

an

algorithm

permitting

to

construct

a

Z+-realization

of d

in

O(n

3

)

time

(if one

exists). Schrijver shows

the

following result, from which

Theorem

24.5.1 will

then

follow easily.

Theorem

24.5.2.

Let

G = (V,

E)

be

a connected bipartite graph and,

for

W

C;;;

V,

let H = (W,

F)

be

a graph which is

either

K

4

,

Os,

or

a

union

of

two

stars.

Then,

there

exist

pairwise edge

disjoint

cuts

Dc(SI),

...

,Dc(St)

in

G such

that,

for

each (r, s) E

F,

the

number

of

cuts Dc(Sh)

(1

:::;

h

:::;

t)

separating r

and

s is equal to the distance

dc(r,

s)

from

r to s

in

G. (Here,

the

symbol

Dc(S)

denotes

the

cut

in

G which consists

of

the

edges of G having one

endnode

in

S

and

the

other

endnode

in

V \ S.)

Proof.

Suppose

that

the

theorem

does

not

hold.

Let

G

be

a

counterexample

with

smallest

value

of

lEI.

Then,

(24.5.3)

for each

0

=f.

S c V,

there

exist (r, s) E F

and

a

path

P

connecting

rand

s

in

G such

that

IP \ Dc(S)1

:::;

dc(r,

s) - 2

(where

P

denotes

the

edge set

of

the

path).

Suppose

S is a

subset

of V for which

(24.5.3) does

not

hold.

Then,

for each

(r,s)

E

F,

IPnDc(S)1

= 1 (resp. 0)

for each

shortest

rs-path

P

if

Dc(S)

separates

(resp. does not

separate)

rand

s.

Let

G'

denote

the

connected

bipartite

graph

obtained

from G by

contracting

the

edges

of

Dc(S).

Hence, for

(r,s)

E

F,

dCI(r,s)

=

dc(r,s)

- 1

if

Dc(S)

separates

r,

sand

dCI(r, s) =

dc(r,

s) otherwise. As

G'

has fewer edges

than

G,

by

Theorem

24.5.2,

we

can

find paiwise edge disjoint

cuts

Dc,(SD,

...

,

DCI(S~)

in

G'

such

that

dC1(r,s) is equal

to

the

number

of

cuts

DC1(SU

separating

rand

s.

These

t

cuts

yield t

cuts

Dc(Sh)

in

G which,

together

with

the

cut

Dc(S),

are

pairwise disjoint

and

satisfy: for

(r,

s) E

F,

the

number

of

cuts

separating

rand

s

is

equal

to

dc(r,

s).

This

contradicts

our

assumption

that

G is a

counterexample

to

Theorem

24.5.2.

Claim

24.5.4.

For

alli

=f.j E

V,

there exists

(r,s)

E F such

that

{i,j}n{r,

s}

=

o

and

dc(

i,

j)

+

dc(r,

s)

2:

max(

dc(i,

r)

+

dc(j,

s),

dc

(i, s) +

dc(j,

r)).

3 A

graph

is

said

to

be

a union

of

two stars if

it

has

two

nodes

such

that

every

edge

contains

one

of

them.

24.5

Metrics

with

Restricted

Extremal

Graph

377

Proof

of

Claim

24.5.4.

Let

i

=1=

j E

V.

Set

X

:=

{k

E V I dG(i,j) = dG(i, k) +

dG(j,k)}.

Hence,

i,j

EX.

Suppose

first

that

X =

V.

By

(24.5.3)

applied

to

{i}, we find (r,s) E F

and

an

rs-path

P

such

that

IP\b

G

(

{i})1

~

dG(r,

s)

-2.

Hence, P is a

shortest

rs-path

and

i is

an

internal

node

of

P

and,

thus,

i

rt

{r, s}.

Using

the

fact

that

X =

V,

one

obtains

that

j

rt

{r, s}

and

dG(i,

j)

+dG(r,

s)

= dG(i, r) +dG(j, r) +dG(r, s)

;:::

dG(r, i) +

dc(s,

j);

the

other

inequality

of

Claim

24.5.4 follows

in

the

same

way.

Suppose

now

that

X

=1=

V.

Let

G'

denote

the

graph

obtained

from G

by

contracting

the

edges

of

bG(X).

By

(24.5.3)

applied

to

X,

there

exists

(r,

s) E F

such

that

dG,(r,

s)

~

dG(r,

s)

- 2.

Moreover, we

claim

(24.5.5)

{

dG,(i,s);::: dG(i,s)

-1,

dG,(r,j)

;:::

dG(r,j)

-1,

dG,(j,s)

;:::

dG(j,s)

-1,

dG,(r,i);:::

dG(r,i)-1.

We

show

that

dG'

(i, s)

;:::

dG(i,

s)

-

1;

the

other

inequalities

of

(24.5.5)

can

be

proved

in

the

same

way.

Let

P

be

a

path

connecting

i

and

s

in

G

such

that

IF

\ bG(X)1 = dG,(i,s)

and

with

smallest

value

of

IF

n bG(X)I.

Suppose

that

IP

n bG(X)1

;:::

2.

Let

P'

denote

the

smallest

subpath

of

P

starting

at

i

and

such

that

IP'

n bG(X)1 =

2.

Let

k

denote

the

other

endnode

of

P',

so k E

X,

and

set

P"

:=

P \ P'. As

P'

is

not

contained

in

X,

we have dG(i, k)

~

IP'I- 1

and,

as

G is

bipartite,

dG(i, k)

~

IP'I

-

2.

Let

Q'

be

a

shortest

path

from

i

to

k

in

G.

Then,

IP'I

- 2 = dG,(i, k)

~

IQ'

\

bG(X)1

~

IF'I

- 2 -IQ' n bG(X)I,

which

implies

Q'

n bG(X) = 0

and

IQ'I

= dG(i, k) = IP'I-

2.

Consider

the

path

Q

from

i

to

s

obtained

by

juxtaposing

Q'

and

P".

Then,

IQ

\ bG(X)1 =

IP

\

bG(X)1

and

IQ

n

bG(X)1

=

IP

n

bG(X)1

-

2,

contradicting

our

choice

of

P.

Therefore,

IP

n

bG(X)1

~

1.

This

shows

that

dG,(i,s) = IF\bG(X)I;::: IFI-l;:::

dG(i,s)-1.

Hence, (24.5.5) holds.

From

dG'

(r,

s)

~

dG(r,

s) - 2

and

(24.5.5), we

deduce

that

{i,

j}

n {r, s} =

0.

Moreover,

there

exists

a

rs-path

P

in

G

such

that

IP

\

bG(X)1

= dG,(r,

s)

and

P

contains

a

node

k

EX.

Hence,

dG(r,

s)

+ dG(i,j)

;:::

dG,(r, s) + 2 + dG(i,j)

= dG,(r, k) + dG,(s, k) + 2 + dG(i, k) + dG(j, k)

;:::

dG,(r,i) + dG,(s,j) +

2;:::

dG(r,i) + dG(s,j)

378

Chapter

24. Recognition

of

Hypercube

Embeddable

Metrics

(using (24.5.5) for

the

last inequality).

The

other

inequality from

Claim

24.5.4

follows

in

the

same

way. I

From

Claim

24.5.4,

we

deduce, in

particular,

that

H

is

not

a union

of

two

stars.

Hence, H is

either

K4

or

C

5

.

Suppose

first

that

H = K

4

•

From

Claim 24.5.4,

we

obtain

(24.5.6)

For

i E

W,

set

da(i,j)

+ da(h,

k)

= da(i,

h)

+ da(j,

k)

for all

distinct

i,j,

h,

k E

W.

1

f(i)

:=

"2(da(i,

h)

+ da(i,

k)

- da(h, k))

where h

=1=

k E W \ {i};

the

definition does

not

depend

on

the

choice

of

h, k by

(24.5.6).

Then,

da(i,j)

=

f(i)

+

f(j)

for i

=1=

JEW.

Suppose

f(i)

=1=

O.

By

(24.5.3)

applied

to

{i},

there

exists (r,s) E F

and

a

rs-path

F such

that

IF

\

oa(

{i})1

:s:

da(r, s) -

2.

Hence, F

is

a

shortest

rs-path

passing

through

i.

Thus,

IFI

= da(r,

s)

=

f(r)

+

f(s),

and

IFI

= da(i, r) + da(i, s) =

f(r)

+

f(s)

+

2f(i),

implying

f(i)

=

o.

We

obtain

a contradiction.

Suppose

now

that

H = C

5

. Say,

W:=

{rl,r2,r3,r4,r5}

and

F:=

{(ri,ri+1) I

1

:s:

i

:s:

5}, where

the

indices are

taken

modulo

5.

Applying Claim 24.5.4

to

ri,

ri+2,

we

obtain

that

da(ri,

ri+2)

+ d

a

(ri+3,

riH)

2::

da(ri'

riH)

+ da(ri+2'

ri+3)

for 1

:s:

i

:s:

5 (as

(ri+3,

riH)

is

the

only edge

of

C5

disjoint from

ri

and

ri+2).

Adding

up

these

ten

inequalities,

we

obtain

the

same

sum

on

both

sides

of

the

inequality sign. Hence, each

of

the

above inequalities is, in fact,

an

equality.

Hence, (24.5.6) holds again, yielding a contradiction as above.

I

Proof

of

Theorem 24.5.1. Let d

be

an

integral metric on

Vn

satisfying

the

parity

condition (24.1.1)

and

whose

extremal

graph

H

:=

(w,

F)

is

either

K

4

,

or

C

5

,

or

a

union

of

two stars. We show

that

d can decomposed as a nonnegative integer

sum

of

cut

semimetrics. Consider

the

complete

graph

Kn

on

V

n

. We

construct

a

connected

bipartite

graph

G by subdividing

the

edges

of

Kn

in

the

following

way: For all

distinct

i,

j E V

n

,

replace

the

edge

ij

by a

path

Fij consisting

of

d(i,j)

edges.

The

fact

that

G is

bipartite

follows from

the

parity

condition.

By

Theorem

24.5.2,

there

exist edge disjoint

cuts

0a(Sh)

(1

:s:

h

:s:

t)

in

G such

that,

for each

(r,

s) E

F,

da(r, s)

is

equal

to

the

number

of

cuts

0a(Sh)

separating

r

and

s.

Setting

Th

:=

Sh

n V

n

,

we

obtain

that,

for each

(r,

s)

E

F,

(24.5.7)

d(r, s) = da(r, s) = L o(Th)(r, s).

lShSk

Moreover, for all i

=1=

j E V

n

,

we have

24.5 Metrics with Restricted

Extremal

Graph

379

(24.5.8)

d(i,j)

~

2:

b(Th)(i,j).

l:Sh:St

Indeed,

the

number

of

cuts

bC(Sh) separating

rand

s is less

than

or equal

to

the

number

of

cuts

bC(Sh) intersecting

the

path

Pij

which,

in

turn,

is less

than

or

equal

to

the

length

d(i,j)

of P

ij

since

the

cuts bC(Sh) are pairwise edge disjoint.

In

fact, equality holds

in

(24.5.8). To see it, let i

t=

j E

Vn

and

let P

:=

(io,

...

,ik)

be

a

path

in

Kn

which contains

the

edge

(i,j)

and

is a geodesic for d (Le., P is a

shortest

path

(with respect to

the

length function

d)

between its extremities

io

and

ik;

that

is, d(io, ik) =

L:O<m<k-l

d(im,

im+d).

Choose such a

path

P having

maximum

number

of edges.

Then,

the

pair

(io, ik)

is

extremal

for

d.

For, if not,

there

exists x E

Vn

\

{io,id

such

that,

e.g., d(io,x) = d(io,ik) + d(x,ik) and,

then,

(i

o

,

...

, ik, x) is a geodesic containing

(i,j)

and

longer

than

P.

Then,

using

(24.5.8), we have

k-l k-l

t

d(io, ik) =

2:

d(im' i

m

+

1

)

~

2: 2:

b(Th)(i

m

,

im+l).

m=O

h=l

But,

k-l

t t

k-l

t

2: 2:

b(Th)(im'

im+d

=

2: 2:

b(Th)(i

m

,

im+d

~

2:

b(Th)(io, ik) = d(io, ik),

m=O

h=l

m=O

h=l

where

the

last

equality follows from (24.5.7) as

the

edge (io,ik) belongs

to

F.

Therefore, equality holds

in

(24.5.8) for each of

the

edges (im'

im+l)

of

P and,

in

particular,

for

the

edge

(i,j).

This

shows

that

equality holds

in

(24.5.8) for all

i

t=

j E V

n

.

Therefore, d =

L:~=l

b(T

h

),

showing

that

d is hypercube embeddable.

I

0----0

(a)

(b)

Figure 24.5.9

Remark

24.5.10.

One can check

that

a

graph

H with no isolated node is K

4

,

C

5

,

or

a union of two

stars

if

and

only if H does

not

contain as a

subgraph

the

two

graphs

from Figure 24.5.9.

The

exclusion of these two graphs is necessary

for

the

validity of

Theorem

24.5.1. Indeed, let d

1

be

the

path

metric of

the

com-

plete

bipartite

graph

K

2

,3;

then, d is

not

hypercube embeddable (as d does not

satisfy

the

pentagonal

inequality)

and

its

extremal

graph

is

the

graph

(a) from

Figure

24.5.9. Let d

2

be

the

path

metric of the

graph

K3,3

\

e;

then

its

extremal

380

Chapter

24.

Recognition

of

Hypercube Embeddable Metrics

graph

is

the

graph (b) from Figure 24.5.9

and

d2

is

not

hypercube embeddable

(as

it contains d

1

as a subdistallce). (In fact,

both

dl

and

d2

lie on extreme rays

of

the semimetric cone.) I

M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,

Chapter

25.

Cut

Lattices,

Quasi

h-Distances

and

Hilbert

Bases

We consider

in

this

chapter

several additional questions related to

the

notion of

hypercube

embedding. A possible way

of

relaxing this notion is

to

look for integer

combinations

rather

than

nonnegative integer combinations

of

cut

semimetrics.

In

other

words, one considers

the

lattice Ln generated by all

cut

semimetrics

on

V

n

. We recall

in

Section 25.1

the

characterization

of

Ln.

This

is

an

easy

result; namely, Ln consists

of

the

integer distances satisfying

the

parity

condition.

We also present

the

characterization

of

some sublattices

of

L

n

,

namely,

of

the

sublattice

generated

by all even

T-cut

semimetrics

and

of

the

sublattice generated

by all k-uniform

cut

semimetrics.

Clearly, for a distance

d on V

n

,

(25.0.1 ) d is hypercube embeddable

===>

d E

CUTn

n Ln.

We consider

in

Section 25.2 quasi h-distances, which are

the

distances d

that

belong to

CUTn

n Ln

but

are

not

hypercube embeddable. As was mentioned

in

Theorem

24.1.3,

the

implication (25.0.1) is

an

equivalence for any distance d

on

n

::;

5 points.

This

fact

can

be

reformulated as saying

that,

for n

::;

5,

the

family

of

cut

semimetrics

on

Vn

is

a Hilbert basis. We consider

in

Section 25.3

the

more general question

of

characterizing

the

graphs

whose family

of

cuts

is a

Hilbert

basis.

25.1

The

set

Cut

Lattices

Ln

:=

{ L >'so(8) I

>'s

E Z for all 8

<:;;

V

n

}

SC;;Vn

is trivially a

lattice

contained

in

Z(;),

called

the

cut

lattice.

The

Assouad

[1982]

gives a characterization

of

Ln.

Proposition

25.1.1.

Let

dE

ZEn.

Then,

dE

Ln

if

and only

if

d satisfies the

parity condition (24.1.1).

Proof.

The

parity

condition is clearly a necessary condition for

membership

in

Ln.

Conversely, suppose d is integral

and

satisfies

the

parity

condition.

Then,

Vn

can

be

partitioned

into

Vn

= 8 U T

in

such a way

that

d( i,

j)

is

odd

if

i E

8,

JET

382

Chapter

25.

Cut

Lattices, Quasi h-Distances

and

Hilbert Bases

and

d(i,j)

is even otherwise. Set d'

:=

d + 8(8).

Then,

all components

of

d' are

even. As

d'=

L

d'(i

j

)(8({i})+8({j})-8({i,j})),

l:'O:i<j:'O:n

we deduce

that

d' E

Ln

and, thus, d = d' - 8(8) belongs

to

Ln

too.

I

A basis

of

the

cut

lattice

Ln

is provided by

the

set

{8(i)

11

SiS

n - I} U {8({i,j})

11

S i < j S n - I}.

(Indeed, every vector d E

Ln

can

be decomposed as

d = L

ai

8

(i) +

fJ

ij

8(

{i,j}),

l:'O:i:'O:n-l l:'O:i<j:'O:n-l

setting

ai

:=

din -

Ll:'O:h:'O:n-l,hi-i

fJih

(1

SiS

n

-1)

and

fJij

:=

!(din

+djn

-

dij)

(1

S i < j S n - 1).) Note also

that

the

image

of

the

cut

lattice

Ln

under

the

covariance

mapping

e is nothing

but

the

integer lattice Z(;). For small values

of

n,

Ln

coincides

with

classical lattices; for instance, L3 =

A3

= D3 (recall

Example

13.2.5).

Complete characterizations are also known for several sublattices

of

Ln.

We

consider below

the

sublattices generated by

the

k-uniform

cut

semimetrics,

the

even

cut

semimetrics (more generally,

the

even

T-cut

semimetrics),

and

the

odd

cut

semimetrics

on

six points. Given 8

~

V

n

,

the

cut semimetric 8(8) is

said

to

be

k-uniform

if

181

E

{k,n

-

k}.

We

let

K~

denote

the

set

of

all k-uniform

cut

semimetrics

on

V

n

.

The

following characterization

of

the

k-uniform

cut

lattice

Z(K~)

is given in Deza

and

Laurent

[1992eJ,

based

on

a result

of

Wilson [1973].

Proposition

25.1.2.

Let

k

be

an

integer

such

that

2 S k S

nand

k

=I-

~

and

let

d E ZEn.

Then,

d E

Z(K~)

if

and

only

if

d

satisfies

the following

conditions:

(i)

L

d(i,j)

==

0

(mod

k(n

-

k)),

l:'O:i<j:'O:n

(ii)

Di

:=

n!2k

( ,L,

d(i,j)

- n

~

k L d(r,

S))

E Z

for

all i E V

n

,

l:'O:J:'O:nJi-'

l:'O:r<s:'O:n

(iii)

Di

+ D

j

+

d(i,j)

==

0

(mod

2)

for

all

i,j

E V

n

.

I

In

the

case k = L I

J,

we

have

the

following result.

Proposition

25.1.3.

Let

d E ZEn.

(i)

If

n =

2k

+ 1,

then

d E

Z(K~)

if

and

only

if

d satisfies

the

congruence

relation: L

d(i,j)

==

0

(mod

k(n

-

k)).

l:'O:i<j:'O:n

(ii)

If

n =

2k,

then

d E

Z(K~)

if

and

only

if

(iia),(iib) hold:

25.1

Cut

Lattices

383

1

k E

d(r,s)

for

each

1

~

i

~

n,

l.:Sr<sSn

(iia) E d(i,

j)

(iib) E

d(i,j)

0

(mod

k

2

).

l.:Si<i.:Sn

Proof. (i) Observe

that

the conditions (ii),(iii) from Proposition 25.1.2

are

im-

plied by

the

condition (i)

of

Proposition 25.1.2.

(ii)

The

conditions (iia),(iib) are clearly necessary for membership in

Z(K~).

Conversely, suppose

that

d satisfies (iia),(iib)

and

let

d'

denote its projection

on

the

set {I,

...

, n

-I}.

:From

(iia),

we

obtain

(25.1.4)

d!(r,s)=(k

1)

E

d(i,n).

l.:Sr<sSn-l

Hence,

Ll<r<s<n-l

d'(r,s)

0 (mod k(k

1»,

as

Ll<i<n-l

d(i,n)

==

0 (mod

k)

by (iia,)(iib). Using (i),

we

deduce

that

d'

E

Z(K~_l)~

Hence,

d'

>'s8(S)

S<;{l, ...

,n-l

},ISI=k

with

>'s

E Z for all

S.

We

show

that

d =

Ls

>'s8(S). As

E d!(r,s)

k(k-1)(E>.s),

l.:Sr<s.:Sn-l

s

(25.1.4) yields:

E d(i, n) =

k(E

>'s).

l.:Si.:Sn-l S

Then,

by (iia),

E d(r,

s)

=

k2(E

>.s)

and

E

d(i,j)

=

k(E

>.s)

l.:Sr<s.:Sn S

l':sjSn,jfi

S

for each i = 1,

...

,no

We

compute, for instance,

d(l,n).

The

above relations

yield:

d(l,

n)

=

k(E

>.s}

- E

d(l,j).

s

2Si.:Sn-l

Using

the

value of

d(l,j)

=

d'(l,j}

given by

the

decomposition

of

d!,

we

obtain

that

d(l,

n)

=

LSIIES

>'s.

This

shows

that

d =

Ls

>'s8(S), i.e.,

that

d E

Z(K~).

I

Suppose

that

n is even. A

cut

semimetric 8(S) on

Vn

is said

to

be

even

if

lSI

is even. Similarly, 8(S) is called odd if

lSI

is

odd. More generally, let T

~

Vn

such

that

ITI is even; then, 8(S)

is

said to be

an

even

T-cut semimetric

if

IsnTI

is even.

We

let

K~

denote

the

set of even T-cut semimetrics on V

n

. Hence,

K;:"

is

the

set of even

cut

semimetrics.

We

let also

K~dd

denote

the

set

of

odd

cut

semimetrics.

We

first give a characterization

of

the even

cut

lattice Z(K;:"),

whose

proof

can

be found in Deza, Laurent and Poljak

[1992].

Deza M.M., Laurent M. Geometry of Cuts and Metrics

Подождите немного. Документ загружается.