Back to search

University of Denver

Local-Global Results on Discrete Structures

Abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph.D.
Level thesis:degree_level
Dissertation

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Stevens, Alexander Lewis
Contributors dc:contributor
  • Paul K. Horn
  • Jing Li
  • Mei Yin
  • Mario Lopez

Subjects

dc:subject × 9

Rights

dc:rights
Statement dc:rights
  • <p>Copyright is held by the author. User is responsible for all copyright compliance.</p>
  • Alexander Lewis Stevens
Language dc:language
en

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.du.edu/etd/2082

Chain of custody

source
Harvested from
University of Denver
Base URL
digitalcommons.du.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Stevens, Alexander Lewis. Local-Global Results on Discrete Structures. Dissertation thesis, https://digitalcommons.du.edu/etd/2082