Dissertation/Thesis Abstract

Random Sparse Graphs with a Given Degree Sequence
by Mehrdad, Behzad, Ph.D., New York University, 2014, 100; 3635276
Abstract (Summary)

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 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.

Indexing (document details)
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
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest