# Dissertation/Thesis Abstract

Random Sparse Graphs with a Given Degree Sequence
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