Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
Local-Global Results On Discrete Structures, Alexander Lewis Stevens
Local-Global Results On Discrete Structures, Alexander Lewis Stevens
Electronic Theses and Dissertations
Local-global arguments, or those which glean global insights from local information, are central ideas in many areas of mathematics and computer science. For instance, in computer science a greedy algorithm makes locally optimal choices that are guaranteed to be consistent with a globally optimal solution. On the mathematical end, global information on Riemannian manifolds is often implied by (local) curvature lower bounds. Discrete notions of graph curvature have recently emerged, allowing ideas pioneered in Riemannian geometry to be extended to the discrete setting. Bakry- Émery curvature has been one such successful notion of curvature. In this thesis we use combinatorial …
Exponential Random Graphs And A Generalization Of Parking Functions, Ryan Demuse
Exponential Random Graphs And A Generalization Of Parking Functions, Ryan Demuse
Electronic Theses and Dissertations
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 …
Discrepancy Inequalities In Graphs And Their Applications, Adam Purcilly
Discrepancy Inequalities In Graphs And Their Applications, Adam Purcilly
Electronic Theses and Dissertations
Spectral graph theory, which is the use of eigenvalues of matrices associated with graphs, is a modern technique that has expanded our understanding of graphs and their structure. A particularly useful tool in spectral graph theory is the Expander Mixing Lemma, also known as the discrepancy inequality, which bounds the edge distribution between two sets based on the spectral gap. More specifically, it states that a small spectral gap of a graph implies that the edge distribution is close to random. This dissertation uses this tool to study two problems in extremal graph theory, then produces similar discrepancy inequalities based …