<!
DOCTYPE HTML PUBLIC
"-//W3C//DTD HTML 4.01 Transitional//EN">
<
html>
<
head>
<
meta http-equiv=
"content-type"
content=
"text/html; charset=ISO-8859-1">
<
title>AboutHap</
title>
</
head>
<
body
style=
"color: rgb(0, 0, 153); background-color: rgb(204, 255, 255);"
link=
"#000066" vlink=
"#000066" alink=
"#000066">
<
br>
<
table
style=
"text-align: left; margin-left: auto; margin-right: auto; color: rgb(0, 0, 102);"
border=
"0" cellpadding=
"20" cellspacing=
"10">
<
tbody>
<
tr align=
"center">
<
th style=
"vertical-align: top;">
<
table style=
"width: 100%; text-align: left;" cellpadding=
"2"
cellspacing=
"2">
<
tbody>
<
tr>
<
td style=
"vertical-align: top;"><a
href=
"aboutPersistent.html"><
small style=
"color: rgb(0, 0, 102);">Previous</
small></a><
br>
</
td>
<
td
style=
"text-align: center; vertical-align: top; color: rgb(0, 0, 102);"><
big><
span
style=
"font-weight: bold;">About HAP: Metric Spaces<
br>
</
span></
big></
td>
<
td style=
"text-align: right; vertical-align: top;"><a
href=
"aboutTDA.html"><
small style=
"color: rgb(0, 0, 102);">next</
small></a><
br>
</
td>
</
tr>
</
tbody>
</
table>
<
big><
span style=
"font-weight: bold;"></
span></
big><
br>
</
th>
</
tr>
<
tr align=
"center">
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 255);"><
big><
span
style=
"font-weight: bold;">1. Metrics on Vectors</
span></
big><
br>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 255); text-align: left;">The
<a href=
"data.txt">data file</a> contains a list L of
400 vectorsi in <
span style=
"font-weight: bold;">R</
span><
sup>3</
sup>.
The following commands produce the 400×400 symmetric matrix whose
(i,j)-entry is the Manhattan distance between L[i] and L[j].
(Alternative choices of metric include the Euclidean squared metric and
Hamming metric.)<
br>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 204);">gap>
ReadPackage(
"hap",
"www/SideLinks/About/data.txt");
#This
reads
in
the
list
L<
br>
gap> S:=VectorsToSymmetricMatrix(L,ManhattanMetric);;<
br>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 255);">The
following
command uses GraphViz software to display the graph G(S,t) on
400
vertices with edge between i and j precisely when <
br>
<
br>
<
div style=
"text-align: center;">S[i][j] <= tM / 100 <
br>
</
div>
<
br>
where M is the maximum value of the entries in S. Thus the threshold t
should be chosen in the range from 0 to 100. We choose t=8. We also
choose to give the first 200 vertices a common colour distinct from the
remaining vertices. The display shows that the first 200 vertices lie
in one path-component of G(S,8), and the remaining 200 vertices lie in
a second path-component. Each path-component
"has the shape" of a
cylinder
or annulus. <
br>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 204);">gap>
SymmetricMatDisplay(S,8,
[
[1..200],
[201..400]
]
);<
br>
<
br>
<
div style=
"text-align: center;"><
img
style=
"width: 600px; height: 284px;" alt=
"" src=
"colourgraph.gif"><
br>
</
div>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 255);">The
following commands construct the graph G=G(S,10) and then display it. <
br>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 204);">gap>
M:=Maximum(Maximum(S));;
<
br>
gap> G:=SymmetricMatrixToGraph(S,10*M/100); <
br>
Graph on 400 vertices.<
br>
<
br>
gap>
GraphDisplay(G);<
br>
<
div style=
"text-align: center;"><
img
style=
"width: 384px; height: 347px;" alt=
"" src=
"400graph.gif"><
br>
</
div>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 255);">We
use the term <
span style=
"font-style: italic;">simplicial nerve</
span>
of G to mean the simplicial complex
NG which has the same vertices and edges as G; a collection of vertices
is a simplex in NG if and only if each pair of edges in the collection
is connected by an edge in G. The following commands determine a
subgraph H in G such that the simplicial nerves NG and NH are homotopy
equivalent. The commands replace G by H and then display the subgraph. </
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 204);">gap>
ContractGraph(G);;<
br>
gap> G;<
br>
Graph on 248 vertices.<
br>
<
br>
gap> GraphDisplay(G);<
br>
<
div style=
"text-align: center;"><
img
style=
"width: 384px; height: 178px;" alt=
""
src=
"400contractedgraph.gif"><
br>
</
div>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 255);">The
following commands illustrate <
span style=
"font-weight: bold;">two</
span>
methods for calculating the low-dimensional homology of NG. The second
method is more efficient in degrees 0 and 1 but has yet to be properly
implemented in higher degrees.<
br>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 204);">gap>
#Method
One<
br>
gap> NG:=SimplicialNerveOfGraph(G,3);; <
br>
gap> NG:=SimplicialComplexToRegularCWComplex(NG);<
br>
Regular CW-complex of dimension 3<
br>
gap> Homology(NG,0);<
br>
[ 0, 0 ]<
br>
gap> Homology(NG,1);<
br>
[ 0, 0 ]<
br>
<
br>
gap> #Method Two<
br>
gap> C:=RipsChainComplex(G,1);<
br>
Sparse chain complex of length 2 in characteristic 0 . <
br>
<
br>
gap> Bettinumbers(C,0);<
br>
2<
br>
gap> Bettinumbers(C,1);<
br>
2<
br>
</
td>
</
tr>
<
tr align=
"center">
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 255);"><
big><
span
style=
"font-weight: bold;">2. Metrics on Permutations</
span></
big><
br>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 255);">There
are
a
number of standard metrics d(x,y) on permutations x, y <
sub> </
sub>such
as
the Kendall metric (=number of neighbouring
transpositions (i,i+1) needed to express x*y^-1), the Cayley metric (=
number of transpositions (i,j) needed to express x*y^-1) and the
Hamming metric (= #{ i : x*y^-1(i) differs from i } ). The
following commands display the Sylow 2-subgroup of S<
sub>10</
sub> with
respect to the Cayley metric.<
br>
</
td>
</
tr>
<
tr>
<
td
style=
"vertical-align: top; background-color: rgb(255, 255, 204);">gap>
G:=SymmetricGroup(10);;
<
br>
gap> P:=SylowSubgroup(G,2);;<
br>
gap> P:=Elements(P);;<
br>
gap> S:=NullMat(Size(P),Size(P));;<
br>
gap> for i in [1..Size(P)] do<
br>
> for j in [1..Size(P)] do<
br>
> S[i][j]:=CayleyMetric(P[i],P[j],10);<
br>
> od;od;<
br>
gap> SymmetricMatDisplay(S,50);<
br>
<
div style=
"text-align: center;"><
br>
<
img style=
"width: 355px; height: 384px;" alt=
""
src=
"sylowS10.gif"><
br>
<
div style=
"text-align: left;"><
br>
gap> SymmetricMatDisplay(S,15);<
br>
<
br>
<
div style=
"text-align: center;"><
img
style=
"width: 355px; height: 384px;" alt=
"" src=
"sylowS1015.gif"><
br>
</
div>
</
div>
</
div>
</
td>
</
tr>
<
tr>
<
td style=
"vertical-align: top;">
<
table
style=
"margin-left: auto; margin-right: auto; width: 100%; text-align: left;"
border=
"0" cellpadding=
"2" cellspacing=
"2">
<
tbody>
<
tr>
<
td style=
"vertical-align: top;"><a
style=
"color: rgb(0, 0, 102);" href=
"aboutPersistent.html">Previous
Page</a><
br>
</
td>
<
td style=
"text-align: center; vertical-align: top;"><a
href=
"aboutContents.html"><
span style=
"color: rgb(0, 0, 102);">Contents</
span></a><
br>
</
td>
<
td style=
"text-align: right; vertical-align: top;"><a
href=
"aboutTDA.html"><
span style=
"color: rgb(0, 0, 102);">Next
page</
span><
br>
</a> </
td>
</
tr>
</
tbody>
</
table>
<a href=
"aboutTopology.html"><
br>
</a> </
td>
</
tr>
</
tbody>
</
table>
<
br>
<
br>
</
body>
</
html>
