Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,
DOI 10.1007/978-3-642-04295-9_21, © Springer-Verlag Berlin Heidelberg 2010
Chapter
21.
iI-Graphs
We
study
in
this
chapter
£I-graphs, i.e.,
the
graphs
whose
path
metric
can
be
isometrically
embedded
into
an
£I-space. Such
graphs
can
be
characterized as
the
isometric
subgraphs
of
Cartesian
products
of two
types
of elementary graphs,
namely, half-cube
graphs
and
cocktail-party graphs.
This
result has already
been
established
in
Part
II, using
the
theory of Delaunay polytopes.
We
present here
another
proof
due
to
Shpectorov
[1993]
which is elementary
and,
moreover, yields
a
polynomial
time
recognition algorithm. Section 21.4 contains
additional
results
on
£I-graphs;
in
particular,
a characterization
in
terms
of forbidden isometric
subspaces for isometric
subgraphs
of
half-cube graphs.
21.1
Results
on
£l-Graphs
As was recalled in
Chapter
18, a
graph
G is
an
£l-graph
if
and
only if
it
is
hypercube
embeddable,
up
to
scale. A A-embedding of G into
the
hypercube
H(o') is any
mapping
such
that
Ada(x,
y)
=
IX
L:,.YI
for all
nodes
x, y
of
G.
If
G has a A-embedding into a hypercube,
we
also say
that
G
is
hypercube
embeddable
with
scale
A.
A
I-embedding
in a
hypercube
is
nothing
but
an
isometric
embedding
in
a hypercube.
Three
classes
of
graphs
playa
crucial role
in
the
theory of £ I-graphs: complete
graphs, cocktail-party graphs,
and
half-cube graphs. All of
them
are £ I-graphs,
so is any
Cartesian
product
of
them.
Actually,
we
show below
that
any £I-graph
arises as
an
isometric
subgraph
of such a
Cartesian
product.
Complete
graphs
Km
(m
2 3)
and
half-cube
graphs
!H(m,2)
(m
2
3)
have
minimum
scale
2.
Note
that
1 1
2
H
(2,2)
= K
2
, 2
H
(3,2)
= K
4x2
,
and
Km
is
an
isometric
subgraph
of
both
Kmx2
and
!H(m,2).
The
following
holds clearly.
LeIllIlla
21.1.1.
A graph G is hypercube embeddable with scale 2 (that is,
2dc
is hypercube embeddable)
if
and only
if
G is an
isometric
subgraph
of
some
half-
314
Chapter
21.
iI-Graphs
cube graph.
I
On
the
other
hand, determining the minimum scale
of
cocktail-party graphs
is a
hard
problem. This problem
is
considered in detail in
Chapter
23; see
also Section
7.4.
We
already know from Theorem 19.2.8
that
every connected
bipartite
i'l-graph is hypercube embeddable. For nonbipartite graphs
we
have
the
following observation (Blake
and
Gilchrist [1973]).
Lemma
21.1.2.
Let G
be
an iI-graph and suppose that G has a A-embedding in
a hypercube.
If
G is
not
a bipartite graph, then A is an even integer. Therefore,
the
minimum
scale
of
an iI-graph
is
equal to 1 or is even.
Proof
Suppose
that
G
is
not bipartite. Let C
be
an
odd
circuit in G of minimal
length.
Then,
C is
an
isometric subgraph
ofG.
Say, C
(all
...
,a2k+d.
We
can
suppose
that,
in
the
A-embedding
of
G in a hypercube,
the
nodes al,ak+l,ak+2
are
labeled by
the
sets 0,A,B, respectively. Then, as dG(al'
ak+d
= dG(aI, ak+2)
k
and
dG(ak+l,ak+2)
1,
we
have A = IAt:.BI
and
IAI
=
IBI
=
>..k.
Hence,
A = 2Ak
21A
n BI. Therefore, A is
an
even integer. I
We
now present
the
main results
of
this chapter; they are
due
to Shpectorov
[1993].
Theorem
21.1.3.
Let G
be
an iI-graph. Then, there exist a graph G and an
isometric embedding
(f
from G into G such that
(i)
G G
1
X
•..
X
Gk1
where each
Gh
is isomorphic to a complete graph, a
cocktail-party graph
Kmx2
(m
2:
3),
or
a half-cube graph, and
(ii)
if
1j;
is a A-embedding
of
G into the hypercube, then there is a A-embedding
¢
of
G into the same hypercube such that
1j;
=
¢(f.
Corollary
21.1.4.
A connected graph G is an
iI
-graph
if
and only
if
all the
factors
in
its canonical metric representation
are
i
1
-graphs.
Coro1lary
21.1.5.
A connected graph G is an iI-graph
if
and only
if
G is an
isometric subgraph
of
a Cartesian product
of
cocktail-party graphs and half-cube
graphs.
Corollary
21.1.6.
Let G
be
an iI-graph. Then, G is
iI-rigid
if
and only
if
G
is i1 -rigid.
Corollary
21.1.7.
Every
iI-rigid
graph is an isometric subgraph
of
a half-cube
graph and, therefore, its
minimum
scale
TJ
is equal to 1
or
2.
Corol1ary
21.1.8.
Let G
be
an iI-graph on n
2:
4 nodes. Then its
minimum
scaleq
satisfiesq
~
n - 2.
21.1
Results
on
£l-Graphs
315
Corollary
21.1.9.
Let
G
be
a graph with n nodes and m edges. There exists an
algorithm permitting to decide whether
G is an £l-graph which runs
in
O(mn)
time
using O( n
2
)
space.
We present in Section 21.2 a concrete
construction
of
the
graph
G from
Theorem
21.1.3, using a specific A-embedding of G. We group in Section 21.3
the
proofs for
Theorem
21.1.3
and
Corollaries 21.1.4-21.1.9.
The
result
from Corollary 21.1.5 was already established in
Part
II
(in
The-
orem
17.1.1 (ii)), as
an
application
of
the
correspondence existing between De-
launay
polytopes
and
hypermetrics. However,
the
proof
method
developed
there
did
not
permit
to
obtain
further
results such as
the
characterization of £l-rigidity
and
the
fact
that
£l-graphs
can be recognized in polynomial time.
In
contrast,
the
proof
method
presented here uses only elementary notions.
It
is, in a way, a
continuation
of
the
theory
of canonical metric representations of graphs. Indeed,
the
essential
step
of
the
proof
will be
to
show
that
each factor in
the
canonical
metric
representation
of
an
£l-graph
can
be
further
embedded
into a complete
graph,
a cocktail-party graph, or a half-cube graph.
In
view
of
Corollaries 21.1.4
and
21.1.5, one can check
whether
a
graph
G
is
an
£l-graph
in
the
following way:
(i)
Construct
the
canonical metric representation
of
G.
(ii) For each factor G
h
in
the
canonical metric representation, check
whether
G
h
is
an
isometric
subgraph
of
a cocktail-party
graph
or of
a half-cube
graph.
Then,
G is
an
£l-graph
if
and
only if
the
answer
is
always positive
in
Step
(ii).
As was seen in
Remark
20.1.5,
Step
(i)
can
be performed in
O(mn)
time
using
O(
m)
space.
The
main
difficulty
in
Step
(ii) consists of recognizing
the
isometric
sub
graphs
of
the
half-cube graphs.
The
following result was already implicit
in
Shpectorov
[1993]; full details
about
the
algorithm
are provided in Deza
and
Shpectorov
[1996]. We will give
the
proof
in Section 21.3.
Proposition
21.1.10.
Let
G
be
a graph on n nodes with m edges. There exists
an algorithm permitting to decide whether
G is an isometric subgraph
of
some
half-cube graph which runs
in
O(mn)
time using
O(n
2
)
space. The algorithm
constructs an embedding
if
one exists.
Suppose
that
each factor Gh in
the
canonical metric representation of G
has
nh nodes
and
mh
edges, where
mh
2 nh - 1 as G
h
is
connected.
Then,
m 2
ml
+ ... +
mk
and
nh
:::;
n for all h. Therefore,
nlml
+ ... +
nkmk
:::;
nm.
Checking
whether
G
h
is
a
subgraph
of
a cocktail-party
graph
can
be
done in
O(n~)
time
and
space (simply check
that
every node
is
adjacent
to
all
other
nodes except
at
most one). Therefore,
the
overall
time
complexity for checking
whether
G
is
an
£l-graph
is
in
O(mn)
and
the
space complexity
in
O(n
2
),
as
claimed
in
Corollary 21.1.9.
316
Chapter
21.
iI-Graphs
21.2
Construction
of
G
via
the
Atom
Graph
In t,his section,
we
show how to construct
the
graph G from Theorem 21.1.3,
using a specific scale embedding
of
G.
It
will
turn
out
that,
in fact, G does
not
depend
on
the
choice
of
the
scale embedding
and
that
G is
an
isometric extension
of
t,he
canonical metric representation
of
G.
The
main
tool for
the
construction
of
G is
the
atom
graph
of
G, as
we
explain below.
Let
G = (V,
E)
be
an
iI-graph.
Let
be
a ),-embedding of G into
the
hypercube
H(n).
We
can suppose
without
loss
of
generality
that
n =
UXEV
X
and
that
a given node
Xo
E V is assigned to
0.
Set
(21.2.1)
Eo
:=
{e
(x,y)
EEl
da(xo,x)
i=
dG(xo,Y)}·
For
an
edge e =
(x,y)
E Eo,
we
can
suppose, e.g.,
that
Xo
E
G(x,y).
One
can
easily check
the
following statements:
(21.2.2)
IXI
= ),dG(xo,x) for all x E
V,
(21.2.3)
For
an
edge e = (x, y),
(21.2.4)
{
IX
\
YI
=
IY
\
XI
=
~
XS;;Y
if
e ¢ Eo,
if
e E
Eo.
Call
atom every set
of
the
form
XL".,.
Y corresponding to
an
edge e (x, y)
of
G,
and
proper atom every set of
the
form Y \ X corresponding to
an
edge
e
(x,y)
E (with
Xo
E
G(x,y)).
Atoms have
cardinality),
and
(21.2.5)
if
A,
B are distinct proper atoms,
then
IA
n BI
),
0,
We define
the
atom graph
A(
G) as
the
graph
with
node set
the
set of
proper
atoms
of
G
and
with
two proper atoms A, B being adjacent
if
IA
n
BI
~.
Let AI,
...
,
Ak
denote
the
connected components
of
A(G). For h = 1,
...
,
k,
let
nh
denote
the
union of
the
proper atoms
that
are nodes
of
A
h
.
Hence, each
proper
atom
is
either contained
in
n
h
,
or is disjoint from n
h
.
Actually,
the
same
property
holds for all atoms, as
we
show in
the
next result.
Claim
21.2.6.
Let A
be
an
atom
of
G. Then, for each h = 1,
...
, k, either
21.2
The
Atom
Graph
317
Proof. Let
(x,y)
be
an
edge of G corresponding to
the
atom
A,
i.e., A XL'1Y.
We
can
suppose
that
the
edge (x,
y)
does not belong
to
Hence,
the
node
Xo
is
at
the
same distance s from x
and
y. Let
(XO,Xl,""X.
x)
and
(Yo
=
Xo,
YI,
...
,Ys = y)
be
shortest
paths
from
Xo
to x
and
y in G. Hence,
x UBi, Y = U Ci,
l~i~s
ISiS'
where
Bi
is
the
proper
atom
Xi
\
Xi-I,
C
i
is
the
proper
atom
Yi
\ Yi-l' for
i = 1,
...
, s.
We
claim
that
X \ Y
~
Bio
for some
io
E {1,
...
,8}. Indeed, take a E X \ Y
and
suppose, for instance,
that
a E B
1
•
Then,
Bl
n Y ¥ B
1
•
On
the
other
hand,
B}
n Y ¥
0,
else
Bl
~
X \ Y
implying
that
IX
\
YI
Z:
A,
contradicting (21.2.4). As
the
cardinality of
Bl
'1
Y
is
a multiple
of
~
by (21.2.5),
we
obtain
that
IBI nYI =
~,
IBI
\
YI
=
~.
Therefore,
X \ Y =
Bl
\ Y
~
B
1
•
Similarly,
for some
jo E {I,
...
,8
}.
Furthermore, as
the
Cj'S are pairwise disjoint, each
Bi
either coincides
with
some
Cj,
or meets exactly two of them, unless
B,
= Bio
in which case
Bi
meets exactly one
Cj.
The
symmetric
statement
holds for
each
Ci. This means
that
the
subgraph
ofthe
atom
graph
A(G)
induced by
the
set
{B
1
,
•••
,
B.,
C
l
,
...
, C
s
}
consists
of
isolated nodes, cycles,
and
exactly one
path
whose endpoints are Bio
and
C
jo
' Let Aho
be
the
connected component
of
A(G)
that
contains this
path.
Then, Bio,
Cjo
~
nho'
which implies
that
A X
L'1Y
~
nlto'
Moreover, for h ¥
ho,
Bio, C
jo
are disjoint from
nit,
implying
that
A is disjoint from nit. I
Let denote
the
graph
with
node set
{X
:=
X n
nit
I x E
V}
and
with
(X,17)
being
an
edge if
IX
L'1171
=
A.
Set
C:=
II
Cit.
lSlt9
Claim
21.2.7.
(i)
Each
Ch
is
A-embedded
into
the hyperc7tbe
H(n
h
)
and
its
atom
graph A(CIt)
coincides with
A".
Oi)
C is A-embedded
into
the hypercube
H(n).
(iii) The
mapping
.1:
E V I-->
(X
'1 n
l
,
...
,X
n
nAJ
is
an
isometric
embedding
of
G
into
C.
Proof. Let x, y
be
two nodes of
G,
giving
the
two nodes
of
Cit.
We
show
318
Chapter
21.
iI-Graphs
Set s
:=
dc(x,
y)
and
t
:=
dOh
(X,
V). Let
(Yo
=
X,
Yl,
...
,Ys =
y)
be a
shortest
path
from x
to
y
in
G.
Then,
X.6Y
= L
Yi
\ Yi-l
l$i$s
is a disjoint
union
of
atoms. Let th denote
the
number
of
atoms
Yi
\ Yi-l
that
are
contained
in
Oh.
By
Claim 21.2.6,
we
obtain
Moreover,
we
have found a
path
oflength
th joining X
to
Yin
G
h
, which implies
that
th
2:
t. Let
(Zo
=
X,
Zl,
...
,
Zt
=
Y)
be a
shortest
path
joining
X
to
Y
in
G
h
.
So,
IX
L"YI =
I(X
.6Zd.6(Zl.6Z
2
).6
...
.6(Zt_l.6Y)
I ::; L
IZi-l.6Zil
= 0.
...
l$i$t
This
implies
that
th
::;
t
and,
therefore, th = t. Hence,
the
graph
Gh
is
A-
embedded
into
the
hypercube
H(Oh).
One
checks easily
that
its
atom
graph
is
A
h
.
Hence, (i) holds. Moreover,
(X
n 0
1
,
•••
,X
n Ok)
.......
U(X
n Oh) = X
h
provides a A-embedding
ofG
l
x
...
X
Gk
into
the
hypercube
H(O),
showing (ii).
It
also follows
that
dc(x,
y)
= L
dOh
(X
nOh,
Y n Oh)
l$h$k
for all nodes
x,
y E
V.
This
shows (iii).
I
We now show
that
each factor G
h
can
be
further
embedded
into
some
graph
G
h
which is isomorphic
to
a complete
graph,
a cocktail-party
graph,
or
a half-
cube
graph.
We first deal
with
the
case when
the
atom
graph
A(
G) is connected,
i.e.,
when
k =
1.
Then,
the
graph
G is nothing
but
the
graph
G
embedded
into
the
hypercube
H(O).
Claim
21.2.8.
If
A( G) is connected,
then
there exists a
unique
minimal
graph
G
containing
G as
an
isometric
subgraph
and
such
that
G is
isomorphic
to a
complete graph, a cocktail-party graph
Kmx2
(m
2:
3),
or
a half-cube graph.
Moreover,
G is A-embedded
into
the hypercube
H(O).
Proof. We
distinguish
three
cases.
Case
1: A(G) is a complete graph.
Then,
G itself
is
a complete
graph
and
G = G. Indeed, each node x
is
adjacent
to
Xo
(else, X would be a disjoint
union
of
the
proper
atoms
corresponding
to
the
edges
of
a
shortest
path
from
Xo
to
21.2
The
Atom
Graph
319
x). For two nodes x, y E V, X and Y are adjacent proper atoms, implying
that
IX.6.YI = A and, therefore, x
and
y are adjacent in
G.
(In fact, A(Kn) =
Kn-d
Case
2:
A(
G) is not a complete
graph,
but
is
an induced
subgraph
of
a cocktail-
party
graph.
Let A, B be two proper atoms
at
distance 2 in A(G). Each
other
proper
atom
a is adjacent to
both
A
and
B,
which implies
that
a
<:;;
Au
B.
Hence, for each node x E
V,
X
is
contained in
the
2A-element set A U
B.
We
claim
that
G is an induced subgraph
of
a cocktail-party graph. Indeed, any two
nonadjacent nodes in
G are necessarily
at
distance 2 since
IX
.6.YI
:::;
2A
for all
x,y
E
V.
Moreover, each node x
is
adjacent to all
other
nodes except maybe
one, which is
then
labeled by
the
complement of
X.
Then,
we
take for G
the
cocktail-party graph K
mx
2,
obtained by adding
an
"opposite" node labeled by
the complement
of
X for each node x which
is
adjacent to all
other
nodes in
G.
Hence, G is A-embedded into the same hypercube
H(n).
Moreover, m
~
3.
Otherwise, G would be a sub graph of K2x2, which implies
that
Gis
P.3
or a
4
in
which cases
A(
G) consists of two isolated nodes.
Case
3:
A(
G)
is
not an induced
subgraph
of
a cocktail-party
graph.
We
show
that
G
can
isometrically embedded into a half-cube graph.
First,
we
claim the
existence of distinct proper atoms
A,
B,
a,
D satisfying
{
Ana
=0,
AnD=0,
a is adjacent
to
D in
A(
G),
B
is
adjacent to A
and
a
in
A(
G).
Indeed, let A, a be two proper
atoms
at
distance 2 in A(G)
and
let B be a proper
atom
adjacent
to
A
and
a.
Suppose for contradiction
that,
for each
proper
atom
D,
D is adjacent to A if
and
only if D is adjacent
to
a.
If
D is adjacent to A
and
a,
then
D
Au
C.
If
D'
is adjacent to A
and
a
and
D is adjacent
to
D',
then
D meets A
or
C and, thus, D is adjacent
to
both
A
and
a,
implying D
<:;;
AUC.
By connectivity
of
the atom
graph
A(G),
we
deduce
that
each
proper
atom
D
is contained
in
A U
C.
Therefore, if
D,
D'
are disjoint proper atoms,
then
D'
is
the
complement
of
D.
This shows
that
each proper atom is adjacent to all
other
proper
atoms except
at
most one, contradicting
the
assumption
that
A(G) is not
a
subgraph
of
a cocktail-party graph.
Let
us
call a half each set
of
the form
An
B or A \
B,
where A, B are adjacent
proper
atoms. Each half has cardinality i
and
each proper atom
is
the
disjoint
union
of
two halves.
We
claim
that
(21.2.9) distinct halves are disjoint.
If
(21.2.9) holds then, for each node x E V, X
can
be uniquely expressed as a
disjoint union of halves. Indeed, if
(xo,
xl,'
..
,Xs
=
X)
is a shortest
path
from
Xo
to x
in
G,
then
X UI<i<sXi \
Xi-l
where each proper atom
Xi
\
Xi-l
is
the
union
of
two halves;
this
set of halves does not
depend
on
the choice of
320
Chapter
21.
iI-Graphs
the
shortest
path.
This
gives
an
isometric embedding of G into
the
half-cube
graph
G defined on
the
set of halves. By construction, G is A-embedded into
the
hypercube
H(f/,).
We
now show
that
(21.2.9) holds. As A(
G)
is connected,
we
can order
the
proper
atoms
AI,
A
2
,
...
, AI' in such a way
that
each
Aj
(j
2::
2)
is adjacent
to
at
least
one
As, s <
j.
We
suppose
that
Al
A2
B,
A3 = C, A4
D.
We
show by
induction
on j
2::
4
that
the distinct halves
that
are created by the first j
proper
a toms A I,
...
,Aj
are pairwise disjoint.
Consider first
the
case j 4. By construction,
the
halves
HI
= A \
B,
H2 =
An
B,
H3
= B n C,
H4
C \ B are disjoint. Consider
the
half
enD.
Since
B n D = B n
enD
(C
n
D)
n has cardinality 0 or
~,
we
obtain
that
enD
is equal
to
H3 or H
4
•
The
half D \ C is disjoint from
HI,
Hz,
H3, H
4
•
We
suppose now
that
all halves in
the
set
1t
of
the
halves created by
the
first
j 1
(j
2::
5)
proper
atoms are pairwise disjoint. Call two halves
H,
H'
E
1t
neighboring
if
H u
H'
is a proper
atom
As for some s <
j.
This defines a
graph
structure
on
1t.)
for which
1t
is connected. Suppose
that
Aj
is
adjacent
to
As,
for s <
j,
and
let As
Xl
U X
2
with
XI,X2
E 1t. Suppose
that
Aj
n As
is
not
equal
to
nor
to
Set
0:
IAj
n
XII
and
(3
=
IAj
n X2, where
0:,
(3
> 0
and
0:
+
(3
~.
If
Y
l
,
are two neighboring halves
and
IAj
n
Yil
=
0:
or
(3,
then
IAj
n
Yzi
(3
or
Q,
respectively. By connectivity of 1t,
we
deduce
that
Aj
n YII
0:,
IAj
n
Y21
(3,
or vice versa, for every pair
(Y
l
,
Y2)
of neighboring
halves. Now,
IAj
n
(HI
U
Hz
U H3 U H4 U H
5
)1
= 2(0: +
(3)
+
0:
or 2(0: +
(3)
+
(3,
which is greater
than
A,
yielding a contradiction. Therefore,
Aj
n
As
is
equal
to
or Hence,
Aj
\
As
is either a half from
1t
or a new
half
disjoint from all
halves
in
1t.
This
concludes
the
induction,
and
the
proof
of
Claim 21.2.8. I
Claim
21.2.10.
If
A(G) has k connected components AI,
...
,
AI"
then there
exists a
unique
minimal
graph G containing G as
an
isometric
subgraph
and
such
that
G=
II
Gh,
l~h~k
where each
factor
G h is isomorphic to a complete graph, a cocktail-party graph
Kmx2
(m
2::
3),
or
a half-cube graph. Moreover, G is A-embedded
into
the hy-
percube
H(f/,).
Proof.
As
the
atom
graph
A(Gh)
= Ah is connected,
we
can apply Claim 21.2.8.
Hence, for each h = 1,
...
,
k,
there exists a unique minimal
graph
Gh which
contains
Gh
as
an
isometric subgraph
and
is isometric
to
a complete graph, a
cocktail-party
graph
Kmx2
(m
2::
3), or a half-cube graph. Therefore,
G
'->
G =
II
Gh,
l~h~k
providing a minimal
graph
G satisfying Claim 21.2.10. Moreover, G is
A-
embedded
into
H(f/,)
as each factor Gh
is
A-embedded into
H(f/,h)
and
the
sets
f/,h
are disjoint subsets of f/,. I
21.2
The
Atom
Graph
321
Remark
21.2.11.
Each
of
the
graphs
Gh
is
irreducible since
it
is
an
isometric
subgraph
of
a
complete
graph,
a
cocktail-party
graph
on
at
least
6 nodes,
or
a
half-cube
graph,
which are all irreducible
graphs.
As
the
embedding
G
'-+
G is
clearly
irredundant,
we
deduce from
Theorem
20.1.1
that
the
metric
representa-
tion
G
'-+
G =
II
G
h
l:::;h:::;k
is,
in
fact,
the
canonical
metric
representation
of
G (which
explains
why
we
de-
noted
the
number
of
connected
components
of
the
atom
graph
by
k,
the
letter
used
in
Chapter
20
for
denoting
the
isometric
dimension
of
G).
In
particular,
the
graph
G whose
construction
depends,
a priori,
on
the
choice
of
the
scale
embedding
of
G
into
a
hypercube
does
not,
in
fact,
depend
on
the
specific em-
bedding.
Hence,
the
graph
G
too
does
not
depend
on
the
specific
embedding.
I
Remark
21.2.12.
One
can
also verify
directly
that
the
graph
G
does
not
depend
on
the
specific scale
embedding
of
G.
Indeed,
the
atom
graph
can
be
defined
in
an
abstract
way,
not
using
the
specific
embedding.
Given
two edges
e =
(x,y),
e' = (x',y')
ofG,
set
(21.2.13)
(e,
e')
:=
dc(y', x) - dc(y', y) - dc(x', x) + dc(x', y).
The
quantity
(e,
e')
takes
the
values
0,
±1, ±2,
depending
to
which
sets
of
the
partition
V =
G(x,y)
U
G(y,x)
U G=(x,y) (defined
in
(18.0.1))
the
nodes
x',y'
belong. Observe
that
(e,
e')
i=
°
if
and
only if e, e' are
in
relation
by
(J
(defined
in
(18.0.2)).
In
the
case when
both
e, e'
belong
to
the
set
Eo (recall (21.2.1))
with,
say,
Xo
E
G(x,y)
n G(x',y'),
then
1
(e,
e') =
:\I(Y
\
X)
n
(Y'
\
X')I
E
{O,
1,
2},
if
x
f->
X is a A-embedding
of
G into a
hypercube.
In
particular,
(e,
e') = 2
if
and
only
if
the
edges e, e'
correspond
to
the
same
proper
atom
Y \ X =
Y'
\
X'.
For e, e' E Eo,
set
e
""'
e'
if
(e,
e') =
2.
The
relation,,", is
an
equivalence
relation
on
Eo.
Clearly,
the
set
of
equivalence
classes
of
Eo
under""'
is
in
bijection
with
the
set
of
proper
atoms.
One
can
define
a
graph
[
on
the
set
of
equivalence classes by
letting
two classes
e,
e'
be
adjacent
if
(e,
e') = 1
(the
value
of
(e,
e') does
not
depend
on
the
choice
of
e
in
the
class
e
and
of
e'
in
the
class e').
The
graph
[ clearly coincides
with
the
atom
graph
A(G).
Let
[1,
...
,
[k
denote
the
connected
components
of
[.
Hence, each edge
e
E Eo is assigned
to
a
node
in
one
of
the
[h'S.
We now see how
to
assign
the
other
edges
of
G
to
some
component
[h.
Let e = (x,
y)
be
an
edge
that
does
not
belong
to
Eo, i.e.,
such
that
dc(xo,x)
= dc(xo,y)
=:
B.
Let
(XO,Xl,
...
,Xs = x)
and
(YO
=
Xo,
Yl,
...
,Ys =
y)
be
shortest
paths
joining
Xo
to
x
and
y
in
G
and
setei:=
(Xi-l,Xi),!;
:=
(Yi-l,Yi) for i = 1,
...
,B.
Consider
the
subgraph
of
[
322
Chapter
2l.
£1-Graphs
induced
by
the
set
{ei,7i
: i = 1,
...
, s}.
An
analogue
of
Claim
2l.2.6
shows
that
this
graph
consists
of
isolated nodes, cycles,
and
exactly
one
path.
Moreover,
the
component
[h
containing
this
path
depends
only
on
the
edge (x,
y)
(not
on
the
choice
of
the
shortest
paths
from
Xo
to
x
and
y).
This
permits
us
to
partition
the
edge
set
E
of
G
into
E1
U
...
U
Ek,
where
Eh
consists
of
the
edges
that
are
assigned
to
[h
by
the
above procedure.
Then,
let
Yh
denote
the
graph
obtained
by
contracting
the
edges from E \
Eh.
The
graph
Yh coincides
with
the
graph
Gh
(up
to
renumbering
of
the
factors).
So we have
shown
how
to
construct
the
graph
G
in
an
abstract
way,
not
depend-
ing
on
the
specific scale
embedding
of
G. I
21.3
Proofs
Proof
of
Theorem
21.1.3.
The
existence
of
a
graph
G satisfying
Theorem
2l.l.3
(i)
follows from
Claim
2l.2.1O. We prove
the
second
part
of
Theorem
2l.l.3.
Let
'lj;
: x
1-+
X
be
a A-embedding
of
G into a
hypercube
H(0,).
Suppose
first
that
'lj;
assigns
the
given
node
Xo
to
0.
Using
'lj;,
by
the
construction
of
Section
2l.2,
we
obtain
a
graph
G.p
which is A-embedded into
H(n)
and
is
isomorphic
to
G
(by
Remark
2l.2.11).
This
gives
the
A-embedding
{$
such
that
'lj;
=
{$(f.
Sup-
pose
now
that
'lj;
assigns
the
set
Xo
to
the
node
Xo.
Consider
the
A-embedding
x
1-+
X
6Xo,
denoted
by
'lj;6X
o
,
of
G
into
H(n).
As 'lj;6Xo
maps
Xo
to
0,
we
obtain
('lj;6xo)6Xo
for
the
embedding
{$.
I
Proof
of
Corollaries 21.1.4
and
21.1.5.
IfG
is
an
£1-graph,
then
the
graph
G is
an
£1-graph (by
Claim
2l.2.7)
and
G coincides
with
the
canonical
metric
represen-
tation
of
G (by
Remark
21.2.11).
This
shows Corollary
2l.l.4.
Corollary
2l.l.5
is
an
immediate
consequence
of
Corollary 21.1.4. I
Proof
of
Corollaries
21.1.6
and
21.1.7.
The
implication:
Gis
£1-rigid
===}
G is
£1-rigid follows from
Theorem
21.1.3 (ii). Conversely,
suppose
that
G is £1-rigid.
We show
that
G is £1-rigid.
Consider
a scale
embedding
{$i
of
G
in
the
hypercube
ni,
for i =
1,2.
We
can
suppose
that
0,1
and
0,2
have
the
same
cardinality
(if
not,
add
some
redundant
elements). We
can
also
suppose
that
{$1
and
{$2
have
the
same
scale
A.
(If, for i =
1,2,
{$i
has scale
Ai,
then
replace
{$i
by
{$;,
where
{$~
is
the
A1A2-embedding
constructed
from
{$1
by
replacing
the
elements
of
0,1
by dis.i?int
sets
each
of
cardinality
A2
and
($~
is
the
A1A2-embedding
constructed
from
'lj;2
in
the
same
way.)
Then,
'lj;i
:=
'lj;i(f : x
1-+
Xi
is a A-embedding
of
G
into
the
hypercube
H(n
i
),
for i =
1,2.
As G is £1-rigid,
any
two
isometric
£1-embeddings
of
G
are
equivalent (recall
the
definition from
Chapter
18).
It
is
not
difficult
to
see
that
this
implies
the
existence
of
a bijection
0:
:
0,1
----+
0,2
and
of
a
set
A
~
0,2
such
that
X
2
=
ip(Xd
for each
node
x
of
G where, for a
subset
Z
~
nl,
we
set
ip(Z) =
a(Z)6A.