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

3.1 Distance Spaces

and

fp-Spaces

31

(3.1.4)

NORn(p)

:=

{d E

JRE"

I ifti is fp-embeddable},

where

\fd

denotes the vector

({Iilij)..

. Then,

the

set NORn(p) is a cone

'JEE"

which is not polyhedral if 1 < p <

00;

moreover, every

cut

semimetric lies on

an

extreme ray

of

NORn(p) (see Lemma 11.2.2). Note

that

the cones

NORn(l)

and

CUTn coincide.

The

cone NORn(2) (which corresponds

to

the

Euclidean

distance) has also been extensively investigated; results are grouped in Section

6.2.

We

want

to

point

out

that,

although NORn(I) = CUTn appears

to

be much

nicer

than

NORn(2) since

it

is

a polyhedral cone with very simple extreme rays,

we do not know

an

inequality description of NORn(1).

In

fact,

the

investigation

of

the facial

structure

of

the

cone NORn(I) CUTn will form

an

important

part

of

this

book, taken

up

especially in

Part

V.

Figure 3.1.5:

The

unit balls for

the

fl'

f2

and

foo-norms

To conclude let us compare

the

unit balls

of

the

various fp-spaces. Let Bp

denote

the

unit ball in

f;,

defined by

Then,

Ijn

is

the ·n-dimensional hypercube

In

(with side length 2),

Bl

coincides

with

the

n-dimensional cross-polytope

fin,

and

B2

is

the

usual

Euclidean unit ball.

The

following inclusions hold:

Bl

<;

Bp

<;

Boo

for 1

:::;

P

:::;

00,

which follow from the well-known Jensen's inequality (see, e.g., Section 2.10

in

Hardy, Littlewood

and

P6lya [1934]):

II

x

Ilq

:::;

II

x

lip

for all x E

JR

n

,

1:::; P < q

:::;

00.

Figure 3.1.5 shows

the

three balls B

l

,

B

2

,

and

Boo

in dimension n 2. Note

that

the

balls

Bl

and

Boo

are in bijection via

the

mapping f :

JR2

--+

JR2

defined

by

(3.1.6)

(

Xl

X2

X =

(Xl,X2)

f-+

f(x):=

-2-'~-":::'

(which

rotates

the

plane by

45

degrees and

then

shrinks it by a factor

~).

In-

deed, one

can

verify

that

II

x

1100=11

f(x)

IiI

for all X E

JR

2

•

Therefore,

the

map-

ping

f provides

an

isometry between the distance spaces

(JR

2

,de"",)

and

(JR

2

,

del)'

32

Chapter

3.

Preliminaries

3.2

Measure

Spaces

and

Lp-Spaces

We now define

the

distance space Lp(n,

A,

J.i),

which is

attached

to

any measure

space

(n,

A,

J.i).

For this,

we

recall some definitions

5

on measure spaces.

Let

n

be

a set

and

let A

be

a a-algebra

of

subsets

of

n,

i.e., A is a collection

of

subsets

of

n satisfying

the

following properties:

if

A E A

then

n \ A E A,

{

nEA,

if

A = U Ak

with

Ak

E A for all k,

then

A E A.

k=l

A function

J.i

: A is a measure on A

if

it

is additive, i.e.,

J.i(

U Ak) =

2:

J.i(Ak)

k2:1 k;:::l

for all pairwise disjoint sets Ak E

A,

and

satisfies

J.i(0)

0.

Note

that

measures

are always

assumed

here to

be

nonnegative. A measure

.space

is a triple

(n,

A,

J.i)

consisting

of

a set

n,

a a-algebra A

of

subsets

of

n,

and

a measure

J.i

on

A.

A

probability

.space

is a measure space

with

total

measure J.i(n) =

1.

Given a function f : n

JR,

its Lp-norm is defined by

1

II

f

(In

If(W)lPJ.i(dW)Y·

Then,

Lp(n,

A,

J.i)

denotes

the

set

of

functions f : n

--->

JR

which satisfy

II

f

00.

The

Lp-norm defines a metric

structure

on Lp(n,A,J.i), namely, by

taking

II

f - 9

lip

as distance between two functions

f,9

E Lp(n,A,J.i)' A distance

space

(X,

d)

is said to

be

Lp-embeddable

if

it

is a subspace

of

Lp(n,

A,

J.i)

for

some

measure

space (n,A,J.i).

The

most

classical example

of

an

Lp-space is

the

space Lp(n,

A,

J.i),

where n

is

the

open

interval (0,1), A is

the

family

of

Borel subsets

of

(0, 1),

and

J.i

is

the

Lebesgue measure; it is simply denoted by

Lp(O,

1).

We

now make precise

the

connections existing between Lp-spaces

and

fp.spaces:

(i)

If

n =

N,

A =

211

is

the

collection

of

all subsets

of

n,

and

J.i

is

the

cardinality

measure,

i.e.,

J.i(A)

=

IAI

if

A is a finite subset

of

nand

J.i(A)

=

00

otherwise,

then

Lp

(N,

2N

,

1.1)

coincides

with

the

space

ff.

(ii)

If

n

Vrn

is a set

of

cardinality

m,

A 2

11

,

and

J.i

is

the

cardinality

measure,

then

Lp

(V

m,

2

v~

,

1·1)

coincides

with

t;;'.

In

other

words,

f;J"

is

an

isometric subspace

of

ff

which,

in

turn,

is Lp-embeddable.

We consider

in

detail L

1

-embeddable distance spaces

in

Chapter

4.

It

turns

out

that,

for a finite distance space,

the

properties

of

being flo,

ff,

or L

1

-

embeddable

are

all equivalent

to

the

property

of

belonging to

the

cut

cone (see

Theorem

4.2.6).

more

information concerning measure spaces

and

integrability of functions,

the

reader

may

consult

the

textbook

by

Rudin

[1966].

3.2

Measure

Spaces

and

Lp-Spaces

33

Similar

results

are

known

for

the

case p

?:

1 (see, e.g.,

Fichet

[1994]).

Namely, for a finite

distance

space

(X,

d),

the

properties

of

being

£p-,

£';-,

or

Lp-embeddable

are all equivalent.

Though

we

are

mainly

concerned

with

finite

distance

spaces, i.e.,

with

dis-

tance

spaces

(X,

d)

where X is finite,

we

also

present

a

number

of

results

involv-

ing infinite

distance

spaces. For instance,

we

consider

in

Section

8.3

the

normed

vector

spaces whose

norm

metric

is L1-embeddable. However,

the

following fun-

damental

result

of

Bretagnolle,

Dacunha

Castelle

and

Krivine [1966] shows

that

the

study

of

Lp-embeddable

spaces

can

be

reduced

to

the

finite case.

Theorem

3.2.1.

Let

p

?:

1

and

let

(X,

d)

be

a distance space.

Then,

(X,

d)

is Lp-embeddable

if

and

only

if

every finite subspace

of

(X,

d)

is Lp-embeddable. I

Similarly,

the

study

of

£~-embeddable

spaces

can

be

reduced

to

the

finite

case.

The

follows from

the

compactness

theorem

oflogic

(as

observed

by

Malitz

and

Malitz

[1992]

in

the

case p = 1).

Theorem

3.2.2.

Let

p, m

?:

1

be

integers

and

let

(X,

d)

be

a distance space.

Then,

(X,

d) is

£~-embeddable

if

and

only

if

every

finite

subspace

of

(X,

d) is

£~

-embeddable.

Proof.

Necessity is obvious. Conversely,

suppose

that

every finite

subspace

of

(X,

d)

is

£~-embeddable.

Fixing

Xo

E X

we

can

restrict

ourselves

to

finding

an

embedding

of

(X,

d)

in

which

Xo

is

mapped

to

the

zero vector. Hence,

we

search

for

an

element

(UX)XEX

ofthe

set

K:=

II

[-d(xo, x), d(xo,

x)]m

such

that

xEX

II

U

x

- u

y

IIp= d(x, y) for all x, y

EX.

For x, y E

X,

let

Kx,y

denote

the

subset

of

K

consisting

of

the

elements

that

satisfy

the

condition

II

U

x

- u

y

IIp= d(x, y).

By

assumption,

any

intersection

of

a finite

number

of

Kx,y's

is

nonempty.

Therefore,

since

K is

compact

(by Tychonoff's

theorem,

as

it

is a

Cartesian

product

of

compact

sets)

and

since

the

Kx,y's

are closed sets,

the

intersection

n

Kx,y

is

x,yEX

nonempty,

which shows

that

(X,

d)

is

£~-embeddable.

I

Finally,

we

introduce

one

more

semimetric

space.

Let

(n,

A,

/1»

be

a

measure

space.

Set

AI':=

{A

E A I

/1>(A)

<

oo}.

One

can

define a

distance

dl'

on

AI'

by

setting

for all A, B E AI'"

Then,

dl' is a

semimetric

on

AI'" We call dl' a

measure

semimetric

and

the

space (AI" dl') a measure

semimetric

space.

The

semimetric

dl' is also called

the

Fnkhet-Nikodym-Aronszajn

distance

in

the

literature.

We

34

Chapter

3.

Preliminaries

will consider

in

Section 9.2

the

distance, which is defined by

JL(A6B)

JL(A

n

B)

for

A,

B E

AiL"

Note

that

the

measure semimetric space

(AiL'

d

iL

) is

the

subspace

of

Ll(fl,A,JL)

consisting of

its

0-1

valued functions. Moreover,

if

fl

=

Vm

is a

finite set

of

cardinality

m,

A =

2°,

and

JL

is

the

cardinality measure,

then

the

space (AiL' d

iL

) coincides

with

the

hypercube

metric

space

({O,

l}m, d

R

,).

We

close

the

section

with

two

remarks

grouping a

number

of

results

about

the

isometric embeddings existing among

the

various Lp-spaces. Figure 3.2.3

summarizes

some

of

the

connections existing

among

fp-spaces

and

mentioned

in

Remark

3.2.4 below.

d is

fp-embeddable

=*

2<p<00

if

d is f

2

-embeddable

n

d is foo-embeddable

dis

fp-embeddable

=*

dis

f,-embeddable

=*

l<p<2

if

d is

f~-embeddable

l<p<oo

f/d

is fp-embeddable

l::;p<oo

Figure 3.2.3: Links between various fp-spaces

Remark

3.2.4.

Isometric

embeddings

among

the

Lp-spaces.

There

is a

vast

literature

on

the

topic

of isometric embeddings

among

the

various Lp-spacesj see, e.g.,

Wells

and

Williams [1975],

Dar

[1976], Ball

[1987]

, Lyubich

and

Vaserstein [1993]. We

summarize

here

some of

the

main

results.

The

following is shown in

Dar

[1976].

Let

1

::;

p <

00,

1

::;

T

::;

00

and

mEN,

m

~

2.

Then,

f;:' is

an

isometric

subspace

of

Lp(O,

1)

if

and

only if,

either

(i)

p::;

T < 2,

or

(ii) T = 2, or

(iii)

m = 2

and

p =

1.

Hence, for

instance,

f;

does

not

embed

isometrically in

Lp(O,

1) if T > 2.

It

was

already

shown

by

Bretagnolle,

Dacunha

Castelle

and

Krivine

[1966]

that

Lp(O,I)

embeds

iso-

metrically

in L,(O, 1) for all 1

::;

p::;

2.

As a reformulation

of

the

above result,

we

have

the

following implications for a

distance

space

(X,

d):

•

If

(X,

d)

is

f~-embeddable

for some 1

::;

P

::;

00,

then

(X,

d)

is L

,

-embeddable.

•

If

(X,

d)

is

fp-embeddable

for some 1

::;

p

::;

2,

then

(X,

d)

is

L

,

-embeddable.

•

If

(X,d)

is

f

2

-embeddable,

then

(X,d)

is

Lp-embeddable for

aliI::;

p::;

00.

Let

T

i=

p such

that

1

::;

T,p <

00

and

let m

~

1 be

an

integer.

Then,

f;:'

embeds

isometrically in f; for some integer n

~

1 if

and

only

if

T = 2

and

p is

an

even

integer

(Lyubich

and

Vaserstein [1993]). Given

an

even integer p, define

N(m,p)

as

the

smallest

integer

n

~

1 for which

f2'

embeds isometrically into f;.

It

is

shown in Lyubich

and

Vaserstein [1993]

that

N(2,p)

=

~

+ 1

and

that,

for

any

p

~

2

and

m

~

1,

max(N(m

-

l,p),N(m,p

- 2))

::;

N(m,p)

::;

(m~~~').

An

exact

evaluation

of

N(m,p)

is known for

3.2 Measure Spaces

and

Lp-Spaces

small values

of

p,

m; for instance,

N(3,4)

28,

lv(8,

6) =

120,N(23,4)

276,N(23,6)

35

6,

N(3,

6) 11,

N(3,

8) = 16,

N(7,

4) =

2300,

N(24,

10) = 98280.

Therefore, given

r

and

mEN

such

that

1 < r

s:

2 <

m,

we

have

that

i;:' does

not

embed

isometrically into

ir

(n

positive integer),

but

i;:' embeds

into

LI(O, 1)

and,

moreover, every finite subspace

of

i;?'

on

8 points embeds into

i~;).

I

Remark

3.2.5.

We mention here some observations made by Fichet [1994].

First,

it

can

be easily verified

that

every semimetric on 3 points embeds isometrically in

i~

for

any 1

s:

p

s:

00.

Moreover, every semimetric

on

4 points embeds isometrically in

ii.

On

the

other

hand,

there exist semimetrics on 4 points

that

are

not ip-embeddable for

any

1 < p <

00.

For such

an

example consider

the

distance d on X

:=

{1,2,3,4}

taking

value 2

on

the

pairs

(1,3)

and

(2,4)

and

value 1 on all

other

pairs.

One

can

verify

that

d

is

not

ip-embeddable for 1 < p <

00.

For, suppose

that

there

exist vectors

Ul>

'Uz,

'U3,

U4

E RN providing

an

ip-embedding

of

d.

For each coor-

dinate

mE

[1,

N] consider

the

distance

d'"

on

X defined by IUi(m) uj(m)1 for

i,

j

EX.

We now exploit

the

fact

that

d satisfies several inequalities

at

equal-

ity.

It

can

be

easily observed (using Minkowski's inequality)

that

every d

m

satisfies

the

same

triangle equalities

as

d.

From this follows

that,

for each coordinate

m,

either

(i)

uI(m)

u2(m)

s:

us(m)

= u4(m),

or

(ii)

uz(m)

u3(m)

s:

'uI(m) u4(m). Denoting

by

Nl

(resp. N

z

)

the

set

of

coordinates m for which (i) (resp. (ii)) occurs

and

setting

a:=

EmEN,luj(m)-u3(m)IP,

b:=

EmENz

IUj(m)-uz(m}IP,

we

obtain

that

a b 1

and

21'

= a +

b,

a contradiction if p > 1. I

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

DOI 10.1007/978-3-642-04295-9_4, © Springer-Verlag Berlin Heidelberg 2010

Chapter

4.

The

Cut

Cone

and

1!1-Metrics

In

this

chapter,

we

establish

the

basic connections existing between

the

cut

cone

and

metrics. We show how

the

members

of

the

cut

cone

can

be inter-

preted

in

terms

of

£l-metrics

and

measure semimetric spaces; see

in

particular

Theorem

4.2.6, where several equivalent characterizations are

stated.

We also

introduce

in

Section 4.3 several basic notions which will

be

used

throughout

the

book, namely,

the

notions

of

rigidity, size, scale

and

realizations.

In

Section 4.4,

we

present a

number

of

basic problems

about

cut

polyhedra

and

indicate

their

complexity

status.

4.1

The

Cut

Cone

and

Polytope

We give here

the

exact definitions for

the

cut

cone

and

polytope. We

start

with

recalling

the

notion of

cut

semimetric. Given a subset S of

Vn

=

{I,

...

,n},

let

8(S)

denote

the

vector

of

~En

defined by

( 4.1.1) 8(S)ij = 1

if

IS

n {i,j}1 =

1,

and

8(S)ij = 0 otherwise,

for 1

s:

i < j

s:

n. Obviously,

8(S)

defines a distance on

Vn

which

is

a semimetric;

for

this

reason,

8(S)

is called a cut semimetric. Note

that,

in

later

chapters,

we

may

drop

the

word "semimetric"

and

simply

speak

of

"the

cut

8(S)"

or of

"the

cut

vector 8(S)". We use here

the

word "semimetric"

in

order

to

stress

the

fact

that

we

are working

with

distance spaces.

The

cone

in

~En,

which is generated by

the

cut

semimetrics

8(S)

for S

<;::;

V

n

,

is called

the

cut cone

1

and

is

denoted by

CUT

n

.

The

polytope

in

~En,

which is

defined as

the

convex hull

of

the

cut

semimetrics

8(S)

for S

<;::;

V

n

,

is called

the

cut polytope

and

is

denoted

by

CUT~.

Hence,

(4.1.2)

CUTn

= { L

>'s8(S)

I

>'s

::::

0 for all S

<;::;

V

n

},

S<;;Vn

( 4.1.3)

CUT~

= { L

>'s8(S)

I L

>'s

= 1

and

>'s

::::

0 for all S

<;::;

V

n

}.

S<;;Vn S<;;Vn

It

may

sometimes

be

convenient to consider

an

arbitrary

finite set X

instead

on

'The

cone

CUTn

is also known

in

the

literature

under

the

name

of Hamming

cone;

see, e.g.,

Avis [1977, 1981J,

Assouad

and

Deza

[1982J, etc.

38

Chapter

4.

The

Cut

Cone

and

£l-Metrics

V

n

.

One defines in

the

same

way2

the

cut

cone

CUT(X)

and

the

cut

polytope

CUTD(X)

on

X.

Hence,

Note

that

CUTn

and

CUT~

are

trivial

for n =

2,

as

there

is

only one nonzero

cut

semimetric

on

V

2

.

From now on,

we

will suppose

that

n

2':

3.

There

is a vast

literature

on

the

cut

polyhedra; references will be given

throughout

the

text

when appropriate. Let us

mention

a

few

areas where these

polyhedra

arise.

The

cut

polytope comes up

in

connection

with

the

following

basic geometric question:

What

are

the

linear inequalities

that

are satisfied by

the

pairwise angles of a set of vectors ?

In

fact,

the

inequalities valid for

the

cut

polytope

CUT~

yield valid relations for

the

pairwise angles

among

a

set

of

n

unit

vectors (see Sections 6.4

and

31.2). As will be explained

in

the

cut

cone arises

naturally

in

the

context of £l-metrics.

On

the

other

hand,

the

cut

polytope

also plays

an

important

role in combinatorial optimization, as

it

permits

to formulate

the

max-cut problem. Given weights w =

(Wij)

E

JRE

n

associated

with

the

pairs

ij

E En,

the

max-cut

problem consists of finding a

cut

8(8) whose weight w

T

8(8)

is

as large as possible. Hence,

it

is

the

problem:

(4.1.4)

max

w

T

8(8)

s.t. 8

<;;;;

V

n

,

which

can

be reformulated as

an

optimization

problem over

the

cut

polytope:

max

wTx

s.t. x E

CUT~.

This

is a

hard

problem,

for which no algorithm

is

known

that

runs

in a

polynomial

number

of

steps

(polynomial in n

and

the

size of w); see Section 4.4.

The

max-

cut

problem

has

many

applications

in

various fields. For instance,

the

problem

of

determining

ground

states

of

spin

glasses in

statistical

physics, or

the

problem

of

minimizing

the

number

of vias

subject

to

assignment

and

layer preferences in

VLSI

circuit

design,

can

both

be formulated as instances of

the

max-cut

problem.

These

two applications are

treated

in

detail

in

Barahona,

Grotschel,

Junger

and

Reinelt [1988]. We expose

the

application to

spin

glasses

in

Section 4.5.

Other

applications

and

connections are mentioned

in

Section 5.1,

within

the

framework

of

unconstrained

boolean

quadratic

programming.

The

reader

may

consult

the

survey

paper

by Poljak

and

Tuza

[1995]

for more information

about

max-cut

and

the

annotated

bibliography by

Laurent

[1997a] for detailed references.

2We will

use

later

(in

Sections

25.3

and

27.3)

the

notation

CUT

(G)

and

cUTD(G)

for

denoting

the

projections

of

cUTn

and

cUT~

on

the

subspace

indexed

by

the

edge

set

of

a

graph

G.

It

should

not

be

confused

with

the

notation

cUT(X)

and

cUTD(X)

which

stands

for

the

cut

polyhedra

of

the

complete

graph

with

node

set

X.

4.2 fll-Spaces

39

4.2

fl-Spaces

Every

member

d

of

the

cut

cone

CUT

n defines a

semimetric

on

n points, as

it satisfies all

the

triangle inequalities (3.1.1). Hence a

natural

question is

the

characterization

of

the

semimetrics

that

belong to

the

cut

cone.

The

main

result

is

that

a

semimetric

belongs to

the

cut

cone

if

and

only

if

it

is isometrically

fll-embeddable, a

result

first found

in

Assouad [1980b]. Several

other

equivalent

characterizations

are

stated

in

Theorem

4.2.6.

The

results

3

in

this

section are

essentially

taken

from Assouad [1980b]

and

from Assouad

and

Deza [1982]. We

start

with

several

intermediate

results.

Proposition

4.2.1.

Let

d =

(dij)r":;i<j":;n

E

JRE

n

•

The following assertions

are

equivalent.

(i) d E

CUTn

(resp. d E

CUT~).

(ii) There exist a measure space (resp. a probability space) (fl, A,

JL)

and events

AI'

...

'

An

E A such that dij = JL(Ai6Aj) for aliI:::; i < j

:::;

n.

Proof. (i)

==>

(ii) Suppose

that

dE

CUT

n

.

Then,

d = L

>-'s8(S)

,

S<:;;{l,

...

,n}

where

>-'s

~

0 for all S. We define a measure space (fl,

A,

JL)

in

the

following

way: Let

fl

denote

the

family of subsets

of

{I,

...

,n},

let A denote

the

family

of

subsets

of

fl,

and

let

JL

denote

the

measure

on

A defined by

JL(A)

:=

L

>-'s

SEA

for each A E A (i.e., A

is

a collection

of

subsets

of

{I,

...

,n}).

Set

Ai

:=

{S E fl

liE

S}.

Then,

JL(Ai

6A

j)=JL({SEfl:lsn{i,j}I=I})=

L >-'s=d

ij

,

sE!1:lsn{i,j}I=1

for all 1

:::;

i < j

:::;

n.

Moreover,

if

d E

CUT~,

then

Ls

>-'s

=

1,

i.e.,

JL(fl)

=

1,

which shows

that

(fl, A,

JL)

is a probability space.

(ii)

==>

(i) Conversely, suppose

that

d

ij

= JL(Ai6Aj) for 1

:::;

i < j

:::;

n, where

(fl,

A,

JL)

is a measure space

and

AI,

...

,An

EA.

Set

AS

:=

n

Ai

n n (fl \

Ai)

iES

i~S

3The

result

from

Proposition

4.2.1 was

already

established

by

Avis [1977].

40

Chapter

4.

The

Cut

Cone

and

f

1

-Metrics

for each S

<:;;;

{I,

...

,n}.

Then,

Ai

= U

AS,

Ai

6A

j = U

As

and

0 =

UA

s

.

SliES

51

ISn{i,j}l=l 5

Therefore,

d = L /L(AS)b(S),

SS:;{l,

...

,n}

which shows

that

d belongs to

the

cut

cone

CUT

n

.

Moreover,

if

(0,

A,

/L)

is a

probability

space, i.e.,

if

/L(O)

= 1,

then

Ls

/L(A

S

)

= 1, implying

that

d belongs

to

the

cut

polytope

CUT~.

I

Proposition

4.2.2.

Let d E

~En

and (Vn,

d)

be

the associated distance space.

The following assertions

are

equivalent.

(i)

dE

CUT

n

.

(ii) (Vn,d) is f1-embeddable, i.e., there exist n vectors

U1"",U

n

E

~m

(for

some

m)

such that dij

=11

Ui

-

Uj

IiI

for aliI:::; i < j

:::;

n.

Proof. (i)

~

(ii)

Suppose

that

d E

CUT

n

.

Then,

d = L Akb(Sk),

l~k~m

where AI,

...

,

Am

::::

0

and

Sl,

...

,

Sm

<:;;;

V

n

. For 1

:::;

i

:::;

n,

define

the

vector

Ui

E

~m

with

components

(Ui)k

=

Ak

if

i E Sk

and

(Ui)k

= 0 otherwise, for

1

:::;

k

:::;

m.

Then,

dij

=11

Ui

-

Uj

III

for 1

:::;

i < j

:::;

n.

This

shows

that

(Vn,

d)

is f

1

-embeddable.

(ii)

~

(i) Suppose

that

(Vn'

d)

is f

1

-embeddable, i.e.,

that

there

exist n vectors

U1,

...

,

Un

E

~m

(for some m

::::

1)

such

that

dij

=11

Ui

-

Uj

IiI,

for 1

:::;

i < j

:::;

n.

We show

that

d E

CUT

n

.

By

additivity

of

the

f

1

-norm,

it suffices to show

the

result

for

the

case m = 1. Hence,

we

can

suppose

that

dij =

lUi

-

Uj

I

where

U1,

...

,

Un

E R

Without

loss

of

generality,

we

can

also suppose

that

U1

:::;

U2

:::;

...

:::;

Un.

Then,

it is easy

to

check

that

d=

L

(Uk+1-

U

k)b({1,2,

...

,k-l,k}).

1~k~n-1

This

shows

that

dE

CUT

n

.

I

Remark

4.2.3.

The

proof

of

Proposition

4.2.2 shows,

in

fact,

the

following

result:

If

a distance d

on

Vn

can

be decomposed as a nonnegative linear combi-

nation

of

m

cut

semimetrics, i.e.,

if

d =

Lk=l

Akb(Sk) where

Ak

::::

0 for all

k,

then

d is fl"-embeddable. I

There

is a characterization for hypercube

embeddable

semimetrics, analogous

to

that

of

Proposition

4.2.2.

Proposition

4.2.4.

Let d E

~En

and (Vn,

d)

be

the associated distance space.

The following assertions

are

equivalent.

41

(i) d = L

>"s6(S)

for

some

nonnegative integers

>"5.

SC;;Vn

(ii)

(V

n

, d)

is hypercube embeddable, i.e., there exist n vectors

U1,

...

,

Un

E

{o,I}m

(for

some

m)

such

that

d

ij

=11

Ui

-

Uj

III

for

aliI

S i < j S

n.

(iii) There exist a finite

set

nand

n subsets

AI,

...

,

An

of

n

such

that

d

ij

IAi6Aji

for

aliI

S i < j S

n.

(iv)

(V

n

, d)

is

an

isometric

subspace

of

(zm, d

l,

) for

some

integer m

2':

1.

Proof.

The

proof

of (i)

¢==>

(ii)

is

analogous to

that

of

Proposition

4.2.2.

Namely, for (i)

==>

(ii), assume d =

2::k=16(Sk)

(allowing repetitions). Con-

sider

the

binary

n x m

matrix

M whose columns are

the

incidence vectors

of

the

sets S1,

...

, Sm.

If

Ur,

...

,

Un

denote

the

rows of

M,

then

d

ij

=11

Ui

-

Uj

111

holds, providing

an

embedding

of

(V

n

,

d)

in

the

hypercube

of

dimension

m.

Con-

versely, for (ii)

==>

(i), consider

the

matrix

M whose rows are

the

n given vectors

U1,

...

,

Un.

Let S

1,

...

, Sm be

the

subsets of

{I,

...

,

n}

whose incidence vectors

are

the

columns of

M.

Then,

d =

2::k=l

6(Sk) holds, giving a decomposition of

d as a nonnegative integer combination of

cut

semimetrics.

The

assertion (iii)

is

a reformulation of (ii),

the

implication (iii)

==>

(iv) is ob-

vious,

and

(iv)

==>

(i) follows from

the

proof

of

the

implication (ii)

==>

(i) in

Proposition

4.2.2. I

We now make

the

link

with

L

1

-spaces.

Lemma

4.2.5.

Let

(X,

d)

be

a distance space. The following

assertions

are

equivalent

(i)

(X,

d) is L1 -embeddable.

(ii)

(X,

d) is a subspace

of

a measure

semimetric

space

(.AI"

dl') for

some

mea-

sure space

(n,.A,

JL).

Proof.

The

implication (ii)

=}

(i) is clear, since

(.AI"

dl') is a subspace of

Ll(n,.A,

JL).

We check (i)

=}

(ii).

It

suffices to show

that

each space

Ll(n,.A,

JL)

is

a

subspace

of (Bv, d

v

) for some measure space (T, B, v). For this, set

T:=

n x

~

B

:=

.A x n where n is

the

family of Borel subsets of

R,

and

v

:=

JL

(1)

>..

where>.. is

the

Lebesgue

measure

on R For f E

L1(n,.A,

JL),

let

E(f)

= {(w, s) E

nxR

Is>

f(w)}

denote

its

epigraph.

Then,

the

mappingf

>------+

E(f)6E(O)

provides

an

iso-

metric

embedding

from

Ll

(n,.A,

JL)

to (Bv, d

v

),

since

II

f - gill =

v(E(f)6E(g))

holds. I

The

the

equivalent characterizations

that

have

been

obtained

for

the

members

of

the

cut

cone

CUT

n

.

Theorem

4.2.6.

Let

d E

REn

and

(V

n

, d)

be

the associated distance space.

The

following

assertions

are equivalent.

(i)

dE

CUT

n

.

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

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