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.|
|School:||New York University|
|School Location:||United States -- New York|
|Source:||DAI-B 76/01(E), Dissertation Abstracts International|
|Keywords:||Degree sequences, Random graphs, Sparse graphs|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be