Networks, or graphs, are useful for studying many things in today’s world. Graphs can be used to represent connections on social media, transportation networks, or even the internet. Because of this, it’s helpful to study graphs and learn what we can say about the structure of a given graph or what properties it might have. This dissertation focuses on the use of the probabilistic method and spectral graph theory to understand the geometric structure of graphs and find structures in graphs. We will also discuss graph curvature and how curvature lower bounds can be used to give us information about properties of graphs. A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for n and C large enough, if G is an edge-colored copy of Kn in which each color class has size at most n/2, then G has at least [n/(C log n)] edge-disjoint rainbow spanning trees. Here we show that spectral graph theory can be used to prove that if G is any edge-colored graph with n vertices in which each color appears on at most δλ1/2 edges, where δ ≥ C log n for n and C sufficiently large and λ1 is the second-smallest eigenvalue of the normalized Laplacian matrix of G, then G contains at least [δλ1/ C log n] edge-disjoint rainbow spanning trees.
We show how curvature lower bounds can be used in the context of understanding (personalized) PageRank, which was developed by Brin and Page. PageRank ranks the importance of webpages near a seed webpage, and we are interested in how this importance diffuses. We do this by using a notion of graph curvature introduced by Bauer, Horn, Lin, Lippner, Mangoubi, and Yau.
","abstract_html":"<p>Networks, or graphs, are useful for studying many things in today’s world. Graphs can be used to represent connections on social media, transportation networks, or even the internet. Because of this, it’s helpful to study graphs and learn what we can say about the structure of a given graph or what properties it might have. This dissertation focuses on the use of the probabilistic method and spectral graph theory to understand the geometric structure of graphs and find structures in graphs. We will also discuss graph curvature and how curvature lower bounds can be used to give us information about properties of graphs. A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for <em>n</em> and <em>C</em> large enough, if <em>G</em> is an edge-colored copy of <em>K<sub>n</sub></em> in which each color class has size at most <em>n</em>/2, then<em> G</em> has at least [<em>n</em>/(<em>C</em> log <em>n</em>)] edge-disjoint rainbow spanning trees. Here we show that spectral graph theory can be used to prove that if <em>G</em> is any edge-colored graph with <em>n</em> vertices in which each color appears on at most δλ<sub>1</sub>/2 edges, where δ ≥ <em>C</em> log <em>n</em> for <em>n</em> and <em>C</em> sufficiently large and λ1 is the second-smallest eigenvalue of the normalized Laplacian matrix of <em>G</em>, then <em>G</em> contains at least [δλ<sub>1</sub>/ <em>C</em> log <em>n</em>] edge-disjoint rainbow spanning trees.</p> <p>We show how curvature lower bounds can be used in the context of understanding (personalized) PageRank, which was developed by Brin and Page. PageRank ranks the importance of webpages near a seed webpage, and we are interested in how this importance diffuses. We do this by using a notion of graph curvature introduced by Bauer, Horn, Lin, Lippner, Mangoubi, and Yau.</p>","abstract_has_math":false,"creators":["Nelsen, Lauren Morey"],"institution":null,"degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Paul Horn, Ph.D.","Natasha Dobrinen","Mei Yin","Jennifer Hoffman"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-01-01T08:00:00Z","date_published":"2019-01-01T08:00:00Z","updated_at":"2026-07-24T02:03:26Z","subjects":["Probabilistic method","Spectral graph theory","Graphs","Graph curvature","Geometry and Topology","Mathematics","Physical Sciences and Mathematics"],"languages":["en"],"rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/1607","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Paul Horn, Ph.D.","Natasha Dobrinen","Mei Yin","Jennifer Hoffman"]},{"key":"dc:creator","label":"Author","values":["Nelsen, Lauren Morey"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2019-08-02T07:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Probabilistic method","Spectral graph theory","Graphs","Graph curvature","Geometry and Topology","Mathematics","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright is held by the author. User is responsible for all copyright compliance.
"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/1607"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Networks, or graphs, are useful for studying many things in today’s world. Graphs can be used to represent connections on social media, transportation networks, or even the internet. Because of this, it’s helpful to study graphs and learn what we can say about the structure of a given graph or what properties it might have. This dissertation focuses on the use of the probabilistic method and spectral graph theory to understand the geometric structure of graphs and find structures in graphs. We will also discuss graph curvature and how curvature lower bounds can be used to give us information about properties of graphs. A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for n and C large enough, if G is an edge-colored copy of Kn in which each color class has size at most n/2, then G has at least [n/(C log n)] edge-disjoint rainbow spanning trees. Here we show that spectral graph theory can be used to prove that if G is any edge-colored graph with n vertices in which each color appears on at most δλ1/2 edges, where δ ≥ C log n for n and C sufficiently large and λ1 is the second-smallest eigenvalue of the normalized Laplacian matrix of G, then G contains at least [δλ1/ C log n] edge-disjoint rainbow spanning trees.
We show how curvature lower bounds can be used in the context of understanding (personalized) PageRank, which was developed by Brin and Page. PageRank ranks the importance of webpages near a seed webpage, and we are interested in how this importance diffuses. We do this by using a notion of graph curvature introduced by Bauer, Horn, Lin, Lippner, Mangoubi, and Yau.
"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Applications of Geometric and Spectral Methods in Graph Theory"]}]}],"canonical_facts":{"dc:contributor":["Paul Horn, Ph.D.","Natasha Dobrinen","Mei Yin","Jennifer Hoffman"],"dc:creator":["Nelsen, Lauren Morey"],"dc:date.available":["2019-08-02T07:00:00Z"],"dc:description.abstract":["Networks, or graphs, are useful for studying many things in today’s world. Graphs can be used to represent connections on social media, transportation networks, or even the internet. Because of this, it’s helpful to study graphs and learn what we can say about the structure of a given graph or what properties it might have. This dissertation focuses on the use of the probabilistic method and spectral graph theory to understand the geometric structure of graphs and find structures in graphs. We will also discuss graph curvature and how curvature lower bounds can be used to give us information about properties of graphs. A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for n and C large enough, if G is an edge-colored copy of Kn in which each color class has size at most n/2, then G has at least [n/(C log n)] edge-disjoint rainbow spanning trees. Here we show that spectral graph theory can be used to prove that if G is any edge-colored graph with n vertices in which each color appears on at most δλ1/2 edges, where δ ≥ C log n for n and C sufficiently large and λ1 is the second-smallest eigenvalue of the normalized Laplacian matrix of G, then G contains at least [δλ1/ C log n] edge-disjoint rainbow spanning trees.
We show how curvature lower bounds can be used in the context of understanding (personalized) PageRank, which was developed by Brin and Page. PageRank ranks the importance of webpages near a seed webpage, and we are interested in how this importance diffuses. We do this by using a notion of graph curvature introduced by Bauer, Horn, Lin, Lippner, Mangoubi, and Yau.
"],"dc:format":["application/pdf"],"dc:identifier":["https://digitalcommons.du.edu/etd/1607"],"dc:language":["en"],"dc:rights":["Copyright is held by the author. User is responsible for all copyright compliance.
"],"dc:subject":["Probabilistic method","Spectral graph theory","Graphs","Graph curvature","Geometry and Topology","Mathematics","Physical Sciences and Mathematics"],"dc:title":["Applications of Geometric and Spectral Methods in Graph Theory"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."]},"updated_at":"2026-07-24T02:03:26Z"}