Biology Reference
In-Depth Information
6.3. Graphs That Support Diversity
A natural goal is to characterize the bipartite graphs that support diversity, and the
first result of this section does this for complete bipartite graphs.
Theorem 6.3.
The complete graph
K
p,q
supports diversity if and only if
p
is even
and
q
=1
.
Proof.
Assume that (
V
,
W
,
E
,η,γ
) is a complete diversity graph. Suppose that
>
1. Then, from Theorem 6.1 we have for any
w
1
and
w
2
in
|W|
W
that
max
{
deg(
w
1
)
,
deg(
w
2
)
}≥
2
|N
(
w
1
)
∩N
(
w
2
)
|
=2
|V|,
which is a contradiction. So,
|W|
=1.
The fact that genotypes need pairs of
haplotypes guarantees that
is even.
Now assume that
p
is even and
q
=1. Select
n
so that
|V|
<
2
n
and let
γ
be such that
γ
(
w
)=(0
,
0
,...,
0).Thereare2
n−
1
disjoint pairs of haplotypes
that can mate to form
γ
(
w
).Pick
|V|
H
be the set of
|V|
/
2 of these pairs and let
V→H
haplotypes in these pairs. Allowing
η
:
to be a bijection, we see that
(
V
,
W
,
E
,η,γ
) is a diversity graph.
From Theorem 6.3 we see that the probability of generating a complete bi-
partite graph of the form
K
p,
1
that supports diversity is one half (assuming that
even and odd values of
p
are equally likely). In some ways, the next result extends
this idea by showing that the probability of generating a random bipartite graph
that supports diversity is low. The result decomposes the biadjacency matrix into
matrices whose rows sums are all 2, which guarantees a mating structure.
Theorem 6.4.
The bipartite graph
(
)
supports diversity if and only if the
biadjacency matrix
E
has a logical decomposition
E
1
,E
2
,...,E
s
so that
V
,
W
,
E
e
T
E
k
=2
e
T
for all
1
•
≤
k
≤
s
,
}
|V|×n
with distinct rows and the property
that
(
E
1
)
T
H
=(
E
2
)
T
H
=
...
=(
E
s
)
T
H
, and
•
there exists an
H
∈{−
1
,
1
the rows of
(
E
k
)
T
H
are distinct.
•
Proof.
Assume
that (
V
,
W
,
E
,η,γ
) is
a
diversity
graph,
and
let
s
=
so that deg(
w
1
)
(1
/
2)max
{
deg(
w
):
w
∈W}
.
Order the elements of
W
≥
deg(
w
2
)
deg(
w
|W|
). We construct the matrices
E
1
,E
2
,...,E
s
that
form a desired logical decomposition. The neighborhood of each
w
j
can be writ-
ten as the disjoint union of (1
/
2)deg(
w
j
) pairs,
N
(
w
j
)=
≥
...
≥
v
k
j
,v
k
j
}
k
{
,
(6.2)
Search WWH ::
Custom Search