Graph colorings and graph limits
Abstract/Contents
- Abstract
- This thesis in two parts. The first part studies the monotonicity properties of chromatic polynomials. The second part studies the limiting behavior of certain exponential random graph models. \\ In the first part (chapter 2 and 3), a generalization of the birthday problem is studied and connections are shown to two conjectures about chromatic polynomials: the shameful conjecture due to D. Welsh and Brenti's conjecture about the log-concavity of chromatic polynomials. The probability of getting a proper coloring of a graph under a random coloring scheme is studied. The goal is to understand conditions under which a random coloring with q+1 colors has a higher probability of resulting into a proper coloring of the graph than a random coloring with q colors has? It is shown that one criteria guaranteeing that the above property is true is that q should be large enough in terms of the highest degree of the graph. Ideas from the work of A. Sokal and C. Borgs giving bounds on the roots of chromatic polynomials are used to prove this property. In fact, a much stronger property is proved. Further generalizations of this question are also studied and some useful examples and analyses are provided. \\ The second part (chapter 4) studies the limiting behavior of certain exponential random graph models (ERGMs) with some negative coefficients. This study is motivated by recent results of Diaconis and Chatterjee in which they show that ERGMs with positive coefficients have the same limiting behavior as Erdos Renyi random graph models. Using the theory developed in their work the limiting behavior of the Strauss model is studied. Methods from extremal graph theory such as Turan's theorem are used and proofs of their analogous statements in graph limit theory are also proved. Some more complicated models are studied through simulations and these results are also presented here.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2012 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Fadnavis, Sukhada Sharad |
|---|---|
| Associated with | Stanford University, Department of Mathematics |
| Primary advisor | Diaconis, Persi |
| Thesis advisor | Diaconis, Persi |
| Thesis advisor | Bump, Daniel, 1952- |
| Thesis advisor | Church, Thomas (Thomas Franklin) |
| Advisor | Bump, Daniel, 1952- |
| Advisor | Church, Thomas (Thomas Franklin) |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Sukhada Fadnavis. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2012. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2012 by Sukhada Sharad Fadnavis
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...