{"id":{"repo_id":"denver","oai_identifier":"oai:digitalcommons.du.edu:etd-3074"},"canonical_url":"https://search.ndltd.org/etd/denver/oai:digitalcommons.du.edu:etd-3074","repository":{"repo_id":"denver","name":"University of Denver","base_url":"https://digitalcommons.du.edu/do/oai/"},"display":{"title":"Local-Global Results on Discrete Structures","abstract":"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 implications of Bakry- Émery curvature on graphs to prove a sort of local discrepancy inequality. This then allows us to derive a number of results regarding the local structure of graphs, dependent only on a curvature lower bound. For instance, it turns out that a curvature lower bound implies a nontrivial lower bound on graph connectivity. We also use these results to consider the curvature of strongly regular graphs, a well studied and important class of graphs. In this regard, we give a partial solution to an open conjecture: all SRGs satisfy the curvature condition CD(∞, 2). Finally we transition to consider a facility location problem motivated by using Unmanned Aerial Vehicles (UAVs) to guard a border. Here, we find a greedy algorithm, acting on local geometric information, which finds a near optimal placement of base stations for the guarding of UAVs.","abstract_html":"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 implications of Bakry- Émery curvature on graphs to prove a sort of local discrepancy inequality. This then allows us to derive a number of results regarding the local structure of graphs, dependent only on a curvature lower bound. For instance, it turns out that a curvature lower bound implies a nontrivial lower bound on graph connectivity. We also use these results to consider the curvature of strongly regular graphs, a well studied and important class of graphs. In this regard, we give a partial solution to an open conjecture: all SRGs satisfy the curvature condition CD(∞, 2). Finally we transition to consider a facility location problem motivated by using Unmanned Aerial Vehicles (UAVs) to guard a border. Here, we find a greedy algorithm, acting on local geometric information, which finds a near optimal placement of base stations for the guarding of UAVs.","abstract_has_math":false,"creators":["Stevens, Alexander Lewis"],"institution":null,"degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Paul K. Horn","Jing Li","Mei Yin","Mario Lopez"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:54:32Z","subjects":["Bakry Emery curvature","Graph theory","Local-global results","Spectral graph theory","Computer Sciences","Mathematics","Other Computer Sciences","Other Mathematics","Physical Sciences and Mathematics"],"languages":["en"],"rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>","Alexander Lewis Stevens"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/2082","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.du.edu/etd/2082","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.du.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.du.edu%3Aetd-3074","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Paul K. Horn","Jing Li","Mei Yin","Mario Lopez"]},{"key":"dc:creator","label":"Author","values":["Stevens, Alexander Lewis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2022-08-26T07:00:00Z"]},{"key":"dc:date.copyright","label":"Dc Date Copyright","values":["2022-01-01T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2022-01-01T08: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":["Bakry Emery curvature","Graph theory","Local-global results","Spectral graph theory","Computer Sciences","Mathematics","Other Computer Sciences","Other 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":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"]},{"key":"dc:rights.holder","label":"Dc Rights Holder","values":["Alexander Lewis Stevens"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/2082"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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 implications of Bakry- Émery curvature on graphs to prove a sort of local discrepancy inequality. This then allows us to derive a number of results regarding the local structure of graphs, dependent only on a curvature lower bound. For instance, it turns out that a curvature lower bound implies a nontrivial lower bound on graph connectivity. We also use these results to consider the curvature of strongly regular graphs, a well studied and important class of graphs. In this regard, we give a partial solution to an open conjecture: all SRGs satisfy the curvature condition CD(∞, 2). Finally we transition to consider a facility location problem motivated by using Unmanned Aerial Vehicles (UAVs) to guard a border. Here, we find a greedy algorithm, acting on local geometric information, which finds a near optimal placement of base stations for the guarding of UAVs."]},{"key":"dc:description.provenance","label":"Dc Description Provenance","values":["Received from ProQuest"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["107 pgs"]},{"key":"dc:title","label":"Title","values":["Local-Global Results on Discrete Structures"]}]}],"canonical_facts":{"dc:contributor":["Paul K. Horn","Jing Li","Mei Yin","Mario Lopez"],"dc:creator":["Stevens, Alexander Lewis"],"dc:date.available":["2022-08-26T07:00:00Z"],"dc:date.copyright":["2022-01-01T08:00:00Z"],"dc:date.created":["2022-01-01T08:00:00Z"],"dc:description.abstract":["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 implications of Bakry- Émery curvature on graphs to prove a sort of local discrepancy inequality. This then allows us to derive a number of results regarding the local structure of graphs, dependent only on a curvature lower bound. For instance, it turns out that a curvature lower bound implies a nontrivial lower bound on graph connectivity. We also use these results to consider the curvature of strongly regular graphs, a well studied and important class of graphs. In this regard, we give a partial solution to an open conjecture: all SRGs satisfy the curvature condition CD(∞, 2). Finally we transition to consider a facility location problem motivated by using Unmanned Aerial Vehicles (UAVs) to guard a border. Here, we find a greedy algorithm, acting on local geometric information, which finds a near optimal placement of base stations for the guarding of UAVs."],"dc:description.provenance":["Received from ProQuest"],"dc:format":["application/pdf"],"dc:format.extent":["107 pgs"],"dc:identifier":["https://digitalcommons.du.edu/etd/2082"],"dc:language":["en"],"dc:rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"],"dc:rights.holder":["Alexander Lewis Stevens"],"dc:subject":["Bakry Emery curvature","Graph theory","Local-global results","Spectral graph theory","Computer Sciences","Mathematics","Other Computer Sciences","Other Mathematics","Physical Sciences and Mathematics"],"dc:title":["Local-Global Results on Discrete Structures"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."]},"updated_at":"2026-11-19T07:54:32Z"}