With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
Let GD be the set of graphs G(V, E) with n vertices, and the degree sequence equal to D = (d1, d2,..., dn). In addition, for ½ < a < 1, we define the set of graphs with an almost given degree sequence D as follows:
Ga(D): = ∪ G(D'),
where the union is over all degree sequences D¯ such that, for 1 ≤ i ≤ n, we have |d i-d'i|< (di)a.
Now, we choose random graphs Gg(D) and Ga(D) uniformly out of the sets G(D) and Ga(D) , respectively, which we call random graphs with given and almost given degree sequence D. We first survey the known results about graphs and random graphs with a given degree sequence. This has been studied when Gg(D) is a dense graph, i.e. |E|=Θ(n2), in the sense of graphons, or when Gg(D) is very sparse, i.e. (dn)2=o(|E|).
Second and in the case of sparse graphs with an almost given degree sequence, we investigate this question, and give the finite tree subgraph structure of Ga(D) under some mild conditions. For the random graph Gg(D) with a given degree sequence, we re-derive the finite tree structure in dense and very sparse cases to give a continuous picture.
Finally, for a pair of integer vectors (D1, D 2) ∈ Z(n1) × Z (n2), we let Gb(D1, D2) be the random bipartite graph that is chosen uniformly out of the set G(D1, D2), where G(D1, D2) is the set of all bipartite graphs with the degree sequence (D1, D2). We are able to show the result for Gb(D1, D 2) without any further conditions.
Advisor: | Chatterjee, Sourav, Varadhan, Srinivasa R. S. |
Commitee: | |
School: | New York University |
Department: | Mathematics |
School Location: | United States -- New York |
Source: | DAI-B 76/01(E), Dissertation Abstracts International |
Source Type: | DISSERTATION |
Subjects: | Mathematics |
Keywords: | Degree sequences, Random graphs, Sparse graphs |
Publication Number: | 3635276 |
ISBN: | 978-1-321-16258-5 |