Quelle aboutRandomComplexes.html Sprache: HTML

products/sources/formale Sprachen/GAP/pkg/hap/www/SideLinks/About/aboutRandomComplexes.html

<!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">
 
<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="aboutCubical.html">Previous</a> 
 </td>
 <td
style="text-align: center; vertical-align: top; color: rgb(0, 0, 102);"><big>About HAP: Random Simplicial Complexes 
 </big></td>
 <td style="text-align: right; vertical-align: top;"><a
href="aboutLinks.html">next</a> 
 </td>
 </tr>
 </tbody>
 </table>
 <big></big> 
 </th>
 </tr>
 <tr align="center">
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big
style="font-weight: bold;">Homology of random graphs and their nerves</big> 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255); text-align: left;">For
a
positive
integer
n
and
probability
p
we
denote
by G(n,p) the
Erdos–Renyi random graph. This has n vertices with each potential edge
included independently with probability p. 
 
The following commands construct low dimensions of the simlicial nerve NG(n,p) of the
random graph on n=100 vertices for probability values in the range
0<p<0.5. By definition this nerve has n vertices and one
k-simplex for each collection of k+1 vertices spanning a complete
subgraph of G(n,p). 
 
Finally, for k=0,1,2,3,4 , the integral homology Hk(NG(n,p),Z)
is
computed
and
stored
in
a
list
H.

 
 </td>
 </tr>
 <tr>
 <td
style="background-color: rgb(255, 255, 204); vertical-align: top;">H:=[];; 
n:=100;; 
 
for p in [1..50]*(1/100) do 
K:=RandomSimplicialGraph(n,p);; 
G:=GraphOfSimplicialComplex(K);; 
N:=SimplicialNerveOfGraph(G,5);; 
Y:=SimplicialComplexToRegularCWComplex(N);; 
CriticalCellsOfRegularCWComplex(Y);; 
Add(H, List([0..4],i->Homology(Y,i)) ); 
od; 
 </td>
 </tr>
 <tr>
 <td
style="background-color: rgb(255, 255, 255); vertical-align: top;">The
following command shows that no torsion occurs in any of the computed
homology groups Hk(NG(n,p),Z) . </td>
 </tr>
 <tr>
 <td
style="background-color: rgb(255, 255, 204); vertical-align: top;">gap>
SSortedList(Flat(H)); 
[ 0 ] 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">It
is shown in [ M. Kahle and E. Meckes, "Limit theorems for Betti numbers
of random simplicial complexes", HHA, 15(1), 2013, 343-374] that the
Betti numbers 
 
 <div style="text-align: center;">bk(n,p)= rank( Hk(NG(n,p),Z)
)

 
 </div>
 
are normally distributed for large n. The distribution is illustrated
by the following commands which plot bk(n,p)
against p for fixed n=100 and k=0,1,2,3,4. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
B:=List([1..5],k->List(List(H,h->h[k]),x->Length(x)));; 
 
gap> for k in [0,1,2,3] do 
> A:=NullMat(Maximum(B[k+1])+5,100);; 
> for P in [1..50] do 
> A[B[k+1][P]+1][2*P]:=1; 
> od; 
>
M:=ThickenedPureCubicalComplex(PureCubicalComplex(TransposedMat(Reversed(A))));; 
> ViewPureCubicalComplex(M); 
> od; 
 
 <div style="text-align: center;"><img
style="width: 104px; height: 25px;" alt="" src="randomgraph1.png">




 <img style="width: 104px; height: 263px;" alt=""
src="randomgraph2.png"> <img
style="width: 104px; height: 620px;" alt="" src="randomgraph3.png">
 <img
style="width: 104px; height: 1310px;" alt="" src="randomgraph4.png">
 <img style="width: 104px; height: 1072px;" alt=""
src="randomgraph5.png"> 
 </div>
 </td>
 </tr>
 <tr align="center">
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big
style="font-weight: bold;">Homology of random simplicial 2-complexes</big> 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">For
a positive integer n and probability p we denote by Y(n,p) the
Linial-Meshulam random simplicial 2-complex. Its 1-skeleton is the
complete graph on n vertices; each possible 2-simplex is included
independently with probability p. 
 
The following commands compute the Betti numbers 
 
 <div style="text-align: center;">rank( H1(Y(n,p),Z)
) 
 </div>
 
for n=200 vertices and for p= 1/200, 2/200, 3/200, ... , 50/200. 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">L:=[]; 
n:=200;; 
 
for p in [1..50]*(1/200) do 
K:=RandomSimplicialTwoComplex(n,p); 
H:=Homology(K,1); 
Add(L,H); 
od; 
 
List(L,x->Length(x)); 
[ 13065, 6597, 1299, 393, 138, 48, 16, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0 ] 
 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following additional command shows that there is no torsion in any
of
the computed
homology groups H1(Y(n,p),Z) . 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
SSortedList(Flat(L)); 
[ 0 ] 
 </td>
 </tr>
 <tr align="center">
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);"><big
style="font-weight: bold;">Fundamental groups of random simplicial
2-complexes</big> 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 255);">The
following commands compute presentations for the fundamental groups of
Y(n,p) for n=60 vertices and probabilities in the range 0<p<0.25.
 
 
The commands also list the number of generators for each fundamental
group, and show that in most cases there are no relators between
generators. Thus, in most (and possibly all) cases, the fundamental
group is free; for large p the fundamental group is trivial 
 </td>
 </tr>
 <tr>
 <td
style="vertical-align: top; background-color: rgb(255, 255, 204);">gap>
L:=[];; 
gap> n:=60;; 
gap> for p in [1..50]*(1/200) do 
> K:=RandomSimplicialTwoComplex(n,p);; 
> Add(L,FundamentalGroup(K)); 
> od; 
 
gap> NumbersOfGenerators:=List(L,g->Length(GeneratorsOfGroup(g))); 
[ 1542, 1357, 1206, 1024, 822, 647, 502, 344, 195, 110, 82, 57, 39, 18,
9, 14, 16, 15, 2, 4, 3, 2, 2, 2, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] 
 
gap> NumbersOfRelations:=List(L,g->Length(RelatorsOfFpGroup(g))); 
[ 0, 0, 0, 0, 0, 0, 0, 0, 37, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0 ] 
 </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="aboutCubical.html">Previous
Page</a> 
 </td>
 <td style="text-align: center; vertical-align: top;"><a
href="aboutContents.html">Contents</a> 
 </td>
 <td style="text-align: right; vertical-align: top;"><a
href="aboutLinks.html">Next
page 
 </a> </td>
 </tr>
 </tbody>
 </table>
 <a href="aboutTopology.html"> 
 </a> </td>
 </tr>
 </tbody>
</table>
 
 
</body>
</html>

Messung V0.5

¤ Dauer der Verarbeitung: 0.15 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.