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

570

Bibliography

[1976]

D. McCarthy, R.C. Mullin,

P.J.

Schellenberg, R.G.

Stanton,

and

S.A. Vanstone.

An

approximation

to

a projective plane of

order

6.

Ars

Combinatoria, 2:169-189,

1976.

[350]

[1977] D. McCarthy, R.C. Mullin,

P.J.

Schellenberg, R.G.

Stanton,

and

S.A. Vanstone.

Towards

the

nonexistence of (7, I)-designs with 31 varieties. In B.L. Hartnell

and

H.C. Williams, editors, Proceedings

of

the Sixth Manitoba Conference on

Numeri-

cal Mathematics, volume 18

of

Congressus Numerantium, pages 265-285. Utilitas

Mathematica,

Winnipeg, 1977.

[350]

[1977] D.

McCarthy

and

S.A. Vanstone. Embedding

(r,

I)-designs in finite projective

planes.

Discrete Mathematics, 19:67-76, 1977.

[347]

[1972] W.B. McRae

and

E.R. Davidson. Linear inequalities for density matrices II.

Journal

of

Mathematical Physics, 13:1527-1538,1972. [54,64,69,405,477,503]

[1928]

K.

Menger. Untersuchungen iiber allgemeine Metrik. Mathematische

Annalen,

100:75-163,1928.

[25,73,78,141]

[1931]

K.

Menger. New foundation of Euclidean geometry.

American

Journal

of

Math-

ematics, 53:721-745, 1931. [25,78,80]

[1954]

K.

Menger. Geometrie Generale. Memorial des Sciences

Mathematiques

CXXIV,

Academie des Sciences de

Paris,

Gauthier-Villars, Paris, 1954. [25,77,78]

[1987]

M.M. Mestechkin. On

the

diagonal N-representability problem. In R.M.

Erdahl

and

V.H. Smith, editors,

Density

Matrices and

Density

Functionals, pages 77-87.

D. Reidel, 1987. [64,69]

[1987]

M. Mezard, G. Parisi,

and

M.A. Virasoro. Spin Glass Theory and Beyond. World

Scientific, Singapore,

1987.

[51]

[1990] W.H. Mills. Balanced incomplete block designs

with>'

=

1.

Congressus

Numer-

antium, 73:175-180, 1990.

[343]

[1980] H.M. Mulder. The Interval Function

of

a Graph.

Mathematical

Centre

Tracts

132,

Mathematisch

Centrum,

Amsterdam, 1980.

[309]

[1982]

H.M. Mulder. Interval-regular graphs. Discrete Mathematics, 41:253-269, 1982.

[309]

[1987]

A.

Neumaier. Some relations between roots, holes

and

pillars. European Journal

of

Combinatorics, 8:29-33, 1987.

[237]

[1941]

J.

von Neumann

and

I.J.

Schoenberg. Fourier integrals

and

metric geometry.

Transactions

of

the

American

Mathematical Society, 50:226-251, 1941. [113,117]

[1994]

A.

Nilli.

On

Borsuk's problem. In

H.

Barcelo

and

G. Kalai, editors, Jerusalem

Combinatorics

'93, volume 178 of Contemporary Mathematics, pages 209-210,

1994.

[512J

[1987J

A.

Noda. Generalized

Radon

transform

and

Levy's Brownian motion I

and

II.

Nagoya Mathematical Journal, 105:71-87

and

89-107, 1987.

[162J

[1989J

A.

Noda.

White

noise representations of some Gaussian

random

fields. The

Bulletin

of

Aichi

University

of

Education, 38:35-45, 1989.

[162J

[1992]

S.P. Novikov, S.S. Ryshkov, N.P. Dolbilin,

and

M.A. Shtan'ko, editors. Discrete

Geometry and Topology. Proceedings

of

the Steklov

Institute

of

Mathematics, 196

(4),1992.

[171J

[1972]

G.I. Orlova

and

Y.G. Dorfman. Finding

the

maximum

cut

in a

graph.

Engineering

Cybernetics, 10:502-506, 1972.

[48,52J

[1992]

J.G.

Oxley. Matroid Theory. Oxford University Press, London, 1992.

[436J

Bibliography

571

[1989]

M.W.

Padberg.

The

boolean quadric polytope: some characteristics, facets

and

relatives. Mathematical Programming, 45:139-172, 1989. [54,425,435,453,539]

[1995]

M.W.

Padberg.

Personal communication, 1995.

[506]

[1982]

M.W.

Padberg

and

M.R.

Rao.

Odd

minimum

cut-sets

and

b-matchings. Mathe-

matics

of

Operations Research, 7:67-80, 1982.

[442]

[1982] C.H.

Papadimitriou

and

K.

Steiglitz. Combinatorial Optimization: Algorithms

and Complexity. Prentice-Hall, Englewood Cliffs, New Jersey, 1982.

[18]

[1976]

B.A.

Papernov.

On

existence of multi commodity flows (in Russian). Studies

in

Discrete Optimization, Nauka, Moscow, pages 230-261, 1976.

[375]

[1982) D. Penny, L.R. Foulds,

and

M.D. Hendy. Testing

the

theory

of

evolution by

comparing

phylogenetic trees

constructed

from five different

protein

sequences.

Nature, 297:197-200, 1982.

[310)

[1972)

J.R.

Pierce. Network for block switching

of

data.

The

Bell

System

Technical

Journal, 51:1133-1145,1972.

[278)

[1986)

1.

Pitowsky.

The

range

of

quantum

probability. Journal

of

Mathematical Physics,

27:1556-1565,1986. [54,59)

[1989)

1.

Pitowsky.

Quantum

Probability -

Quantum

Logic, volume 321

of

Lecture Notes

in

Physics. Springer-Verlag, Berlin, 1989.

[54)

[1991]

1.

Pitowsky.

Correlation

polytopes:

their

geometry

and

complexity. Mathematical

Programming, 50:395-414, 1991. [54,61,64,69,405,477]

[1993] S.A.

Plotkin

and

E.

Tardos. Improved

bounds

on

the

max-flow min-cut

ratio

for

multicommodity

flows. Proceedings

of

the 25th

Annual

ACM

Symposium

on the

Theory

of

Computing, pages

691-697,1993.

[134]

[1995] S.

Poljak

and

F.

Rend!. Nonpolyhedral relaxations

of

graph-bisection problems.

SIAM

Journal on Optimization, 5:467-487, 1995.

[460)

[1987)

S.

Poljak

and

D. Turzik.

On

a facet

of

the

balanced

subgraph

polytope. Casopis

Pro Pestovani Matematiky, 112:373-380, 1987.

[496]

[1992J

S.

Poljak

and

D. Turzik.

Max-cut

in

circulant

graphs.

Discrete Mathematics,

108:379-392, 1992. [496,497]

[1995] S.

Poljak

and

Z.

Tuza.

Maximum

cuts

and

largest

bipartite

subgraphs.

In

W.

Cook, L.

Lovisz,

and

P.D. Seymour, editors, Combinatorial Optimization, vol-

ume

20

of

DIMACS

Series

in

Discrete Mathematics and Theoretical

Computer

Science, pages 181-244. American

Mathematical

Society, 1995. [v,38,548J

[1990J

K.F.

Prisacaru,

P.S. Soltan,

and

V. Chepoi.

On

embeddings

of

planar

graphs

into

hypercubes

(in Russian). Buletinal Academiei

de

Stiinte

a

R.S.S.

Moldovenesti,

Matematica, 1:43-50, 1990.

[329J

[1991J

S.T. Rachev. Probability Metrics and the Stability

of

Stochastic Models.

John

Wiley & Sons, Chichester, 1991. [161,162]

[1955J

R.A.

Rankin.

On

packing spheres

in

Hilbert space. Proceedings

of

the Glasgow

Mathematical Association, 2:145-146, 1955.

[85]

[1993J

L. Reid

and

X. Sun. Distance matrices

and

ridge function

interpolation.

Canadian

Journal

of

Mathematics, 45:1313-1323, 1993.

[84J

[1964)

C.A. Rogers. Packing and Covering, volume 54

of

Cambridge tracts

in

Mathe-

matics

and Mathematical Physics. Cambridge University

Press,

Cambridge, 1964.

[172J

[1957)

C.A. Rogers

and

G.C.

Shephard.

The

difference

body

of

a convex body.

Archiv

der Mathematik, 8:220-233, 1957.

[205]

572

Bibliography

[1976J

A.

Rosenfeld

and

A.C. Kak. Digital Picture Processing. Academic

Press,

New

York, 1976.

[163]

[1986J

R.L.

Roth

and

P.M. Winkler. Collapse of

the

metric hierarchy for

bipartite

graphs. European Journal

of

Combinatorics, 7:371-375, 1986. [286,288J

[1966]

W. Rudin. Real and Complex Analysis. McGraw-Hill, New York, 1966.

[32]

[1963J

H.J.

Ryser. Combinatorial Mathematics, volume

14

of The Carus Mathematical

Monographs.

The

Mathematical

Association

of

America, 1963.

[342]

[1979]

S.S. Ryshkov

and

E.P. Baranovskii. Classical

methods

in

the

theory of

lattice

packings. Russian Mathematical Surveys, 34(4):1-68,1979. [172,248]

[1988J

S.S. Ryshkov

and

RM.

Erdahl.

The

empty

sphere

Part

II.

Canadian Journal

of

Mathematics, 40:1058-1073, 1988. [172,188]

[1989J

S.S. Ryshkov

and

RM.

Erdahl. Layerwise construction of L-bodies of

lattices

(in Russian). Uspekhi Matematicheskikh Nauk, 44 (2):241-242, 1989. (English

translation

in: Russian Mathematical Surveys, 44(2):293-294, 1989.)

[185]

[1960]

G. Sabidussi.

Graph

multiplication. Mathematische ZeitschriJt, 72:446-457,1960.

[305]

[1976]

S.

Sahni

and

T. Gonzalez.

P-complete

approximations problems. Journal

of

the

Association for Computing Machinery,

23:555-565, 1976.

[461]

[1990]

R. Scapellato.

On

F-geodetic graphs. Discrete Mathematics, 80:313-325, 1990.

[309]

[1983]

R. Schneider

and

W.

Weil. Zonoids and related topics. In P.M.

Gruber

and

J.M.

Wills, editors, Convexity and its Applications, pages 296-317. Birkhauser-Verlag,

Basel, 1983.

[110]

[1935]

I.J.

Schoenberg. Remarks

to

Maurice Frechet's article "Sur

la

definition axiom a-

tique

d'une

classe d'espace distancies vectoriellement applicable

sur

l'espace de

Hilbert".

Annals

of

Mathematics, 36:724-732, 1935. [25,73,74,89]

[1937]

I.J.

Schoenberg. On

certain

metric spaces arising from Euclidean spaces by a

change of metric

and

their imbedding in Hilbert space.

Annal.~

of

Mathematics,

38:787-793,1937. [25,69,83,113,117]

[1938a]

LJ.

Schoenberg. Metric spaces

and

completely monotone functions. Annals

of

Mathematics, 39:811-841, 1938. [25,69,83,113,114,117J

[1938b]

LJ.

Schoenberg. Metric spaces

and

positive definite functions. Transactions

of

the American Mathematical Society, 44:522-536, 1938. [25,69,74,83,115,117]

[1986] A. Schrijver.

Theory

of

Linear and Integer Programming.

John

Wiley & Sons,

Chichester, 1986. [11,49,428,431]

[1991] A. Schrijver.

Short

proofs on multicommodity flows and cuts. Journal

of

Com-

binatorial Theory B,

53:32-39, 1991.

[376]

[1995] A. Schrijver. Personal communication, 1995.

[150]

[1975]

J.J.

Seidel. Metric problems in elliptic geometry. In L.M. Kelly, editor, The Ge-

ometry of Metric and Linear Spaces,

volume 490 of Lecture Notes in Mathematics,

pages

3243.

Springer-Verlag, Berlin, 1975.

[87]

[1979]

P.D. Seymour. Sums of circuits. J.A. Bondy

and

U.S.R. Murty, editors, Graph

Theory and Related Topics,

pages 341-355. Academic Press, New York, 1979.

[440J

[1981]

P.D. Seymour. Matroids and multicommodity flows. European Journal

of

Com-

binatorics,

2:257-290, 1981. [434,439,440]

[1993J

S.V. Shpectorov.

On

scale embeddings

of

graphs into hypercubes. European

Journal of Combinatorics,

14:117-130, 1993. [100,211,252,313,314,315]

Bibliography 573

[1996] S.V. Shpectorov. Distance-regular isometric subgraphs

of

the

halved cubes.

Preprint,

1996.

[269]

[1989) C.L. Siegel. Lectures on the Geometry of Numbers. Springer-Verlag, Berlin, 1989.

[205]

[1960]

C.

Sperling. Lasung einer elementargeometrischen I)-age von Fejes

T6th.

Archiv

der Mathematik,

11:69-71, 1960.

[514]

[1986] R Stanley.

Two

order polytopes. Discrete and Computational Geometry, 1:9-23,

1986.

[427]

[1986]

Z.I. Szab6.

Hilbert's

fourth problem, I. Advances in Mathematics, 59:185-301,

1986.

[111]

[1987) P. Terwiliger

and

M. Deza. Classification

of

finite connected hypermetric spaces.

Graphs and Combinatorics, 3:293-298, 1987.

[211J

[1952] \V.S. Torgerson. Multidimensional scaling:

I.

theory and method. Psychometrika,

17:401-419,1952.

[81]

[1977]

C.

Toulouse.

Theory

of

the

frustration effect in spin glasses:

I.

Communications

in Physics,

2:115-119, 1977.

[52]

[1987]

I.

Vajda.

Lj-distances

in statistical inference: comparison

of

topological func-

tional

and

statistical

properties.

In

Y. Dodge, editor, Statistical Data Analysis

Based on the

Lj-Norm

and Related Methods, pages 177-184. Elsevier Science

Pub-

lishers, North-Holland, Amsterdam, 1987.

[163J

[1908]

G.F.

Voronoi. Nouvelles applications des

parametres

continus it

la

theorie des

formes

quadratiques

- Deuxieme memoire. Journal fur die Reine und Angewandte

Mathematik,

134:198-287, 1908. [172,188,189,226]

[1909]

G.F.

Voronoi. Nouvelles applications des

parametres

continus a

la

theorie des

formes

quadratiques

- Deuxieme memoire - Seconde

Partie.

Journal tiir

die

Reine

und Angewandte Mathematik,

136:67-181,1909. [172,188,189,226]

[1937]

K.

Wagner.

tber

eine Eigenschaft

der

ebene Komplexe. Mathematische Annalen,

114:570-590, 1937.

[434]

[1990]

A. Wagner

and

D.C. CorneiL Embedding trees in a hypercube is NP-complete.

SIAM

Journal on Computing, 19:570-590, 1990.

[294]

[1993] A. Wagner

and

D.C. CorneiL

On

the

complexity

of

the

embedding problem for

hypercube

[294]

[1992] M. Waldschmidt, P. Moussa, J.-M. Luck,

and

C. Itzykson, editors. Prom Number

Theory

to

Physics. Springer-Verlag, Berlin, 1992.

[187]

[1988] W.D. Wallis. Combinatorial Designs. :vIarcel Dekker, New York, 1988.

[343J

[1992] P.M. WeichseL Distance regular subgraphs of a cube. Discrete Mathematics,

109:297-306,1992. [269,3081

[1975]

J.IL

Wells

and

L.R

Williams. Embeddings and Extensions in Analysis. Springer-

Verlag, Berlin,

1975. [34,113,117]

[1976J

D.J.A.

Welsh. Matroid Theory. Academic Press, London, 1976.

[436J

[19901

E.

Wilkeit. Isometric embeddings in Hamming graphs. Journal of Combinatorial

Theory B,

50:179-197, 1990.

[304]

[1973]

RM.

Wilson.

The

necessary conditions for t-designs

are

sufficient for something.

Utilitas Mathematica, 4:207-217, 1973.

[382]

[1975]

R M. Wilson. An existence

theory

for pairwise balanced designs III:

proof

of

the

existence conjectures. Journal

of

Combinatorial Theory

A,

18:71-79,1975.

[3<13]

574

Bibliography

[1983J

P.M. Winkler.

Proof

of

the

squashed

cube conjecture. Combinatorica, 3:135-139,

1983. [278,294J

[1984J

P.M. Winkler. Isometric embed dings in

products

of

complete graphs. Discrete

Applied Mathematics, 7:221-225,1984.

[304J

[1985J

P.M. Winkler.

On

graphs

which

are

metric spaces

of

negative type.

In

Y. Alavi,

G.

Chartrand,

and

L. Lesniak, editors, Graph Theory with Applications to Algo-

rithms

and

Computer

Science, pages 801-810. Wiley, New York, 1985.

[290J

[1987aJ P.M. Winkler.

Factoring

a

graph

in

polynomial time. European Journal

of

Combinatorics, 8:209-212, 1987.

[305J

[1987bJ P.M. Winkler.

The

metric

structure

of

graphs:

theory

and

applications.

In

C.

Whitehead,

editor, Surveys

in

Combinatorics 1987, volume 123 of London Math-

ematical Society Lecture Note Series, pages 197-221. Cambridge University

Press,

Cambridge,

1987.

[297J

[1988J

P.M. Winkler.

The

complexity

of

metric realization.

SIAM

Journal on Discrete

Mathematics, 1:552-559, 1988.

[310J

[1978J

H.S.

Witsenhausen.

A

support

characterization

of

zonotopes. Mathematika,

25:13-16,1978.

[110J

[1967J

D. Wolfe.

Imbedding

of a finite metric set in

an

n-dimensional Minkowski space.

Proceedings

of

the Koninklijke Nederlandse

Akademie

van Wetenschappen, Series

A,

Mathematical Sciences, 70:136-140,1967.

[156J

[1978J

M. Yannakakis. Node-and edge-deletion NP-complete problems. Proceedings

of

the 10th

Annual

ACM

Symposium

on the Theory

of

Computing, pages 253-264,

1978.

[48J

[1938J

Gale Young

and

A.S. Householder. Discussion

of

a set

of

points

in

terms

of

their

mutual

distances. Psychometrika, 3:19-22, 1938.

[74J

[1970J

M.L. Yoseloff. A Combinatorial Approach to the Diagonal N -Representability

Problem.

PhD

thesis,

Princeton

University, 1970.

[64,69J

[1969J

M.L. Yoseloff

and

H.W.

Kuhn.

Combinatorial

approach

to

the

N-representability

of

p-density

matrices. Journal

of

Mathematical Physics, 10:703-706, 1969.

[54J

[1965J

K.A. Zaretskii. Factorization

of

an

unconnected

graph

into

a

cartesian

product.

English

translation

in Cybernetics, 1(2):92, 1965.

[305J

[1995J

G.M. Ziegler. Lectures

on

Polytopes,

Graduate

Texts in

Mathematics

152.

Springer-Verlag, New York, 1995. [l1,431J

Notation

Index!

G =

(V,

E)

11

graph

e = (u, v) =

uv

11

edge in a

graph

joining

nodes u

and

v

Vn

11 set

of

elements 1,

...

, n

En

11

set

of

pairs

ij

for 1

:<:;

i < j

:<:;

n

Kn

=

(Vn,En)

11

complete

graph

on

n nodes

Knlln2

11

complete

bipartite

graph

8G(S)

11

cut

in

graph

G

G[W]

12

subgraph

of

G induced by W

G\e

12

subgraph

of

G

obtained

by deleting edge e

G/e

12

subgraph

of

G

obtained

by

contracting

edge e

P

n

12

path

on

n nodes

en

12 circuit

on

n nodes

H(n,2)

12

hypercube

graph

k

H

(n,2)

12

half-cube

graph

Knx2

12

cocktail-party

graph

PlO

13

Petersen

graph

G

1

x G

2

13

Cartesian

product

of

two

graphs

G

1

and

G

2

\lG

14 suspension

graph

of

G

L(G)

14 line

graph

of

G

~

14

set

of

real

numbers

Q 14

set

of

rational

numbers

Z

14 set

of

integer

numbers

N 14

set

of

natural

numbers

X

S

14 incidence vector

of

a

set

S

Al:::.B

14

symmetric

difference

of

two sets A

and

B

xT,

MT

14

transpose

of vector

x,

matrix

M

xTy

14

scalar

product

of

vectors x

and

y

dim(X)

14

dimension of a

set

X

rank(X)

14

rank

of

a set X

JK(X) 14

linear

hull

of

X

with

coefficients in

JK

Conv(X)

14

convex hull

of

X

KO

14

polar

of

convex set K

CUTn

15

cut

cone

CUT~

15

cut

polytope

an

16

n-dimensional

simplex

(3n

16

n-dimensional

cross-polytope

In

16

n-dimensional

hypercube

P,

NP,

co-NP

18

complexity

classes

1

Symbols

are listed in

the

order

of first occurrence

in

the

text.

576

A-I

OA(n)

A

~

0

det(A)

PSD

n

Gram(

Vb

...

,

V,,)

In(A)

d

ij

,

MET"

tin

6(S)

II;J;

II

dJ.1I

II

xiiI'

dip

e;,

=

(Rom

,dl.

p

)

d

H

da,

d(G)

dG,w

G~H

mlp(X,d)

mep(n)

NORn(P)

(11,

A,

11)

Lp(l1, A,

JL)

(AI' A

..

)

CUT(X),

CUTD(X)

sdd)

s,,(d)

T)(d)

7r(S)

COR"

COR~

COR(X),

CORO(X)

,

{xo

)T1(S),

CORn(I),

COR~(I)

Qn(b), Q(b)

HYP

n

HYP(X)

NEG"

CM(X,d)

Sm

8

m

gat"

(d)

ant,,(d)

Ant"

(d)

spht(d)

(L,::$)

xl\y

19

20

21

27

28

29

31

32

33

38

45

47

53

54

55

56

64

68

69

76

86

93

94

97

105

Notation Index

inverse of

matrix

A

set

of

orthogonal matrices

of

order

n

matrix

A

is

positive semidefinite

determinant

of

matrix

A

cone

of

positive semidefinite matrices

Gram

matrix

of

vectors

VI,

.••

,

Vn

inertia

of

matrix

A

distance between points i

and

j

semimetric cone

equidistant metric on

n points with value t

cut

semimetric

norm

of

x

distance induced by

norm

II

.

II

fip-norm

of

x

t'p-distance

Rom

equipped with fp-distance

Hamming distance

shortest

path

metric

of

graph

G

shortest

path

metric

of

weighted

graph

(G,

w)

G is

an

isometric

subgraph

of

H

ip-dimension

of

distance space

(X,

d)

minimum ip-dimension

of

distance

spaces

on

n points

cone

of

pth

powers

of

ip-distances

measure space

distance space of measurable functions

measure semi metric space

cut

cone

and

polytope

on

a set X

minimum iI-size of d

minimum h-size of d

minimum scale of d

correlation vector of set S

correlation cone

correlation polytope

correlation cone

and

polytope on a set X

covariance mapping

covariance mapping pointed

at

position

Xo

generalized correlation vector, cone

and

polytope

vector

with

coordinates bibj

hypermetric cone

hypermetric cone on a set

X

negative

type

cone

Cayley-Menger

matrix

of

(X,d)

m-dimensional unit sphere

spherical distance space

of

m-sphere

gate extension

of

d

antipodal

extension

of

d

full

antipodal

extension

of

d

spherical extension of d

poset (partially ordered set)

meet of

x

and

y

Notation

Index

577

xVy

105

join

of

x

and

y

Jp(m)

141

order

of

congruence

of

£;'

C

139

family

of

shores

of

the

cuts

in C

D:d(A)

145

isolation

index

of

8(A)

~d

145

set

of

d-s plits

of

d

d(2)

170

square

of

Euclidean

distance

L

177

(point)

lattice

det(L)

178

determinant

of

lattice

L

Lmin

178

set

of

minimal

vectors

of

L

L*

179

dual

lattice

of

L

L1

Ell

L2

179

direct

sum

of

lattices

L1

and

L2

L(P)

179

lattice

generated

by

the

vertices

of

P

(V(P),

d(2))

180

Delaunay

polytope

space

of

P

en

181

cut

lattice

Pv(uo)

182

Voronoi

polytope

at

Uo

x*

183

antipode

of

x (on a sphere)

Pyrv(P),

Bipyrv(P)

185

pyramid,

bipyramid

with

base P

Ker

A

189

kernel

(=

nullspace)

of

matrix

A

Pd,

Ld,

Sd

196

Delaunay

polytope,

lattice,

sphere

associated

with

distance

d

An,

Dn, E

6

,

E

7

, Es

206

irreducible

root

lattices

h,n

207

n-dimensional

half-cube

J(n,

t)

207

Johnson

graph

3

21

208

Gosset

polytope

G

56

208

Gosset

graph

221

208

Schliifii

polytope

G

27

208

Schliifii

graph

H(P)

208

Delaunay

polytope

graph

(=

I-skeleton

of

P)

Ann(X,d)

218

annullator

of

(X,

d)

S(X,d)

218

system

of

hypermetric

equations

associated

with

(X,

d)

F(X,

d), F(d)

218

smallest face

of

HYP(X)

containing

d

rk(X,

d)

218

rank

of

(X,

d)

rk(P)

218

rank

of

P

P~

226

repartitioning

polytope

A24

244

Leech

lattice

A

16

245

Barnes-

Wall

lattice

d*

G

251

truncated

distance

of

graph

G

AG

251

adjacency

matrix

of

G

Amin(A)

251

minimum

eigenvalue

of

matrix

A

LEes

267

class

of

187

graphs

with

Am

in

(AG)

~

-2

(J

279

Djokovic's

relation

dimJ(G)

279

isometric dimension

of

graph

G

mh(G)

280

smallest dimension

of

a

hypercube

containing

G isometrically

PG(2, t)

335

projective

plane

of

order

t

JC~

382

set

of

k-uniform

cuts

on

n

points

JC;:

383

set

of

even

T-cuts

on

n

points

JC~dd

383

set

of

odd

cuts

on

n

points

R(F)

400

set

of

roots

of

face F

Sym(n)

403

group

of

permutations

on

n

points

578 Notation Index

0"(

7J)

403

applying

permutation

0"

to

vector v

vB

404

switching vector v by set B

rB

404

switching mapping

I1

Cl

(F)

407

orbit

of face F in

the

cut polytope

I1(F)

407

orbit

of

face F in

the

cut

cone

Is(CUT~)

409

set

of symmetries

of

cut

polytope

v"

410

1T

-collapse

of

vector v

MET~

421

semimetric polytope

RMET~+l

425

rooted semimetric polytope

MET(G),

METD(G)

430

semimetric cone

and

polytope

of

G

CUT(G),

CUTD(G)

430

cut

cone

and

polytope

of

G

M

436

binary

matroid

M(G)

436

graphic matroid

of

graph

G

M*(G)

436

cographic

matroid

of graph G

M*

436

dual

matroid

of

M

GF(2)

437

field with two elements

M\e

437

deleting element e in M

M/e

437

contracting

element e in M

F7

437

Fano

matroid

P,*

7

438

dual

Fano

matroid

RIO

438

matroid

RIO

P

r

438

binary

projective space

CYC(M)

438

cycle cone

of

M

CYCD(M)

438

cycle polytope

of

M

METo(M)

439

semimetric polytope

of

M

MET(M)

439

semimetric cone

of

M

Z(M)

442

cycle

lattice

of M

Z+(M)

444

integer cycle cone

of

M

[(b)

457

gap of b

db)

457

sum

of

components

of

b

:In

459

positive semidefinite relaxation of

CUT~

mc(Kn,

c)

460

max-cut value

En

462

elliptope

W;,

AW;

467

web, antiweb graphs

(CW~)Tx

~

0

468

pure

clique-web inequality

cW:(bfx

~

0

470

general clique-web inequality

ST:(T,bj1'x

~

0

487

suspended-tree inequality

C(n,r)

496

circulant

graph

(Par2k+l)T x

~

0

497

parachute

inequality

(Fib

2k

?x

~

0

499

Fibonacci inequality

(Gr7)Tx

~

0

502

inequality by Grishukhin

E(G)

515

eUiptope

of

graph

G

NEG(G)

528

negative

type

cone

of

graph

G

N(K,x)

534

normal cone

C(K,x)

534

supporting

cone

(A,B)

535

inner product

of

matrices A

and

B

TrA

535

trace

of

matrix

A

FK(A)

536

smallest face

of

K containing A

<Pd(P)

539

set of

d-

faces

of

P

Subject

Indexl

adjacency

matrix

251

adjacent

nodes

11

affine basis

178

affine

generating

set

178

affine integer hull

14

affine

lattice

178

affine realization

219

annuJlator

200,218

antipodal

extension 94,98-101

full

94

antipode

183

antiweb

467

weighted

470

apex

14

asymmetric

Delaunay

polytope

183

atom

316

proper

316

atom

graph

316

automorphism

of

a face

408

Barnes-Wall

lattice

245

basic Delaunay polytope 180,443

basic

set

180

basic

subgraph

242

basis

177

Bell-Wigner polytope

54

BlBD

(n,

k,

,\)-

342

binary

matroid

435-444

biotope distance

119

bipartite

graph

11

bipartition

11

bipyramid

185

body

convex

14

Boole problem 61-65

boolean quadric polytope

54

canonical metric representation

298

capacity

of

an

edge

132

Caratheodory's

theorem

15

cardinality measure

32

Cartesian

product

13

Cayley-Menger

determinant

77

Cayley-Menger

matrix

77

centered

lattice

250

centrally symmetric

15

centrally symmetric Delaunay polytope

183

Chebyshev metric

164

chessboard metric

164

chord

431,440

chordal

graph

517

chordless

431

Chvatal

closure

428

Chvatal

cut

428

Chvatal

rank

428

circuit

12,436

circulant inequality

496-497

circular decomposable distance

91

city-block metric

164

Clebsch

graph

209

clique

12

clique condition 516,529

clique k-sum

13

clique-web inequality 467-485

cocircuit

436

cocktail-party

graph

12,98-101,207,313

cocycle

436

cocycle inequality

439

collapsing

operation

410-413

commodity

pair

132

commutative semigroup

107

complete

bipartite

graph

11

complete

graph

11

condition

clique

516,529

'Rnlrlf."p

numbers

refer

to

the

pages where

items

are

introduced.

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

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