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

27.4 Cycle Polytopes

of

Binary

Matroids

437

space

GF(2)E.

Hence, identifying a set

and

its

incidence vector,

the

cycle spaces

of

binary

matroids

are

nothing

but

the

linear subspaces over

GF(2).

In

this

terminology,

the

cocycle space

C*

of M

is

the

orthogonal complement

of

the

cycle space C

in

GF(2)E.

Hence,

the

cycle space of a

binary

matroid

M

on

E

can

be

realized as

the

set

of

solutions I E

{O,

I}E

of

a linear equation:

M I = ° (modulo

2)

where M is a zero-one

matrix

whose columns are indexed by

E.

Such

matrix

M

is called a representation

matrix

of

M.

The

maximum

number

of

columns

of

M

that

are linearly

independent

over

GF(2)

is

called

the

rank

of

M.

If

M

has

rank

r,

then

a

representation

matrix

can

be found for M having

the

form

(IT

I

A),

where

IT

is

the

r x r

identity

matrix.

Moreover,

the

matrix

(AT

I IIEI-T) is

then

a

representation

matrix

for

the

dual

M*

of

M.

Minors.

Let M =

(E,

C)

be a

binary

matroid

and

let e E

E.

Set

C\e:={C<:;:E\{e}ICEC},

Cle:={C\{e}ICEC}.

In

the

language

of

binary

spaces,

C\e

arises from C by

taking

its intersection

with

the

hyperplane

Ie

=

0,

while C I e arises from C by

taking

its

projection

on

RE\{e}.

Both

C\e

and

Cle

are again

binary

spaces. Hence,

M\e

:=

(E\

{e},

C\e)

and

Mle

:=

(E

\

{e},Cle)

are

both

binary

matroids. One says

that

M\e

is

obtained

from M by deleting

the

element e

and

that

Mle

is

obtained

from M

by contracting

the

element

e.

The

deletion

and

contraction

operations

commute

with

respect

to

taking

duals, namely,

(M\e)*

=

M*

Ie,

(Mle)*

=

M*\e.

If

N is a

binary

matroid

that

can

be

obtained

from M by a series

of

deletions

and

contractions, one says

that

N is a

minor

of

M.

Every

minor

of

M is of

the

form:

M\XIY,

where

X,

Yare

two disjoint subsets

of

E (as

the

deletion

and

contraction

operations

commute, i.e.,

M\el

f =

MI

f\e).

Observe

that

the

deletion

and

contraction

operations,

when

applied

to

the

graphic

matroid

M(G)

of

a

graph

G, correspond

to

the

usual operations of deleting

and

contracting

an

edge

in

G. Hence,

the

class of graphic

matroids

is closed under

taking

minors;

the

same

holds for

the

class of cographic matroids.

We

now present several concrete examples

of

binary

matroids

that

we

will

need.

The

Fano

Matroid.

The

Fano matroid

F7

is

the

binary

matroid

on

the

set

E

:=

{I,

2,

3,

4, 5, 6,

7}

whose cycles are

0,

E,

and

the

sets

124,135,167,236,257,347,456

together

with

their

complements. (Here

we

denote a set

{I,

2,

4} by

the

string

124.) Note

that

the

cycles

of

size 3

of

F7

can

be viewed as

the

lines

of

the

438

Chapter

27.

Triangle Inequalities

Fano plane, shown in Figure 27.4.1. A representation

matrix

for

F7

is

also

shown there.

The

dual Fano matroid

F;

is

the

dual of

the

Fano

matroid

F7;

its

nonempty cycles are the complements of the lines in the Fano plane.

3

1 2 3 4 5 6

7

(!

0 0 1 1 0

D

1

0

1

0

1

0

1

0 1 1

Representation

matrix

for

F7

2 4

The

Fano plane

Figure 27.4.1

The

Matroid

RlO. Let E

:=

{eij I 1

:s

i < j

:s

5}

denote the edge set of

the

complete

graph

K

5

.

Then, RlO denotes the binary

matroid

on E whose cycles

are

the

sets C

<;

E forming a cycle of even length in K

5

•

The

cocycles are

the

cuts

of

K5

together

with

their

complements. Note

that

RlO

is

self-dual;

that

is,

RlO is isomorphic to its dual Rio.

The

Binary

Projective

Space

PT. Let P

r

denote

the

binary

matroid

which

is represented by the r x

(2'

-1)

matrix

whose columns are all possible nonzero

binary

vectors of length

r.

Hence,

P3

coincides

with

the

Fano

matroid

F

7

•

One

can

verify

that

P

T

has

2T

- 1 nonempty cocycles, each having size 2

T

-

1

,

and

that

their

incidence vectors are linearly independent.

The

dual

matroid

P;

is

represented, for instance, by

the

matrix

(12

r

-,-1

I A

r

),

where

hr-r-1

is

the

identity

matrix

of order

2T

- r

-1

and

AT

is

the

matrix

whose rows are all

binary

vectors of length r having

at

least two nonzero components.

27.4.2

The

Cycle

Cone

and

the

Cycle

Polytope

Let M =

(E,

C)

be

a binary matroid.

The

cycle polytope of M is

the

polytope

CYCD(M),

which is defined as the convex hull of the incidence vectors of

the

cycles of

M,

i.e.,

CYCD(M):=

Conv({x

c

ICE

C}).

The

cycle cone of M is

the

cone

CYC(M),

which

is

defined as

the

conic hull of

the

incidence vectors of

the

cycles of

M,

i.e.,

CYC(M)

:=

CE

>'CX

c

I

>'c

2 0 for all C E C}.

CEe

27.4 Cycle Polytopes

of

Binary Matroids

439

Therefore,

if M =

M*(G)

is

the

cographic

matroid

of

a

graph

G,

then

its cycle

cone

and

polytope coincide, respectively, with

the

cut

cone

CUT(

G)

and

the

cut

polytope

CUT

D

(G)

of

G.

For

the

study

of

cycle polyhedra,

we

may clearly assume to deal

with

cosimple

matroids. Indeed,

if {e}

is

a cocircuit

of

M,

then

no cycle

of

M contains e

and,

thus,

the

cycle cone

and

polytope are contained

in

the

hyperplane

Xe

=

o.

Similarly, if {e, J}

is

a cocircuit

of

M,

then

the

cycle

polyhedra

lie

in

the

hyperplane

Xe

-

xf

=

o.

Moreover,

the

cycle polyhedra of a cosimple

binary

matroid

are full-dimensional (cf.

Barahona

and

Grotschel [1986]).

By

the

results

of

Section 26.3.1,

the

switching

operation

preserves

the

cy-

cle

polytope

CYCD(M)

of

any binary

matroid

M;

that

is,

rc(CYCD(M))

=

CYCD(M)

for any cycle C

of

M.

Moreover, a linear description

of

the

cycle

polytope

CYCD(M)

can

be

derived from a linear description

of

the

cycle cone

CYC(M).

(Recall Proposition 26.3.6.)

Some valid inequalities for

the

cycle polytope

CYCD(M)

can be easily defined

as follows.

First,

the

inequalities: 0

:::;

Xe

:::;

1 (for e E

E)

are trivially valid for

CYCD(M).

Let

D be a cocycle of M

and

let F

~

D with

IFI

odd;

then,

the

cocycle inequality:

(27.4.2)

x(F)

-

x(D

\

F)

:::;

IFI

- 1

is

valid for

CYCD(M).

(This follows from

the

fact

that

every cycle has

an

even

intersection with

the

co cycle D). Let

METD(M)

denote

the

polytope

in

~E,

which is defined by

the

inequalities: 0

:::;

Xe

:::; 1

(e

E

E)

together

with

the

co cycle inequalities (27.4.2) for D E

C*,

F

~

D

with

IFI

odd. Similarly, define

the

cone:

MET(M)

:=

{x

E~!

I

Xe

-

x(D

\ {e})

:::;

0 for all

DE

C*,e

ED}.

In

the

case when M

is

the

cographic

matroid

M*(G)

of

a

graph

G,

then

METD(M*(G))

= METD(G)

and

MET(M*(G))

=

MET(G)

are

the

usual semi-

metric

polyhedra

of

the

graph

G (which explains

our

notation).

We

have

the

inclusions:

CYCD(M)

~

METD(M),

CYC(M)

~

MET(M).

Hence arises

the

question

of

characterizing

the

binary matroids for which equality

holds. Due

to

switching,

CYCD(M)

=

METD(M)

{=;>

CYC(M)

=

MET(M).

Following Seymour [1981],

the

binary matroids M for which equality:

CYC(M)

=

MET(M)

holds are

said

to have

the

'sums

of

circuits property'.

Observe

that

none

of

the

binary

matroids

F;,

RIO,

or M*(K5) has

the

sums

of

circuits property. Indeed,

the

vector

(~,

...

,

~)

is

a fractional vertex

of

the

polytope

METD(M)

for M = M*(K5) or

F;

and

the

vector

(~,

...

,~)

is a

440

Chapter

27. Triangle Inequalities

fractional

vertex

of

the

polytope

METD(RlO).

In

fact,

the

exclusion of

these

three

matroids

F-i, R

lO

,

and

M*(K5)

as minors characterizes

the

sums

of

circuits

property.

Theorem

27.4.3.

A binary matroid M has the

sums

of

circuits property, that

is,

CYC(M)

=

MET(M)

or, equivalently,

CYCD(M)

=

METD(M),

if

and only

if

M does

not

have F-i,

M*(K

5

),

or

RlO

as

a minor. I

In

particular,

the

cographic

matroid

of a

graph

with

no K5

minor

has

the

sums

of

circuits property, a

result

already

mentioned

in

Theorem

27.3.6,

and

any

graphic

matroid

has

the

sums

of circuits property, a

result

established

earlier

by

Seymour

[1979].

Theorem

27.4.3 was proved

by

Seymour

[1981]' who considered

the

sums

of

circuits

property

along

with

several

other

properties

multicommodity

flows;

the

result

follows

there

from more general considerations. A

more

direct

proof

was given

by

Grotschel

and

Truemper

[1989a].

The

proof

of

Theorem

27.4.3 relies essentially

on

some decomposition

results

for

binary

matroids,

involving

an

operation

on

matroids

which

can

be

seen as

an

analogue of

the

clique

sum

operation

for graphs. Roughly speaking, a

matroid

with

no F-i,

M*(K

5

),

or

RlO

minor

can

be

decomposed into pieces

that

are

either

cographic

matroids

with

no

M*(K5)

minor, or graphic

matroids,

or copies of F

7

.

Thus

the

proof

can

be

sketched as follows: show

that

the

sums

of circuits

property

is preserved

under

taking

minors

and

under

the

'clique

sum

operation'.

Further

results

about

the

facial

structure

of

cycle

polytopes

can

be

found

in

Barahona

and

Griitschel

[1986]

and

Griitschel

and

Truemper

[1989b]. For

instance,

Barahona

and

Griitschel give conditions

under

which

the

co

cycle in-

equality

(27.4.2) defines a facet

of

the

cycle polytope. Clearly,

if

the

inequality

(27.4.2) is facet defining,

then

D

must

be

a

co

circuit

without

a chord

(a

chord

of

D

being

an

element e E E for which

there

exist two cocircuits

D1

and

D2

such

that

D1

n

D2

=

{e}

and

D = D

1

6D

2

).

Conversely,

if

M has no

F-i

minor

and

if

D is chordless cocircuit,

then

the

inequality (27.4.2) defines a facet

of

CYCD(M).

Example

27.4.4.

The

cycle

polytope

of

the

dual

projective

space

P;.

The

dual

projective space

P;

is defined

on

a groundset of

cardinality

2

r

-1;

it

has

2'

- 1

nonempty

cycles, each of

cardinality

2

r

-

1

,

and

whose incidence vectors

are linearly

independent.

Therefore, its cycle

polytope

CYCD(pn

is a full-

dimensional

simplex

with

2

r

vertices, whose facets are defined

by

the

inequality:

together

with

its switchings

by

the

2'

- 1

nonempty

cycles.

These

switched

inequalities all have a right

hand

side zero

and

they

constitute

the

full linear

description

of

the

cone

CyC(pn.

As

an

example,

we

obtain

that

the

cycle

27.4 Cycle Polytopes of Binary Matroids

441

polytope of

the

dual Fano matroid

F;

=

Pi

is defined by the inequality:

together with its switchings by the seven circuits of

Pi

(complements of the Fano

lines).

We

note, therefore,

that

the cocycle inequalities (27.4.2) do not define

facets

of

the

cycle polytope

of

Hence,

the

cycle polytope of a dual projective space, being a simplex, has a

very simple facial structure.

In

fact, as

we

see below,

any

cycle polytope

can

be

realized as

the

projection

of

such a simplex.

But

finding the facial

structure

of a

cycle polytope is a task which, in general, is far from being

easy!

(It is already

difficult in

the

special case when the binary matroid in question is the cographic

matroid

of the complete graph; then

we

have the problem of describing the facial

structure

of

the

cut

polytope

CUT~

which forms, in fact, the main objective

of

this

Part

V.)

Following Grotschel

and

Truemper [1989b],

we

now indicate how any cycle

polytope can be realized as projection of a simplex. Let

M be a cosimple binary

matroid. Consider a representation

matrix

of

M

of

the

form

(1

I A) where A is

a 0,

I-matrix

having two units

at

least

per

row.

Say,

A has r columns. Recall

that

P;

is represented by the

matrix

(I2"-r--l I AT), where the rows of

AT

are all

binary

vectors of length r

with

two units

at

least.

Now,

A

is

a row

submatrix

of

AT' Let Y denote the index set for the rows

of

Ar

not present

in

A.

Then,

M

coincides

with

the

contraction minor

P;

/Y

of

P;.

Therefore,

its

cycle polytope

CYCD(M)

can be obtained from

the

cycle polytope

CYCD(P;)

of

P;

by pro-

jecting

out

the

variables

Xe

(e

E Y). I

27.4.3

More

about

Cycle

Spaces

We

mention here some questions

and

results dealing with other relevant aspects

of

binary matroids.

In

particular,

we

mention results concerning optimization

over cycle spaces.

We

also consider the lattice

Z(M)

and the integer cone

Z+(M)

generated by

the

cycle space of a binary matroid

M.

In

this setting,

we

find

again two problems raised earlier concerning

the

existence of nonbasic Delaunay

polytopes

and

the

study

of Hilbert bases.

Indeed, as every cycle polytope CYCD(M)

is

a Delaunay polytope in

the

lattice

Z(M),

Problem 13.2.3 raises the question of existence of a basis of

Z(M)

consisting only of cycles. This question remains open

for

general binary matroids

but

several classes of binary matroids are known for which

it

has a positive

answer. Goddyn

[1993]

raised the question of characterizing the

binary

matroids

whose cycle space is a Hilbert basis, which contains the question posed

in

Section

25.3

about

Hilbert bases of cuts.

We

review what is known

about

this problem.

The

Maximum

Weight

Cycle

Problem.

Let

A1

=

(E,C)

be a

binary

ma-

troid

and

W E

Ql.

The

maximum weight cycle problem consists of finding a

cycle

C E C whose weight

We

is maximum. This problem is

NP-hard

as

442

Chapter

27.

Triangle Inequalities

it

contains

the

max-cut problem as a special instance. However,

this

problem

becomes polynomial-time solvable for several classes

of

binary matroids. This is

the

case, for instance, for cographic matroids

of

graphs

with

no K5-minor (recall

Theorem 27.3.7).

This

is also

the

case for graphic matroids, by

the

results

of

Edmonds

and

Johnson

[1973].

Griitschel and Truemper [1989a] show

that

the

maximum

weight cycle problem

can

be

solved in polynomial time for

the

larger

class

of

binary matroids having

the

sums

of

circuits property.

The

latter

result is based on showing

that

the

separation problem for

the

polytope

MET

O

(}'-1)

can be solved

in

polynomial

time

if

M has

the

sums

of

circuits property. Using decomposition results, Griitschel

and

Truemper reduce

this

question to the special cases when M is graphic

or

cographic. A separation

algorithm was given by Padberg

and

Rao

[1982]

in

the

graphic case

and

by

Barahona

and

Mahjoub

[1986]

in

the

cographic case (the

latter

algorithm has

been described

in

Section 27.3.1).

The

Cycle

Lattice.

For a binary

matroid

M = (E,

C),

let

Z(M)

{L

>'CX

c

I

>'c

E Z ve E

C}

CEe

denote

the

lattice generated by

its

cycle space, called

the

cycle lattice of

}'-1.

If

M is

the

cographic

matroid

of

the

complete graph K

n

,

then

Z(M)

coincides

with

the

cut

lattice

en

introduced earlier. As

we

saw

in

Proposition 25.1.1,

the

cut

lattice

en

has a very easy description; namely, an integer vector x belongs

to

en

if

and

only

if

Xij

+

Xik

+

Xjk

E 2Z for all

i,j,

k E

{I,

...

,

n}.

One may

wonder whether a similar result holds for any cycle lattice.

As cycles

and

co

cycles have

an

even intersection,

the

following parity condi-

tion:

(27.4.5)

x(D)

E 2Z for every cocycle D

of

M

is obviously necessary for a vector x E

ZE

to belong to

Z(M).

However,

this

condition does not suffice in general for characterizing

Z(M).

For instance,

if

M is

the

dual

Fano matroid

F;,

then

every vector x E

Z(F;)

should, in fact,

satisfy

the

congruence relation: L

Xe

= 0 (modulo 4).

The

next result follows

eEE

from

the

work

of

Cunningham

[1977].

Theorem

27.4.6.

The following assertions

are

equivalent for a cosimple binary

matroid

M.

(i)

Z(M)

is completely characterized by the parity condition (27.4.5) and the

same holds for every

minor

of

M.

(ii) M does

not

have

F;

as

a minor.

I

This

leaves unanswered

the

question of characterizing the binary matroids

M whose cycle space is described by

the

parity condition (while not requiring

27.4 Cycle Polytopes

of

Binary Matroids

443

this

property

for minors of

M).

Lovasz

and

Seress

[1993]

give a complete answer

to

this question.

They

give in fact several equivalent characterizations for such

matroidsj

we

mention

in

Theorem 27.4.7 below one

of

them.

Further

results on

cycle lattices

can

be

found in Lovasz

and

Seress [1993, 1995].

We

need a definition. Given a

matrix

B

with

rows bI, .

..

,

bTl

let

B'

denote

the

matrix

with

rows b

i

,

...

,b

r

and

bi

0

bj

(1

~

i < j

~

r) where, for two vectors

a,

bE

]Rn, a 0 b

stands

for the vector

with

components aibi

(1

~

i

~

n).

Theorem

27.4.7.

Let M

be

a cosimple binary matroid with representation ma-

trix

B.

Then, the cycle lattice Z(A1) is completely characterized by the parity

condition

(27.4.5)

if

and only

if

the

matrix

B'

has full column rank over G

F(2).

I

Delaunay

Polytopes

in

Cycle

Lattices.

We

saw

in

Example 13.2.5

that

the

cut

polytope

GlJT~

is a Delaunay Polytope

in

the

cut

lattice Ln. More generally,

as

noted

in Hochstattler, Laurent

and

Loebl [1996],

the

following holds.

Lemma

27.4.S.

Let

M

be

a cosimple binary matroid. Then, its cycle polytope

CYCD(M)

is a Delaunay polytope in the cycle lattice Z(.A1).

Proof.

We

verify

that

the polytope CYCD(M) is inscribed on a sphere S which

is

empty

in

Z(M).

Indeed, CYCD(M) is inscribed on

the

sphere S

with

center

c

a,

...

,

t)

and

radius r

:=

tJlET·

Let x E

Z(M).

Then,

with

equality

if

and

only

if

x is

0,

I-valued.

Now

the only binary vectors in

Z(M)

are

the incidence vectors of cycles. This shows

that

the

sphere S is

empty

in

Z(M).

I

We

asked

in

Problem 13.2.3 whether every Delaunay polytope is basic. This

question remains already unsettled for Delaunay polytopes arising from cycle

lattices.

That

is,

we

have the following question:

Problem

27.4.9.

Given a binary matroid

."'1,

can one find a basis B for the

cycle lattice

Z(M)

consisting only

of

cycles?

The

following information is known. Gal1ucio

and

Loebl

[1997]

show

that

Prob-

lem 27.4.9 has a positive answer for graphic matroids. Gallucio

and

Loeb!

[1996]

show

that

the

same holds

for

matroids with no minor (using decomposition

results). A

short

elementary proof for this result is given

by

Hochstattler, Lau-

rent

and

Loebl

[19961;

moreover, these authors extend

the

result

to

one-element

extensions of

binary

matroids with no Pi minor. Problem 27.4.9 is further stud-

ied

in

Hochstattler

and

Loebl

[1995].

444

Chapter

27.

Triangle

Inequalities

The

Integer

Cycle

Cone.

For a

binary

matroid

M = (E,C), let

Z+(M):=

{l::

ACX

C

I

AC

E

Z+

'Ie E

C}

CEe

denote

the

integer

cone

generated

by

its

cycle space, called

the

integer cycle cone

of

M.

If

M is

the

cographic

matroid

of

the

complete

graph

K

n

,

then

Z+(M)

consists,

in

fact,

of

the

distances

on

n

points

that

are

isometrically

hypercube

embeddable

(recall

Proposition

4.2.4). Clearly,

Z+(M)

<;::;

Z(M)

n

CYC(M).

As

in

Section

25.3,

we

say

that

C is a

Hilbert

basis if

equality

holds

in

the

above

inclusion.

Characterizing

the

binary

matroids

whose cycle space C is a

Hilbert

basis

is

an

open

problem,

already

within

cographic

matroids.

We

summarize

below

what

is

known

about

this

question.

Alspach,

Goddyn

and

Zhang

[1994]

answer

this

question

for

graphic

matroids.

Namely,

they

show

that

the

family

of

cycles

of

a

graph

G is a

Hilbert

basis

if

and

only

if

G does

not

have

the

Petersen

graph

as a minor. (Indeed,

let

x

denote

the

vector

indexed

by

the

edge

set

of

the

Petersen

graph

taking

value 2

on

a

perfect

matching

and

value 1

on

the

remaining

edges.

Then,

x E

Z(M(P

lO

))

n

CYC(M(PIO))

but

x

if.

Z+(M(P

lO

)),

which shows

that

the

cycles

of

PIO

do

not

form a

Hilbert

basis.)

Note

that

CYC(M)

=

MET(M)

for

graphic

matroids.

More generally,

this

equality

holds

for

matroids

with

the

sums

of

circuits property. Fu

and

Goddyn

[1995] have

characterized

the

Hilbert

basis

property

within

this

class. Namely,

they

show

that

Z+(M)

=

Z(M)

n

MET(M)

if

and

only

if

M is a

binary

matroid

with

no

F;,

RIO,

M*(K5),

or

M(PIO)

minor.

At

this

point

let

us recall

the

result

of

Laurent

[1996b] for cographic

matroids,

already

mentioned

in

Section

25.3:

The

co cycle space

of

M(G)

is a

Hilbert

basis

for

any

graph

G

i-

K6

on

at

most

6 nodes

and

it

is

not

a

Hilbert

basis

if

G

has

a

K6

minor.

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

Chapter

28.

Hypermetric

Inequalities

In

this

chapter

we

study

in

detail

the

class of

hypermetric

inequalities.

In

partic-

ular,

we

present several subclasses of

hypermetric

inequalities

that

define facets

of

the

cut

cone. We also address

the

separation

problem for

hypermetric

in-

equalities.

Although

its

exact complexity

status

is not known, there are several

results

that

indicate

that

it

is

very likely to be a

hard

problem.

In

particular,

the

problem

of finding

the

smallest violated

hypermetric

inequality is

NP-hard.

Hypermetric

inequalities belong,

in

fact, to

the

larger class of

gap

inequali-

ties. Unfortunately, very little

is

known

about

these more general inequalities.

In

particular,

it

is not known whether

they

contain new facets (besides

the

hy-

permetric

ones). Moreover, computing

their

exact right

hand

sides

turns

out

to

be

an

NP-complete

problem!

One way to avoid this difficulty is by relaxing

the

right

hand

·sides by a larger

number

(which is easy to compute).

In

this

manner,

one

obtains

a class of valid inequalities which defines a weaker relaxation of

the

cut

polytope.

This

relaxation forms a (nonpolyhedral) convex

body

which has

the

property

that

one

can

optimize over it

in

polynomial time. Moreover, opti-

mizing over this convex

body

yields a very

tight

approximation

for

the

max-cut

problem

(see Section 28.4.1).

28.1

Hyperrnetric

Inequalities:

Validity

Hypermetric

inequalities

constitute

the

first nontrivial class of valid inequali-

ties for

the

cut

cone. As was already mentioned earlier

in

Section 6.1

(and

Remark

5.4.11)

they

were discovered independently by several

authors

with

dif-

ferent

mathematical

backgrounds

and

motivation.

Hypermetric

inequalities have

already

been

introduced

in

Chapter

6

in

the

context of

£1-

and

£2-metrics. We

refer

to

Part

II

for a detailed

study

of

some

of

their

properties,

in

particular,

in

connection

with

geometry of numbers. We concentrate here

on

the

question of

identifying

hypermetric

facets.

In

order to make this

chapter

self-contained,

we

recall below

the

definitions

and

basic properties of hypermetric inequalities.

To define

hypermetric

and

further types

of

inequalities, it is convenient

to

use

the

following notation. For b E

llt

n

,

we

remind

that

Q(b) denotes

the

vector

in

llt

En

whose

ij-th

component

is

equal

to

the

product

bib

j

.

Hence, for x E

llt

En

,

Q(bf

x = L bibjX;j.

ijEEn

446

Chapter

28. Hypermetric Inequalities

This

notation

gives us a convenient way

of

defining left

hand

sides

of

inequalities

with

G)

coefficients based on a given vector b

of

length n.

In

case

we

want to

highlight the fact

that

the vector b

is

in]Rn,

we

will write Qn(b) or Qn(bl,

...

,

bn)

instead of Q(b).

Definition

28.1.1.

Let b =

(b

1j

•••

,b

n

)

be

an

integral vector satisfying Ei",1

bi

=

1. Then, the inequality:

(28.1.2) Q(b)T X = L bibjXij

~

O.

19<j:5n

is called the

hypermetric inequality defined

by

b.

A hypermetric inequality

(28.1.2) is said to

be

(2k+l)-gonal

if

Eilbi<O

Ibil

= k

or,

equivalently,

ifEi=1

Ibil

=

2k

+ 1.

Lemma

28.1.3.

Every hypermetric inequality (28.1.2) is valid for the cut cone

CUT

n

.

Moreover, the

roots

of

a hypermetric inequality

are

the cut vectors 6(S)

(S

<;-;

V

n

) for which b(S)

bi

is equal

to

0 or 1.

Proof. Given S

<;-;

V

n

,

integer.

bibjo(S)';j b(S)(1 -

b(S»

~

0, since b(S) is

an

I

We

remind

that

hypermetric inequalities contain as a special case the triangle

inequality:

(which is obtained by taking

bi

=

bj

:=

1,

bk

=

-1

and

bh

:=

0 for h E

Vn

\

{i,j,k}).

Since the O-lifting operation produces facets from facets,

we

obtain

that

the

inequality

Q(b)T x

~

0

is

facet inducing if

and

only if the inequality

Q(bll

x

~

0 is

facet inducing, where

b

'

is any vector obtained from b

by

adding zero components.

If

we

apply

the

permutation

operation to a hypermetric inequality or if

we

switch

it

by one

of

its

roots,

then

we

obtain again a hypermetric inequality. More

precisely, a

permutation

of

Q(b)T x

~

0 amounts to permuting the

b;'s.

Switching

the

inequality Q(b)T x

~

0 by

the

cut

o(S)

with

b(S) 0 yields the inequality

Q(b')T x

~

0, where

b~

=

-bi

if

i E S and

~

=

bi

otherwise.

In

other words,

switching a hypermetric inequality

by

a root amounts

to

changing

the

signs

of

some coefficients

of

b.

If

we

switch the inequality

Q(bl

x

~

0 by a

cut

vector O(S) which is not a

root

of it,

we

obtain

an

inequality which is valid for the

cut

polytope

CUT~

(but

not for the cut cone

CUT

n). For example, the inequality:

L

Xij

~

k(k+

1)

1

:5i<j

:S2k+l

is a switching of the inequality

Q21<:+1(1,

...

, 1,

-1,

...

,

-l)T

x

~

O.

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

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