Back to search

Georgia Institute of Technology

On Extremal, Algorithmic, and Inferential Problems in Graph Theory

Abstract

dc:description.abstract

In this dissertation we study a variety of graph-theoretic problems lying at the intersection of mathematics, computer science, and statistics. This work consists of three parts, each of which is in turn split into a number of chapters. While each part and the chapters therein are largely independent from each other, certain common themes feature throughout (most notably, the use of probabilistic techniques). In Part I, we consider graphs and hypergraphs satisfying certain structural constraints. We examine a celebrated conjecture of Alon, Krivelevich, and Sudakov regarding vertex coloring. Our results provide improved bounds in all known cases for which the conjecture holds. Additionally, we introduce a generalized notion of local sparsity and study the independence and chromatic numbers of graphs satisfying this property. We also consider multipartite hypergraphs, a natural extension of bipartite graphs to this more general setting. We show how certain probabilistic techniques applied to problems on bipartite graphs can be adapted to multipartite hypergraphs and are therefore able to extend and generalize a number of results. In Part II, we investigate edge-coloring from an algorithmic standpoint. We focus on multigraphs of bounded maximum degree, i.e., $\Delta(G) = O(1)$. Following the so-called augmenting subgraph approach, we design deterministic and randomized algorithms using a near optimal number of colors in the sequential setting as well as in the LOCAL model of distributed computing. Additionally, we study list-edge-coloring for list assignments satisfying certain local constraints, and describe a polynomial-time algorithm to compute such a coloring. Finally, in Part III, we explore a number of statistical inference problems in random hypergraph models. Specifically, we consider the statistical--computational gap of finding large independent sets in sparse random hypergraphs, and the computational threshold for the detection of planted dense subhypergraphs (a generalization of the classical planted clique problem). We are interested in the power and limitations of low-degree polynomial algorithms, a powerful class of algorithms which includes the class of local algorithms as well as the algorithmic paradigms of approximate message passing and power iteration.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dhawan, Abhishek
Advisors dc:contributor.advisor
  • Bernshteyn, Anton
  • Mao, Cheng
Committee members dc:contributor.committeemember
  • Perkins, Will
  • Kelly, Tom
  • Wein, Alexander

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/75670

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dhawan, Abhishek. On Extremal, Algorithmic, and Inferential Problems in Graph Theory. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75670