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

344

Chapter

23.

Hypercube Embeddings of

the

Equidistant

Metric

Remark

23.1.6.

The

parameters (k,

A)

with

3

15

for which there ex-

ists a symmetric

(n, k, A)-BIBD (then, n = 1 + by (23.1.1» have been

completely classified (with

the

exception

of

k 13, 1 corresponding

to

the

question of existence of

PG(2,

12»

(see Biggs and

Ito

[1981]). Besides

the

pa-

rameters

corresponding

to

a projective plane, or

to

a

Hadamard

design, or

to

a

dual

of

them,

a symmetric (n,

k,

A)-BIBD exists if

and

only if (n,

k,

A)

is

one of

the

following list: (16,6,2), (37,9,2), '(25,9,3), (16,10,6) (which

is

dual

to

the

case

(16,6,2)),

(56,11,2), (31,10,3), (45,12,3), (79,13,2), (40,13,4), (71,15,3)

and

(36,15,6). I

A useful notion is

that

of extension of a design. Let

13

be

a collection of

subsets

of

Vn

and

let

io

rt.

V

n

. Given

an

integer

.'I,

the .'I-extension

of

13

is

the

collection

13

1

whose blocks are

the

blocks of

13

together with

the

block

{io}

repeated

s times.

23.1.2

Intersecting

Systems

Let A

be

a collection of subsets of a finite set

and

let r, A be positive integers.

Then,

A

is

called a (r,

A)-intersecting

system

if

IAI

r for all A E A

and

IA

n BI = A for all distinct A, B E

A.

The

maximum cardinality

of

a (r,

A)-

intersecting system consisting of subsets of

Vb

is

denoted by

f(r,

A;

b).

A is called a

l::.-,~ystem

with

center

K

and

parameters

(r,

A)

if

IKI

=

A,

IAI

= r for all A E

A,

and

An

B K for all distinct

A,

B E

A.

Clearly,

if

A

consists

of

subsets of

Vb,

then

IAI

::;

Remark

23.1.7.

(r,

A,

n)-designs

and

(r, A)-intersecting systems are basically

the

same

objects. Namely, let M

be

a n x b binary matrix, let

13

denote

the

family

of

subsets of whose incidence vectors are

the

columns

of

lvI,

and

let

A denote

the

family of subsets of

~'b

whose incidence vectors are

the

rows of

M.

Then,

13

is a (r,

A,

n)-design

if

and

only if A is a (r, A)-intersecting system

of

cardinality n. Moreover,

13

is trivial

if

and

only if A is a l::.-system.

As

a

reformulation of Theorem 23.1.3,

f (r,

A;

b)

::;

b holds. These two terminologies

of

(r,

A,

n)-designs

and

intersecting systems are commonly used in the literature;

this is why

we

present

them

both

here. Moreover,

we

will need intersecting

systems

in

Section 24.3.

Note also

that

partial

projective planes of order t (with n lines)

and

(t

+ 1,1)-

intersecting systems (with

n members) are exactly the same notions

and

they

correspond to (t + 1,1, n)-designs (trivial

partial

projective planes or

corresponding

to

l::.-systems). I

By

the

above remark, intersecting systems arise as the h-Iabelings of

the

equidistant metric. Namely,

Proposition

23.1.8.

There is a

one-to-one

correspondence between the

h-

labelings

of

the equidistant

metric

2tlt

n

and

the (2t,

t)-intersecting

systems

of

23.2

Embeddings

of

2tl

n

and

Designs

345

cardinality n

1.

Proof. Indeed,

in

any h-Iabeling

of

2tl

n

,

we

may assume

that

one

of

the

points

is labeled by 0

and

then

the

sets labeling

the

remaining n - 1 points are the

members

of

a (2t, t)-intersecting system. I

Hence,

Theorem

23.1.9 below from Deza [1973b] follows as a reformulation

of

Theorem

22.0.6.

Theorem

23.1.9.

Let t

~

1

be

an integer and let A

be

a

(2t,

t)-intersecting

system.

If

IAI

~

t

2

+ t + 2, then A

is

a tl-system. I

As

an

application

of

Theorem

23.1.9, Deza

[1974]

proved

the

following result, solving

a conjecture

of

Erdos

and

Lovasz.

Theorem

23.1.10.

Let t

~

1

be

an integer and let A

be

a collection

of

subsets

of

a

finite set such that IA

n BI = t for all A I: B E

A.

Set k

max(IAI:

A E

A).

If

IAI

~

k

2

-

k + 2, then A is a t:.-system. I

We conclude

with

an

easy application,

that

will be needed later.

Lemma

23.1.11.

Let k, t

~

1

be

integers such that t < k

2

+ k + 1 and let A

be

a

(k

+ t, t)-intersecting system.

If

IAI

~

k

2

+ k + 3, then A is a

tl-system.

Proof. Let

A1

E A

and

set

A'

:=

{Al'lA1 I A E

A\

{Ad}.

One checks easily

that

AI is a (2k, k)-intersecting system

with

IAII

~

k

2

+ k +

2.

By

Theorem

23.1.9,

AI is a

tl-system.

Let K denote its center,

IKI

= k. Let A E

A,

A

=1=

AI.

Set

alAI

n

KI,

then

IAI

n

((Al'lAt)

\

K)I

= k - a since

Al

n

(Al'lA

1

)

Al

\ A

has

cardinality

k.

If

a::; k 1,

then

implying t

~

(k a)(k2 + k + 1), contradicting the

assumption

on

t.

Hence,

a = k, \

A.

K and, thus,

Al

n

A.

=

Al

\

K.

This

shows

that

A is a

tl-system.

I

23.2

Embeddings

of

2tln

and

Designs

Let t, n

~

1 be integers. Every :l+-realization of 2tJl

n

is

of

the

form

(23.2.1)

2t1

n

=

o(E),

where B is a collection

of

(not necessarily distinct) subsets

of

V

n

.

Let k

~

1 be

an

integer.

The

realization (23.2.1) is said

to

be k-uniform if

lEI

= k, n k for

346

Chapter

23.

Hypercube

Embeddings

of

the

Equidistant

Metric

all E E

B.

It

is very easy

to

construct

IZ+-realizations

of

the

equidistant

metric

from designs.

For

instance,

let

B

be

a

(r,

A,

n)-design.

Then,

L

6(E)

= 2(r -

A)ln.

BEB

Moreover,

if

r

;::::

2A,

then

the

(r - 2A)-extension

of

B yields a IZ+-realization

of

2(r -

A)ln'

namely,

L 6(E) + (r - 2A)6({io}) = 2(r -

A)ln+h

BEB

where

V

n

+

1

\

Vn

= {io}.

In

particular,

each (t +

1,I,n)-design

yields a

IZ+-

realization

of

2t1

n

and

its

(t -

I)-extension

yields a

realization

of

2t1

n

+l.

Also,

the

O-extension

of

a (2t, t, n -

I)-design

gives a IZ+-realization

of

2t1

n

.

If

B is a (n, k, A)-BIBD,

then

(23.2.1) is a IZ+-realization

of

the

equidistant

metric

2A

~=~

In.

In

particular,

if

B is a

Hadamard

design

of

order

4t - 1,

then

(23.2.1) is a IZ+-realization

of

2t14t-l

and

the

O-extension

of

B yields a

IZ+-realization

of

2t14t.

If

B is

PG(2,

t),

then

(23.2.1) is a

IZrrealization

of

2t1

t

2+t+l

and

the

(t -

I)-extension

of

B yields a IZ+-realization

of

2t1

t

2+t+2'

The

makes precise

the

correspondence

between

IZ+-realizations

of

the

equidistant

metric

and

designs.

The

first

assertion

(i) is

nothing

but

a

reformulation

of

Proposition

23.1.8 (using

the

link

between

intersecting

systems

and

designs,

explained

in

Remark

23.1.7).

Proposition

23.2.2.

(i)

There is a one-to-one correspondence between the IZrrealizations

of

2t1

n

and the (2t, t, n -

1)

-designs.

(ii) For k

i=

~,

there is a one-to-one correspondence between the k-uniform

IZrrealizations

of

2t1

n

and the

(n, k,

t(:-=-~))-BIBD

'so

Proof. (i) follows by

assuming

that

all

blocks E E B

do

not

contain

a given

point

io

of

Vn

(replacing,

if

necessary, E by

Vn

\

E).

(ii)

It

is

immediate

to

check

that

(23.2.1) holds

if

B is a (n, k,

t(:-=-~))_BIBD.

Suppose

now

that

(23.2.1) holds,

with

lEI

= k for all E E B,

and

k

i=

~.

By

taking

the

scalar

product

of

both

sides

of

(23.2.1)

with

the

all-ones vector,

we

obtain

that

the

number

b

of

blocks satisfies

b =

tn(n

-1).

k(n - k)

We show

that

each

point

belongs

to

the

same

number

of

blocks. For

this,

let

r

denote

the

number

of

blocks

that

contain

the

point

1

and

denote

by

ai

the

number

of

blocks

containing

both

points

1

and

i, for i = 2,

...

,n.

Then,

~2<i<n

ai

=

r(k

-1).

Counting

in

two ways

the

total

number

of

units

in

the

incidence-matrix

of

B

(summing

over

the

columns

or

over

the

rows),

we

obtain

bk

= r + L (2t - r + 2ai),

2:'Oi:'On

23.3

The

Minimum h-Size of

2tl

n

347

implying

l'

= t

~=~.

Hence, any two points of

Vn

belong to

l'

t = t

!=k

common

blocks. Therefore,

B is a (n, k, I

It

is convenient for further reference to reformulate Theorem 22.0.5

in

terms

of

designs. As

can

be easily verified,

the

above proof

of

Theorem 22.0.5

permits

to

formulate

the

following sharper statement.

Theorem

23.2.3.

Suppose that n

;:::

~(t

+

2)2

with t

;:::

3, or that n >

!(t

+

2?

with t

2.

Let B

be

a family

of

subsets

of

Vn

for which (23.2.1) holds and

defines a nontrivial hypercube embedding

of

2tl

n

•

Then B is equivalent, either

to

a nontrivial

(t

+ 1,1, n)-design, or

to

the (t - I)-extension

of

a nontrivial

(t + 1,1, n I)-design. I

Take, for instance, 3 and n =

12

«

!(t

+ 2)2). Then,

61

12

has a

Z+-realization which is

not of the form indicated

in

Theorem 23.2.3; such a real-

ization can be obtained from the I-extension

of

a (5,2,1l)-design.

The

following

result of McCarthy

and

Vanstone

[1977]

will yield a new case

of

h-rigidity for

the

equidistant metric.

Theorem

23.2.4.

Let

0:,

t

be

positive integers such that t >

20:

2

+

30:

+ 2 (i.e.,

0:

< Suppose that PG(2, t)

does

not exist. Then, for n

;:::

t

2

-

0:,

each

(t + 1,1, n )-design is trivial. I

Corollary

23.2.5.

Suppose that PG(2, t)

does

not exist.

lfn>

t

2

+1-

~-3,

then the metric

2tl

n

is h-rigid.

Proof. Let B

be

a family

of

subsets of

Vn

for which (23.2.1) holds

and

defines a

nontrivial hypercube embedding

of

2tl

n

.

By Theorem 23.2.3, B is equivalent to

a

(t + 1,1, n)-design or

to

the

(t - I)-extension

of

a (t +

1,1,

n - I)-design (as

n;:::

!(t

+ 2)2). By Theorem 23.2.4, such designs are trivial. Hence, B yields

the

star

realization

of

2tl

n

,

a contradiction. I

23.3

The

Minimum

h-Size

of

2tln

Recall

that

the

minimum h-size

of

2tl

n

is defined as the smallest cardinality

of

a multiset B

~

2

v

"

satisfying (23.2.1);

it

is denoted by

sh(2tl

n

).

(The notion

of

minimum

h-size was introduced in Section 4.3.)

The

following result is a

reformulation of Ryser's result on

the

number

of

blocks of a (2t, t, n I)-design.

Theorem

23.3.1.

(i)

sh(2tl

n

)

;:::

n 1, with equality

if

and only

if

n = 4t and there exists a

Hadamard matrix

of

order 4t.

348

Chapter

23. Hypercube

Embeddings

of

the

Equidistant

Metric

(ii)

Suppose n

=I-

4t.

If

n = 2t + A +

t(t~l)

for some integer A

:::::

1 and

if

there

exists a symmetric

(n, A + t, A)-BIBD, then

sh(2t.D.

n

)

= n.

Proof. (i) By

Proposition

23.2.2,

the

minimum

h-size of

2t.D.

n

is equal

to

the

minimum

number

of

blocks

in

a (2t, t, n - I)-design, which is greater

than

or

equal

to

n -

1,

by

Theorem

23.1.3.

If

sh(2t.D.

n

)

= n - 1,

then

there

exists a

(2t, t, n - I)-design B

with

n - 1 blocks. Applying again

Theorem

23.1.3,

we

deduce

that

B

is

a

symmetric

(4t -

1,

2t, t)-design, Le., a

Hadamard

design of

order

4t

-

1.

The

assertion (ii)

can

be easily checked. I

As

an

application

of

Theorem

23.3.1

and

Remark

23.1.6,

we

deduce

that

sh(2t.D.

n

)

= n for

the

following

parameters

(t,n): (7,37), (6,25), (9,56), (7,31),

(9,45), (11,79), (9,40), (12,71). Note also

that

sh(2t.D.

n

)

= n - 1 for

(t,n)

=

(9,36), (4, 16).

The

implication

from

Theorem

23.3.1 (ii) is,

in

fact,

an

equivalence

in

the

cases A = 1 (i.e., n = t

2

+ t + 1)

and

A = t (Le., n =

4t

- 1).

Proposition

23.3.2.

(i)

Sh(2t.D.

t

2+t+l)

= t

2

+ t + 1

if

and only

if

there exists a projective plane

of

order

t.

(ii) sh(2t.D.4t-l) = 4t

-1

or,

equivalently,

sh(2t.D.4t)

=

4t

-1

if

and only

if

there

exists a Hadamard design

of

order 4t -

1.

(iii) Suppose

PG(2,

t)

exists. Then,

sh(2t.D.

t

2+t+2)

= t

2

+ 2t

if

t

:::::

3 and

sh(2t.D.t2+t+2)

= t

2

+ t + 1

if

t =

1,2.

(iv) Suppose

PG(2,

t) does not exist.

If

n > t

2

+ 1 -

y'8t:;-7-3,

then

sh(2t.D.

n

)

=

nt.

Proof. (i) follows from

Theorems

22.0.4

and

23.3.1.

(ii) Suppose

B is a block family yielding a Z+-realization of 2t.D.4t-l

with

IBI

=

4t -

1.

Then,

IBI

=

r~L~)Jt

(n

= 4t - 1), which implies

that

all blocks of B have

size

2t. Hence, B is a

Hadamard

design of order

4t

-

1.

The

remaining of (ii)

follows from

Theorem

23.3.1.

(iii) For

the

case t =

1,2,

use

Theorem

23.3.1. Suppose t

:::::

3

and

set n

:=

t

2

+ t +

2.

The

(t -

I)-extension

of

PG(2,

t) yields a Z+-realization

of

2t.D.

n

of

size t

2

+ t, implying

sh(2t.D.

n

)

:S

t

2

+ 2t. Let B

be

a block family yielding a Z+-

realization

of

2t.D.

n

.

We show

that

IBI

:::::

t

2

+ 2t.

This

is

obvious if B corresponds

to

the

star

realization. Otherwise,

we

can

use

Theorem

23.2.3.

Either,

B is

equivalent

to

a nontrivial

(t+

1,1,

n)-design;

then,

its

(t-I)-extension

yields a Z+-

realization

of

2t.D.t2+t+3

distinct

from

the

star

realization,

in

contradiction

with

Theorem

22.0.6. Or, B is equivalent

to

the

(t - I)-extension of a

(t

+

1, 1,

n - 1)-

design

and,

then,

IBI

:::::

n-I

+t-I

= t

2

+2t.

This

shows

that

sh(2t.D.

n

)

= t

2

+2t.

Finally, (iv)

is

a reformulation of Corollary 23.2.5. I

23.3

The

Minimum

h-Size of

2t:D.

n

349

Set

t f

n

(n-1)t1

f

2t1

an

:=

lIJ

III

=

4t

-

III

.

By

taking

the

scalar

product

of

both

sides of (23.2.1)

with

the

all-ones vector,

we

obtain

the

following bounds:

The

equality

sh(2t:D.

n

)

=

nt

holds if

and

only if

the

star

realization (22.0.1)

is

the

only Z+-realization

of

2t1

n

,

i.e., if

2t:D.

n

is h-rigid.

This

is

the

case, for instance, if n

2:

t

2

+ t + 3 (by

Theorem

22.0.6). Several

other

results

about

classes of

parameters

n, t for which

2t:D.

n

is h-rigid have

been

given in

Chapter

22.

A

natural

question is

what

are

the

parameters

n,

t for which

the

equality

holds.

If

2t:D.

n

admits

a Z+-realization

L:s

>'s8(S) where

>'5

> 0 only if

8(S)

is

an

equicut (i.e., satisfies

lSI

= liJ, lil),

then

the

equality

Sh(2tl

n

)

=

a~

holds.

For instance,

Sh(417) =

a¥

= 7

and

Sh(418) =

a§

= 7, as each of 417

and

418

has a

Z+-realization

using only equicuts (see

Proposition

23.4.4).

Clearly (from

Theorem

23.3.1),

the

equality

sh(2t:D.

n

)

=

a~

can occur only if

n

:::;

4t.

The

case n =

4t

is

well understood: equality holds if

and

only if

there

exists a

Hadamard

matrix

of order 4t.

The

following conjectures are

posed

by

Deza

and

Laurent

[1993c].

Conjecture

23.3.3.

Suppose

that

n

:::;

4t

and that there exists a Hadamard

matrix

of

order

4t.

Then,

sh(2t:D.

n

)

=

a~.

Conjecture

23.3.4.

Suppose

that

n

:::;

4t

and

that there exist Hadamard

matri-

ces

of

suitable orders. Then,

sh(2t:D.

n

)

=

a~.

Conjecture

23.3.4 is obviously weaker

than

Conjecture 23.3.3

(the

word "suit-

able"

remains

to

be

defined

in

an

appropriate

way). We refer

to

Deza

and

Laurent

[1993c] for

partial

results

In

particular,

the

following results are proved there.

Proposition

23.3.5.

(i) Conjecture 23.3.3 holds

for

all

n,

t such

that

n

:::;

4t,

and

¥-

<

II

l

or

min(

n,

t)

:::;

20.

(ii) Conjecture 23.3.4 holds for all

n,

t

such

that

n is even

and

satisfies

2V2t

:::;

n

:::;

4t.

(It

suffices to

assume

the existence

of

Hadamard

matrices

of

orders

2n,

4n,

and

n

(if

i is

even)

and n + 2

(if

i is odd).) I

350

Chapter

23.

Hypercube Embeddings of

the

Equidistant

Metric

Corollary

23.3.6.

If

n

:S

4t

:S

80

then

sh(2t:D.

n

)

=

a~.

I

Example

23.3.7.

As

an

example, let us consider the

minimum

h-size

of

the

metric

2t:D.

n

for t = 6

and

n

2:

31.

We

have:

(i)

sh(l211

n

)

=

6n

for all n

2:

33

(by Proposition 22.0.11),

(ii)

sh(12132)

= 67

and

sh(121131)

:S

62.

Indeed, let

B

be

a block design on V

32

for which (23.2.1) holds

and

defines a non-

trivial

hypercube

embedding of 12132. By Theorem 23.2.3, B is equivalent

to

a

(7,1,32)-design, or

to

the

5-extension of a (7,1,31)-design. Each (7,1,32)-design is

trivial

(as its 5-extension yields a Z+-realization of

the

h-rigid metric

121133).

It

is shown

in

McCarthy, Mullin, Schellenberg,

Stanton

and

Vanstone [1976, 1977]

that

the

unique nontrivial (7,1,31)-design

is

the

block family obtained by taking

the

blocks

of

PG(2,

5)

together

with

the

31

singletons; it yields a Z+-realization

of

121131

of

size

31

+

31

= 62. Its 5-extension yields a Z+-realization

of

121132

of

size

62

+ 5 = 67.

This

shows

that

sh(121132)

= 67. I

23.4

All

Hypercube

Embeddings

of

2tlln for

Small

n,

t

We list all

the

Z+-realizations of the equidistant metric

2t:D.

n

in

the

following

cases: t =

1,

t =

2,

n =

4,

and

we

give

partial

information in

the

case n =

5.

The

results are

taken

from Deza

and

Laurent [1993c].

Let t,

n

be

positive integers. For each integer s such

that

t -

ln~3J

:S

s

:S

t,

we

have

the

following Z+-realization of

2t:D.

n

:

(23.4.1)

2t:D.

n

=

(t-(n-3)(t-s))8({n})+

L

(t-s)8({i,n})+s8({i}).

l:<;i:<;n-l

Its

size is equal to

(n

-

3)s

+

3t

and

(23.4.1) coincides with

the

star

realization

(22.0.1) for s = t.

Proposition

23.4.2.

(Case

n = 4)

The

metric

2t:D.4

has

t + 1

Z+-realizations,

given

by (23.4.1)

for

0

:S

s

:S

t.

Proof.

This

follows from

the

fact

that

the restriction to

V3

of

any Z+-realization

of

2t:D.4

coincides with

the

star

realization of

2t:D.3.

I

Proposition

23.4.3.

(Case

t = 1) For n I- 4, (22.0.1) is

the

only

Z+-

realization

of

the

metric

21n

and,

for

n = 4, 214

has

two

Z+-realizations:

the

star

realization

(22.0.1)

and

(23.4.1)

for

s = 0,

namely,

2114=2:1:<;i:<;48({i})

=8({1,4})

+8({2,4})

+8({3,4}).

I

23.4 All Hypercube Embeddings of

2tln

for

Small

n,

t

351

Proposition

23.4.4.

(Case

t = 2)

(i)

For n

2:

9,

(22.0.1) is the only Z+-realization

of

4lL

n

.

(ii) For n =

4,

4lL4

has three Z+-realizations: (22.0.1) and (23.4.1) for s = 0,1,

namely,

4lL4

=

2(

:E

8({i}))

=

2(

:E

8({i,4}))

=

:E

8({i})

+

:E

8({i,4}).

(iii) For n = 5, 415 has (up

to

permutation) three Z+-realizations: the

star

realization (22.0.1), (23.4.1)

for

s =

1,

i.e.,

4lL5

=

:E

8({i,5})

+8({i}),

and

1$i$4

4lL5=8({5})+

:E

8({i,j}).

1$i<j$4

(iv) For n =

6,

4lL6

has (up to permutation) three Z+-realizations: the

star

realization (22.0.1),

4lL6

= 8({2}) +8({3})

+8({4,6}) +8({5,6}) +8({1,4})

+8({1,5})

+8({1,2,6})

+8({1,3,6}),

and

4lL6

= 8({1,2})

+8({3,4}) +8({5,6})

+8({1,3,6})

+8({2,4,6})

+8({1,4,5}) +8({2,3,5})

+8({1,3,6}).

(v) For n =

7,

4lL7

has (up to permutation) three Z+-realizations: the

star

realization (22.0.1),

4lL7

= 8({7})

+8({1,2}) +8({3,4}) +8({5,6})

+8({1,3,6})

+8({2,4,6})

+8({1,4,5})

+8({2,3,5}),

and

4lL7

=

8(

{I,

2,

7})

+

8(

{3,

4,

7})

+

8(

{5,

6,

7})

+

8(

{I,

3,

6})

+8(

{2,

4,

6})

+

8(

{I,

4,

5}) +

8(

{2,

3,

5}).

(vi) For n =

8,

4lL8

has (up to permutation) three Z+-realizations: the

star

realization (22.0.1),

418 = 8({8})

+8({1,2,7})

+8({3,4,7})

+8({5,6,7})

+8({1,3,6})

+8({2,4,6}) +8({1,4,5})

+8({2,3,5}),

and

4lL8

= 8({1,2,7,8})

+8({3,4,7,8}) +8({5,6,7,8})

+8({1,3,6,8})

+8({2,4,6,8})

+8({1,4,5,8})

+8({2,3,5,8})

(corresponding to a Hadamard design).

I

352

Chapter

23.

Hypercube Embeddings

of

the Equidistant Metric

It

seems a

rather

difficult task

to

list all the Z+-realizations

of

the metric

2t1

n

in

the case n

5.

Note

that

we

already have the realizations (23.4.1) for

t -

L~J

S;

li

S;

t. For t

odd

and t

2:

3,

we

also have

2t15

(23.4.5)

t21 (6( {5}) +

6(

{I,

2})

+

6(

{I,

3}) +

6(

{2,

4})

+

6(

{3,

4}»

H{{1,5})

+6({2})

+6({3})

+6({4,5})

+t¥6({1,4})

+ t236({2,3}).

The

following is also a Z+-realizations

of

2t15:

2t15

p6({5})+q6({1})+(8-q)6({1,5})+a

L 6({i,5})

2SiS4

(23.4.6)

+(8-a)

L

6({i})+/3

L 8({1,i})

2<i<4

+(t

8

6(

{I,

i~

5}),

where

a,

,a,p,

q,,5

are integers satisfying

{

OS;

8

S;

t,

OS;

0:

S;

mines, !),

max{O,

s -

20',

t-;"')

S;

p

/3

= t -

20'

p,

q =

30'

+

2p

-

t.

min(t -

20',

t-

3

f+

S

),

Let )..(s,t,a,p) denote the realization from (23.4.6).

For t = 3, the feasible parameters for (23.4.6) are

a,p)

=(1,0,2), (1,1,0),

(2,0,2), (2,1,0), (2,1,1), (3,0,3), (3,1,1), (3,0,3),

and

(3,1,1). Note, however,

that

),,(3,3,0,3) coincides

with

the

star

realization (22.0.1); ),,(3,3,1,1) reads

(23.4.7)

615

= 6({5}) + L 8({i,5}) + 26({i})

ISiS4

(tbis is (23.4.1)

in

the

case t =

3,

n = 5,8 =

2);

),,(2,3,0,2) is a

permutation

of

(23.4.7);

and

,\,(2,3,1,1) coincides with ,\,(1,3,0,2) (up

to

permutation).

Proposition

23.4.8.

(Case

t = 3, n = 5) The metric

615

has five dist'inct (up

to permutation) Z+-realizations: the star realization

(22.0.1), (23.4.7), (23.4.5)

(with t 3), and (23.4.6) for the parameters (8,a,p) 1,1),

(2,

1,0),

(1,1,0)

'Which

read, respectively,

615

6({5}) +26({1}) + L 6({i,5})

+8({i})

+6({1,i,S}),

615

26({1,5})+

L

6({i,5})+6({i})+6({1,i}),

2SiS4

615 8({1,S}) +

6({i,S})

+6({1,i})

+6({1,i,5}).

I

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

Chapter

24.

Recognition

of

Hypercube

Embeddable

Metrics

In

this

chapter

we

consider

the

following problem, called

the

hypercube embed-

dability problem:

Given a distance d on V

n

,

test whether d is hypercube embeddable.

When

restricted

to

the

class of

path

metrics of connected graphs,

this

is

the

problem

of

testing

whether

a

graph

can

be

isometrically

embedded

into a

hypercube.

Such

graphs

have a good characterization

and

can

be

recognized

in

polynomial

time.

This

topic has

been

discussed

in

detail

in

Chapter

19.

The

hypercube

embeddability

problem is

NP-hard

for general distances;

it

is,

in

fact,

NP-complete

for

the

class of distances

with

values

in

the

set {2, 3, 4,

6}

(see

Theorem

24.1.8).

However,

the

hypercube

embeddability problem

can

be

shown

to

be

solvable

in

polynomial

time

for several classes of metrics.

This

is

the

case, typically, for

metrics

having a

restricted

range of values. For instance,

the

hypercube

em-

beddability

problem

is

polynomial-time solvable for

the

class of distances

with

range

of

values

{1,2,3},

or

{3,5,8}

or, more generally,

{x,y,x+y}

where

x,y

are

two positive integers

not

both

even.

This

class is discussed

in

Section 24.3.

We

consider in Section 24.4

the

distances

taking

two values of

the

form a, 2a where

a

2:

1 is

an

integer. Note

that

such distances

can

be

seen as scale multiples

of

truncated

distances

of

graphs. For

this

class

of

distances,

hypercube

embed-

dability

can

be

characterized by a finite

point

criterion

and,

thus,

recognized

in

polynomial

time.

We

also consider generalized

bipartite

metrics, which are

the

metrics d

on

Vn

for which

there

exists a

subset

S

<:;:

Vn

such

that

d(

i,

j)

= 2 for all i

=f.

j E

Sand

for all i

#-

j E

Vn

\

S.

The

hypercube

embeddable

generalized

bipartite

metrics

can

also

be

recognized

in

polynomial time; see Section 24.2.

The

basic idea which is used for characterizing

the

hypercube

embeddable

metrics

within

the

above classes

is

the

existence

of

equidistant

submetrics,

which

are h-rigid if

they

are defined

on

sufficiently

many

points

(by

the

results of

Chapter

22).

We present in Section 24.5

the

following result of Karzanov [1985]: Let d

be

a

metric

whose

extremal

graph

is K

4

,

C

5

,

or a union of two stars;

then,

d is

hypercube

embeddable

if

and

only if d satisfies

the

parity

condition (24.1.1).

Let us

point

out

that,

in

contrast

with

the

results from Section 24.3, no char-

acterization

is known for

the

hypercube

embeddable

metrics

taking

three

values,

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

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