Exponential Random Graphs and a Generalization of Parking Functions

<p>Random graphs are a powerful tool in the analysis of modern networks. Exponential random graph models provide a framework that allows one to encode desirable subgraph features directly into the probability measure. Using the theory of graph limits pioneered by Borgs et. al. as a foundation, we build upon the work of Chatterjee & Diaconis and Radin & Yin. We add complexity to the previously studied models by considering exponential random graph models with edge-weights coming from a generic distribution satisfying mild assumptions. In particular, we show that a large family of two-parameter, edge-weighted exponential random graphs display a phase transtion and identify the limiting behavior of such graphs in the dual space provided by the Legendre-Fenchel transform.</p> <p>For finite systems, we analyze the mixing time of exponential random graph models. The mixing time of unweighted exponential random graphs was studied by Bhamidi, Bresler, and Sly. We extend upon the work of Levin, Luczak, and Peres by studying the Glauber dynamics of a certain vertex-weighted exponential random graph model on the complete graph. Specifically, we identify regions of the parameter space where the mixing time is Θ(<em>n</em> log <em>n</em>) and where it is exponentially slow.</p> <p>Toward the end of this work, we take a drastic turn in a different direction by studying a generalization of parking functions that we call interval parking functions. Parking functions are a classical combinatorial object dating back to the work of Konheim and Weiss in the 1960s. Among other things, we explore the connections that bioutcomes of interval parking functions have to various partial orders on the symmetric group on n letters including the (left) weak order, (strong) Bruhat order, and the bubble-sorting order.</p>

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Year dc:date.available

2021

Author dc:creator

• DeMuse, Ryan

Contributors dc:contributor

• Mei Yin
• Paul Rullkoetter
• Ronnie Pavlov
• Paul Horn
• Alvaro Arias

• Bruhat order
• Exponential random graph model
• Interval parking functions
• Parking functions
• Random graphs
• Sorting order
• Mathematics
• Other Mathematics
• Physics
• Statistical, Nonlinear, and Soft Matter Physics

Statement dc:rights

• <p>Copyright is held by the author. User is responsible for all copyright compliance.</p>

Language dc:language

en

Repository record dc:identifier

https://digitalcommons.du.edu/etd/1910

OAI identifier oai:identifier

oai:digitalcommons.du.edu:etd-2902