# Graph colorings and graph limits [electronic resource]

- Responsibility
- Sukhada Fadnavis.
- Imprint
- 2012.
- Physical description
- 1 online resource.

## Digital content

## Online

### Also available at

## At the library

### Special Collections

#### On-site access

Collections are moving, which may affect access. Request materials as early as possible. Maximum 5 items per day. Contact specialcollections@stanford.edu for information about access.

**University Archives**Request via Aeon (opens in new tab)

Call number | Note | Status |
---|---|---|

3781 2012 F | In-library use |

### More options

## Description

### Creators/Contributors

- Author/Creator
- Fadnavis, Sukhada Sharad.
- Contributor
- Diaconis, Persi primary advisor. Thesis advisor
- Bump, Daniel, 1952- advisor. Thesis advisor
- Church, Thomas (Thomas Franklin) advisor. Thesis advisor
- Stanford University. Department of Mathematics

### Contents/Summary

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

### Bibliographic information

- Publication date
- 2012
- Note
- Submitted to the Department of Mathematics.
- Note
- Thesis (Ph.D.)--Stanford University, 2012.