國立高雄大學圖資館 |

Language: English

Back

Asymptotic properties of random geom...

Rai, Sanatan.

Asymptotic properties of random geometric graphs.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Asymptotic properties of random geometric graphs.
Author:	Rai, Sanatan.
Description:	59 p.
Notes:	Adviser: Ashish Goel.
Notes:	Source: Dissertation Abstracts International, Volume: 66-08, Section: B, page: 4262.
Contained By:	Dissertation Abstracts International66-08B.
Subject:	Mathematics.
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3186379
ISBN:	9780542286551

Asymptotic properties of random geometric graphs.
Rai, Sanatan.

Asymptotic properties of random geometric graphs. - 59 p.

Adviser: Ashish Goel.

Thesis (Ph.D.)--Stanford University, 2005.

Our second result is that the spectral measure of the transition matrix of the simple random walk (SRW) on G( Xn ; r(n)) is concentrated, and in fact converges to that of the graph on the deterministic grid. This permits the approximation of various random walk based functionals on the random graph by their values on the graph on the grid. Conventional approaches from random matrix theory are inapplicable in this case because the entries are not independent. We have a novel approach to derive spectral concentration via proving concentration of the matrices in the Hilbert-Schmidt norm.

ISBN: 9780542286551Subjects--Topical Terms:

184409
Mathematics.

Asymptotic properties of random geometric graphs.
LDR:02319nmm _2200277 _450 001 170776
005 20061228142242.5
008 090528s2005 eng d
020 $a 9780542286551
035 $a 00242806
040 $a UnM $c UnM
100 0 $a Rai, Sanatan. $3 244806
245 1 0 $a Asymptotic properties of random geometric graphs.
300 $a 59 p.
500 $a Adviser: Ashish Goel.
500 $a Source: Dissertation Abstracts International, Volume: 66-08, Section: B, page: 4262.
502 $a Thesis (Ph.D.)--Stanford University, 2005.
520 # $a Our second result is that the spectral measure of the transition matrix of the simple random walk (SRW) on G( Xn ; r(n)) is concentrated, and in fact converges to that of the graph on the deterministic grid. This permits the approximation of various random walk based functionals on the random graph by their values on the graph on the grid. Conventional approaches from random matrix theory are inapplicable in this case because the entries are not independent. We have a novel approach to derive spectral concentration via proving concentration of the matrices in the Hilbert-Schmidt norm.
520 # $a Random geometric graphs result from taking n uniformly distributed points in the unit cube, [0, 1]d, and connecting two points if their Euclidean distance is at most r, for some prescribed r. We show that monotone properties for this class of graphs have sharp thresholds and also present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. In fact, we prove that a random geometric graph is shown is a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs.
590 $a School code: 0212.
650 # 0 $a Mathematics. $3 184409
650 # 0 $a Operations Research. $3 227148
690 $a 0405
690 $a 0796
710 0 # $a Stanford University. $3 212607
773 0 # $g 66-08B. $t Dissertation Abstracts International
790 $a 0212
790 1 0 $a Goel, Ashish, $e advisor
791 $a Ph.D.
792 $a 2005
856 4 0 $u http://libsw.nuk.edu.tw:81/login?url=http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3186379 $z http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3186379