With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
COMING SOON! PQDT Open is getting a new home!
ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at www.proquest.com.
Questions? Please refer to this FAQ.
Let G^{D} be the set of graphs G(V, E) with n vertices, and the degree sequence equal to D = (d_{1}, d_{2},..., d_{n}). In addition, for ½ < a < 1, we define the set of graphs with an almost given degree sequence D as follows:
G_{a}(D): = ∪ G(D'),
where the union is over all degree sequences D¯ such that, for 1 ≤ i ≤ n, we have |d_{ i}-d'_{i}|< (d_{i})^{a}.
Now, we choose random graphs G_{g}(D) and G_{a}(D) uniformly out of the sets G(D) and G_{a}(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 G_{g}(D) is a dense graph, i.e. |E|=Θ(n^{2}), in the sense of graphons, or when G_{g}(D) is very sparse, i.e. (d_{n})^{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 G_{a}(D) under some mild conditions. For the random graph G_{g}(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 (D_{1}, D_{ 2}) ∈ Z^{(n1)} × Z^{ (n2)}, we let G_{b}(D_{1}, D_{2}) be the random bipartite graph that is chosen uniformly out of the set G(D_{1}, D_{2}), where G(D_{1}, D_{2}) is the set of all bipartite graphs with the degree sequence (D_{1}, D_{2}). We are able to show the result for G_{b}(D_{1}, 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 |