Final ACO Doctoral Examination and Defense of Dissertation
On Extremal, Algorithmic, and Inferential Problems in Graph Theory
Abhishek Dhawan
ACO PhD student, School of Mathematics
Date: 5/30/2024
Time: 1-3pm
Location: Skiles 005
Zoom: https://gatech.zoom.us/j/6125656239
Advisors:
Dr. Anton Bernshteyn, School of Mathematics, Georgia Institute of Technology
Dr. Cheng Mao, School of Mathematics, Georgia Institute of Technology
Committee:
Dr. Anton Bernshteyn, School of Mathematics, Georgia Institute of Technology
Dr. Tom Kelly, School of Mathematics, Georgia Institute of Technology
Dr. Cheng Mao, School of Mathematics, Georgia Institute of Technology
Dr. Will Perkins, School of Computer Science, Georgia Institute of Technology
Dr. Alexander Wein, Department of Mathematics, University of California, Davis
Reader: Dr. Will Perkins, School of Computer Science, Georgia Institute of Technology
Thesis draft: pdf icon Dissertation.pdf
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, all of which use probabilistic techniques.
In Part 1, we consider structurally constrained graphs and hypergraphs. 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. 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. We show how certain probabilistic techniques for problems on bipartite graphs can be adapted to multipartite hypergraphs, and are therefore able to extend and generalize a number of results.
In Part 2, 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 3, we explore a number of statistical inference problems in random hypergraph models. Specifically, we consider the statistical-computational gap for 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 explore the power and limitations of low-degree polynomial algorithms, a powerful class of algorithms which includes the class of local algorithms as well as approximate message passing and power iteration.
