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

Algorithms and Combinatorics

Vo l u m e 1 5

Editorial Board

R. L. Graham, La Jolla

B. Korte, Bonn

L. Lovász, Budapest

A. Wigderson, Princeton

G. M. Ziegler, Berlin

123

Michel Marie Deza · Monique Laurent

Geometry of Cuts and Metrics

ISSN 0937-5511

ISBN 978-3-540-61611-5 (hardcover) e-ISBN 978-3-642-04295-9

ISBN 978-3-642-04294-2 (softcover)

DOI 10.1007/978-3-642-04295-9

Springer Heidelberg Dordrecht London New York

Library of Congress Control Number: 2009939941

c

 Springer-Verlag Berlin Heidelberg 1997, First softcover printing 2010

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is

concerned, specificall the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting,

reproduction on microfil or in any other way, and storage in data banks. Duplication of this publication

or parts thereof is permitted only under the provisions of the German Copyright Law of September 9,

1965, in its current version, and permission for use must always be obtained from Springer. Violations

are liable to prosecution under the German Copyright Law.

The use of general descriptive names, registered names, trademarks, etc. in this publication does not

imply, even in the absence of a specifi statement, that such names are exempt from the relevant protective

laws and regulations and therefore free for general use.

Cover design: deblik, Berlin

Printed on acid-free paper

Springer is part of Springer Science+Business Media (www.springer.com)

Michel Marie Deza

Laboratoire Interdisciplinaire

de G

´

eom

´

etrie Appliqu

´

ee

Ecole Normale Sup

´

erieure (ENS)

45 rue d’Ulm

75230 Paris Cedex 05

France

michel.deza@ens.fr

and

Japan Advanced Institute of Science

and Technology (JAIST)

School of Information Science

1-1 Asahidai, Nomi

Ishikawa 923-1292

Japan

Monique Laurent

CWI

Science Park 123

1098 XG Amsterdam

The Netherlands

M. Laurent@cwi.nl

Preface

Cuts

and

metrics are well-known

and

central objects

in

graph

theory, combina-

torial

optimization

and, more generally, discrete mathematics.

They

also occur

in

other

areas

of

mathematics

and

its applications such as distance geometry,

the

geometry

of

numbers, combinatorial

matrix

theory,

the

theory

of

designs,

quantum

mechanics,

statistical

physics, analysis

and

probability theory. Indeed,

cuts

are

many

faceted objects,

and

they

can

be

interpreted

as

graph

theoretic

objects, as metrics, or as probabilistic pairwise correlations.

This

accounts for

their

fecund versatility.

Due

to

the

wealth

of

results,

in

writing

this

book

we

had

to

make a selection.

We focus on

polyhedral

and

other

geometric aspects

of

cuts

and

metrics.

Our

aim

is

to

collect different results, established

within

diverse

mathematical

fields,

and

to

present

them

in

a unified framework. We

try

to

show how these various

results are tied together via

the

notions

of

cuts

and

metrics and, more specifically,

the

cut

cone

and

the

cut

polytope. One

of

our

guidelines for selecting topics

was to concentrate on those aspects

that

are less well-known

and

are

not

yet

covered

in

a unified way elsewhere.

The

book has, moreover,

been

written

with

a special

attention

to interdisciplinarity. For

this

reason, while some topics are

treated

in

full detail

with

complete proofs, some

other

topics are only touched,

by mentioning results

and

pointers to further information

and

references.

The

book

is

intended as a source

and

reference work for researchers

and

graduate

students

interested

in

discrete

mathematics

and

its interactions

with

other

areas of

mathematics

and

its applications. In particular,

it

is

of

interest for

those specializing

in

algebraic

and

geometric combinatorics

and

in combinatorial

optimization.

The

book

is subdivided into

five

parts,

in

which

we

consider

the

following

topics: fi1-metrics

and

hypercube embeddable metrics, hypermetrics

and

Delau-

nay polytopes

in

lattices,

the

metric

structure

of

graphs, designs

in

connection

with

hypercube

embeddings,

and

further geometric questions linked

with

cut

polyhedra.

We do

not

cover extensively

the

topic

of

optimization. Indeed, research on

cuts

and

metrics

in

this

direction

is

already well-documented. Some survey

papers

are available; for instance, by Frank

[1990]

on multicommodity flows

and

by

Poljak

and

Tuza

[1995]

on

the

max-cut problem. Nevertheless,

we

do present

some

of

the

recent breakthroughs. For instance,

we

discuss

the

new semidefinite

programming

approximative algorithm of Goemans

and

Williamson, as well as

VI

Preface

the

result of Bourgain on Lipschitz £l-embeddings

with

small distortion,

and

its

application

to

approximating

multicommodity flows by Linial, London

and

Rabinovich. Moreover,

we

mention

en

route

a

number

of

further

results relevant

to

the

max-cut

problem

and

binary

matroids.

We

made

each

of

the

five

parts

of

the

book as self-contained as possible;

in

principle, each

of

them

can

be read independently of

the

other. Moreover,

we

have chosen a

common

labeling system for all items such as theorems, examples,

figures, etc.,

in

order

to

simplify

the

search

throughout

the

text.

Some portions

of

text

that

contain side information

or

lengthy proofs are

in

small

print

and

can

be avoided

at

first reading.

The

part

of

the

book

treating

links

with

the

geometry of numbers, is based on

a survey

paper

coauthored by

the

authors

with

V.P. Grishukhin

of

the

Academy

of

Sciences of Russia

in

Moscow

(cf.

Deza, Grishukhin

and

Laurent

[1995]). We

are grateful

to

Slava Grishukhin for kindly

permitting

us to include

the

material

in

this

book.

There

are several

institutions

that

we

wish

to

thank

for

their

support

while

we

were working on

the

book. We would particularly like

to

thank

our

home

institute

LIENS

at

the

Department

of

Mathematics

and

Computer

Science

of

Ecole Normale Superieure

in

Paris, for offering us a helpful environment

and

stimulating

working conditions.

The

help of Jacques Beigbeder

in

solving various

1l\TEX

puzzles

in

the

presentation of

the

book was greatly appreciated.

The

first

author

is grateful to

the

Tokyo

Institute

of Technology

and

the

Institute

of

Mathematics

of

the

Academia Sinica

in

Taipei.

The

second

author

is very

thankful

to

CWI

(Center

for

Mathematics

and

Computer

Science)

in

Amsterdam

for

the

hospitality

and

fruitful interactions on

the

occasion of several long-term

visits. We wish also

to

express special

thanks

to

the

University of Augsburg

and

the

Konrad-Zuse-Zentrum

in

Berlin;

in

particular,

to

Martin

Grotschel for

the

many

stimulating

discussions during

our

visits

and

for

sharing

with

us his

time

and

enthusiasm

on

the

topic.

We are grateful to several further people for useful discussions

and

cooper-

ation

on

the

topic

of

this

book.

In

particular,

the

first

author

thanks

warmly

Jin

Akiyama,

Peter

Cameron, Walter Deuber, Antoine Deza, Komei

Fukuda,

Marie Grindel, Zeev Jabotinsky, Ko-Wei Lih, Sergey Shpectorov, Navin Singhi,

Ivo Rosenberg,

Pierre

Rosenstiehl,

and

Maximillian Voloshin.

The

second au-

thor

is

very grateful

to

Lad

Lovasz for insightful advice

and

for offering her

the

opportunity

to

present

parts

of

the

material

at

the

Department

of

Computer

Science

of

Yale University. She also

thanks

David Avis, Hans-Jiirgen

Bandelt,

Victor

Chepoi, Michele Conforti,

Caterina

De Simone, Cid De Souza, Bert Ger-

ards, Franc;ois

Laburthe,

Franz Rendl, Lex Schrijver,

Andras

Sebo,

and

Bruce

Shepherd.

We have a special memory

to

our

dear

friend

and

colleague

Svata

Poljak,

who was always enthusiatic, generous

and

eager

to

share interest

and

questions

on

this

topic.

Contents

1.

Outline

of

the

Book

1.1

Outline

of

Part

I.

Measure Aspects: e1-Embeddability

and

Probability

. . . . . . . . . . . . . . . . . . . . .

1.2

Outline

of

Part

II. Hypermetric Spaces:

an

Approach

via

Geometry

of

Numbers

..............

.

1.3

Outline

of

Part

III. Embeddings

of

Graphs

.....

.

1.4

Outline

of

Part

IV. Hypercube Embeddings

and

Designs

1.5

Outline

of

Part

V.

Facets

of

the

Cut

Cone

and

Polytope

2.

Basic

Definitions

2.1

Graphs

....

.

2.2

Polyhedra

..

.

1

2

4

6

7

8

11

14

2.3 Algorithms

and

Complexity

18

2.4 Matrices . . . . . . . . . . .

19

Part

I.

Measure

Aspects:

C1-Embeddability

and

Probability

23

3.

Preliminaries

on

Distances

27

3.1 Distance Spaces

and

ep-Spaces

27

3.2 Measure Spaces

and

Lp-Spaces .

32

4.

The

Cut

Cone

and

e1-Metrics

37

4.1

The

Cut

Cone

and

Polytope . 37

4.2 e1-Spaces . . . . . . . . . . . .

39

4.3 Realizations, Rigidity, Size

and

Scale

43

4.4 Complexity

Questions.

. . . . . . . .

48

4.5 An Application to

Statistical

Physics

51

5.

The

Correlation

Cone

and

{O,I}-Covariances

53

5.1

The

Correlation Cone

and

Polytope

53

5.2

The

Covariance Mapping

55

5.3 Covariances

....

58

5.4

The

Boole

Problem

. . .

61

VJII

Contents

6.

Conditions

for

LJ-Embeddability

67

6.1

Hypermetric

and

Negative

Type

Conditions

6.1.1

Hypermetric

and

Negative

Type

Inequalities 67

6.1.2

Hypermetric

and

Negative

Type

Distance Spaces

71

6.1.3 Analogues for Covariances . . . . . . . . . . . . .

72

6.2

Characterization

of

L

2

-Embeddability . . . . . . . . . . 73

6.2.1

Schoenberg's Result

and

Cayley-Menger

Determinants

74

6.2.2

Menger's Result 78

6.2.3

Further

Characterizations . . . . . . . 80

6.3

A

Chain

of

Implications.

. . . . . . . . . . . 82

6.4

An

Example:

The

Spherical Distance Space 86

6.5

An

Example:

Kalmanson

Distances

91

7.

Operations

93

7.1

The

Gate

Extension

Operation.

93

7.2

The

Antipodal

Extension

Operation.

94

7.3

The

Spherical Extension

Operation

. 97

7.4

An

Example:

The

Cocktail-Party

Graph

98

7.5

The

Direct

Product

and

Tensor

Product

Operations.

101

7.6

The

I-Sum

Operation

. . . . . . . . . . . . . . . . . . 103

8.

L1-Metrics

from

Lattices,

Semigroups

and

Normed

Spaces

105

8.1

LJ-Metrics from Lattices . . . . 105

8.2

LJ-Metrics from Semigroups . . 107

8.3

LrMetrics

from Normed Spaces 109

9.

Metric

Transforms

of

LI-Spaces

113

9.1

The

Schoenberg Transform 115

9.2

The

Biotope Transform 118

9.3

The

Power Transform 120

10.

Lipschitz

Embeddings

125

10.1

Embeddings

with

Distortion.

. . . . . . . . . . . . . . . . . 125

10.2

The

Negative

Type

Condition

for Lipschitz Embeddings . . 130

10.3

An

Application for Approximating Multicommodity Flows 132

11.

Dimensionality

Questions

for

fJ-Embeddings

11.1

fJ-Embeddings

in Fixed Dimension

......

.

11.1.1

The

Order

of

Congruence

of

the

f1-Space .

11.1.2 A Canonical Decomposition for Distances

11.1.3

Embedding

Distances

in

the

fJ-Plane

11.2

On

the

Minimum

fp-Dimension

.........

.

139

141

144

147

156

Contents

12.

Examples

of

the

Use

of

the

L1-Metric

12.1

The

L1-Metric

in

Probability

Theory.

ix

161

12.2

The

f1-Metric

in

Statistical

Data

Analysis.

. . . . . . . .

..

162

12.3

The

f1-Metric

in

Computer

Vision

and

Pattern

Recognition.

163

Part

II.

Hypermetric

Spaces:

an

Approach

via

Geometry

of

Numbers

167

13.

Preliminaries

on

Lattices

13.1 Distance Spaces

....

13.2 Lattices

and

Delaunay Polytopes

175

177

13.2.1 Lattices

..........

177

13.2.2 Delaunay Polytopes . . . . 179

13.2.3 Basic Facts on Delaunay Polytopes 182

13.2.4

Construction

of

Delaunay

Polytopes.

184

13.2.5 Additional Notes

...........

187

13.3 Finiteness

of

the

Number

of

Types

of

Delaunay Polytopes 189

14.

Hypermetrics

and

Delaunay

Polytopes

193

14.1 Connection between Hypermetrics

and

Delaunay Polytopes 193

14.2 Polyhedrality

of

the

Hypermetric Cone 199

14.3 Delaunay Polytopes

in

Root

Lattices . 206

14.4

On

the

Radius

of

Delaunay Polytopes .

211

15.

Delaunay

Polytopes:

Rank

and

Hypermetric

Faces

217

15.1

Rank

of

a Delaunay Polytope . . . . . 217

15.2 Delaunay Polytopes Related

to

Faces.

222

15.2.1

Hypermetric

Faces

.......

222

15.2.2

Hypermetric

Facets . . . . . . . 226

15.3

Bounds

on

the

Rank

of

Basic Delaunay Polytopes 230

16.

Extreme

Delaunay

Polytopes

235

16.1

Extreme

Delaunay Polytopes

and

Equiangular

Sets

of

Lines.

236

16.2

The

Schliifli

and

Gosset Polytopes are

Extreme.

. . . . .

..

239

16.3

Extreme

Delaunay Polytopes

in

the

Leech

Lattice

A24

. .

..

244

16.4

Extreme

Delaunay Polytopes

in

the

Barnes-Wall

Lattice

A16

245

16.5

Extreme

Delaunay Polytopes

and

Perfect Lattices

17.

Hypermetric

Graphs

17.1 Characterizing Hypermetric

and

f1-Graphs

17.2

Hypermetric

Regular

Graphs

.

17.3

Extreme

Hypermetric

Graphs

. . . . . . . .

248

251

252

262

269

x

Contents

Part

III.

Isometric

Embeddings

of

Graphs

275

18.

Preliminaries

on

Graphs

19.

Isometric

Embeddings

of

Graphs

into

Hypercubes

19.1 Djokovic's

Characterization

19.2

Further

Characterizations

19.3 Additional Notes

.....

.

279

283

286

293

20.

Isometric

Embeddings

of

Graphs

into

Cartesian

Products

297

20.1 Canonical Metric Representation

of

a

Graph

297

20.2

The

Prime

Factorization

of

a

Graph

. .

..

20.3 Metric Decomposition

of

Bipartite

Graphs.

20.4 Additional Notes

..............

.

21.

'pI-Graphs

21.1 Results on 'pI-Graphs.

305

306

308

313

21.2

Construction

of

G via

the

Atom

Graph

316

21.3 Proofs . . . . . . . . . 322

21.4 More

about

'pI-Graphs.

. . . . . . . . . 325

Part

IV.

Hypercube

Embeddings

and

Designs

331

22.

Rigidity

of

the

Equidistant

Metric

335

23.

Hypercube

Embeddings

of

the

Equidistant

Metric

341

23.1 Preliminaries on

Designs.

. . . . . 341

23.1.1 (r,

A,

n)-Designs

and

BIBD's 341

23.1.2 Intersecting Systems . . . 344

23.2

Embeddings

of

2tl

n

and

Designs . 345

23.3

The

Minimum h-Size

of

2tl

n

. . .

347

23.4 All

Hypercube

Embeddings

of

2tl

n

for Small

n,

t . 350

24.

Recognition

of

Hypercube

Embeddable

Metrics

353

24.1

Preliminary

Results . . . . . . 354

24.2 Generalized

Bipartite

Metrics.

. . . . . . 357

24.3 Metrics

with

Few

Values.

. . . . . . . . . 362

24.3.1 Distances

with

Values 2a, b

(b

odd) 363

24.3.2 Distances

with

Values a,

b,

a + b (a,b odd) 365

24.3.3 Distances

with

Values

b,

2a, b + 2a

(b

odd, b < 2a) 367

24.4

Truncated

Distances

of

Graphs

. . . . . . 370

24.4.1

The

Class

of

Graphs

11k

..

. . . . 372

24.5 Metrics

with

Restricted

Extremal

Graph.

375

Contents

25.

Cut

Lattices,

Quasi

h-Distances

and

Hilbert

Bases

25.1

Cut

Lattices

.....

25.2

Quasi

h-Distances

..

25.3

Hilbert

Bases

of

Cuts

Part

V.

Facets

of

the

Cut

Cone

and

Polytope

26.

Operations

on

Valid

Inequalities

and

Facets

26.1

Cut

and

Correlation

Vectors

26.2

The

Permutation

Operation

......

.

26.3

The

Switching

Operation

. . . . . . . .

26.3.1 Switching: A

General

Definition.

26.3.2 Switching:

Cut

Polytope

versus

Cut

Cone

26.3.3

The

Symmetry

Group

of

the

Cut

Polytope

26.4

The

Collapsing

Operation

26.5

The

Lifting

Operation

26.6 Facets

by

Projection

xi

381

385

391

395

401

403

405

409

410

413

416

21.

Triangle

Inequalities

421

27.1 Triangle Inequalities for

the

Correlation

Polytope.

423

27.2

Rooted

Triangle Inequalities

............

424

27.2.1

An

Integer

Programming

Formulation

for

Max-Cut

425

27.2.2 Volume

of

the

Rooted

Semimetric

Polytope

426

27.2.3

Additional

Notes . . . . . . . . . . . 428

27.3

Projecting

the

Triangle Inequalities

........

430

27.3.1

The

Semimetric

Polytope

of

a

Graph

. . . . 431

27.3.2

The

Cut

Polytope

for

Graphs

with

no K5-Minor . 434

27.4

An

Excursion

to

Cycle

Polytopes

of

Binary

Matroids

. 435

27.4.1

Preliminaries

on

Binary

Matroids

. . . . 436

27.4.2

The

Cycle Cone

and

the

Cycle

Polytope

438

27.4.3 More

about

Cycle

Spaces.

. . . . . . . . 441

28.

Hypermetric

Inequalities

445

28.1

Hypermetric

Inequalities: Validity 445

28.2

Hypermetric

Facets

........

447

28.3

Separation

of

Hypermetric

Inequalities.

453

28.4

Gap

Inequalities . . . . . . . . . . . . . 457

28.4.1 A Positive Semidefinite

Relaxation

for

Max-Cut

459

28.5

Additional

Notes . . . . . . . . . . . . . . . . . . . . . 463

29.

Clique-Web

Inequalities

467

29.1

Pure

Clique-Web Inequalities . . . . . . . . . 467

29.2

General

Clique-Web Inequalities . . . . . . . 470

29.3 Clique-Web Inequalities: Validity

and

Roots

472

29.4 Clique-Web

Facets.

. . . . . . . . . . . . . . 477

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

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