Georgia Institute of Technology College of Sciences

This thesis explores Turán-type extremal problems in graphs that exclude certain minors, focusing on the maximum number of $k$-cliques such graphs can contain. The first part of the thesis studies planar graphs, which forbid $K_5$ and $K_{3,3}$ as minors. We determine the maximum number of edges is in a planar graph that contains no cycle of length k, and establish a general upper bound for the number of edges in a planar graph avoiding $C_k$ for any $k\ge 11$.

The second part addresses the maximum number of $k$-cliques in $K_t$-minor-free graphs. We show essentially sharp bounds on the maximum possible number of cliques of order $k$ in a $K_t$-minor-free graph on $n$ vertices. More precisely, we determine a function $C(k, t)$ such that for each $k < t$ with $t - k \gg \log_2 t$, every $K_t$-minor-free graph on $n$ vertices has at most $n \cdot C(k, t)^{1 + o_t(1)}$ cliques of order $k$. We also show that this bound is sharp by constructing a $K_t$-minor-free graph on $n$ vertices with $C(k, t) n$ cliques of order $k$. This result answers a question of Wood and Fox–Wei asymptotically up to an $o_t(1)$ factor in the exponent, except in the extreme case where $k$ is very close to $t$.

This thesis presents several contributions to the fields of image and geometry processing. In 2D image processing, we propose a method that not only computes the relative depth of objects in bitmap format but also inpaints occluded regions using a PDE-based model and vector representation. Our approach demonstrates both qualitative and quantitative advantages over the state-of-the-art depth-aware bitmap-to-vector conversion models.

In the area of 3D point cloud processing, we introduce a method for generating a robust normal vector field that preserves first order discontinuity while being resistant to noise, supported by a degree of theoretical guarantee. This technique has potential applications in solving PDEs on point clouds, detecting sharp features, and reconstructing surfaces from incomplete and noisy data.

Additionally, we present a dedicated work on surface reconstruction from point cloud data. While many existing models can reconstruct implicit surfaces and some include denoising capabilities, a common drawback is the loss of sharp features: edges and corners are often smoothed out in the process. To address this limitation, we propose a method that not only denoises but also preserves sharp edges and corners during surface reconstruction from noisy data.

Graph coloring is a fundamental problem in graph theory in which the goal is to properly color a graph with the minimum number of colors in terms of some parameters (such as maximum degree). We explore this problem from the perspective of three different types of graphs: graphs with forbidden bipartite subgraphs; planar graphs; and Borel graphs that are line graphs. Each can be seen as graphs with a forbidden list of subgraphs; despite this similarity, the techniques used to study each are as varied as the results themselves.

We start with studying $F$-free graphs. We say a graph is $F$-free if it contains no subgraph isomorphic to $F$ (not necessarily induced). A conjecture of Alon, Krivelevich, and Sudakov states that, for any graph $F$, there is a constant $c_F > 0$ such that if $G$ is an $F$-free graph of maximum degree $\Delta$, then $\chi(G) \leq c_F \Delta / \log\Delta$. Alon, Krivelevich, and Sudakov verified this conjecture for a class of graphs $F$ that includes all bipartite graphs. Moreover, it follows from recent work by Davies, Kang, Pirot, and Sereni that %this conjecture holds for $F$ bipartite; moreover, if $G$ is $K_{t,t}$-free, then $\chi(G) \leq (t + o(1)) \Delta / \log\Delta$ as $\Delta \to \infty$. We improve this bound to $(1+o(1)) \Delta/\log \Delta$, making the constant factor independent of $t$. This matches the best known bound for several other class of graphs $F$, such as triangles, fans, and cycles, and lowering this bound further for nontrivial graphs is considered extremely challenging. We further extend our result to the correspondence coloring setting (also known as DP-coloring), introduced by Dvo\v{r}\'ak and Postle.

Next we study defective coloring of planar graphs. Defective coloring (also  known as relaxed or improper coloring) is a generalization of proper coloring defined as follows: for $d \in \mathbb{N}$, a coloring of a graph is $d$-defective if every vertex is colored the same as at most $d$ of its neighbors. We investigate defective coloring of planar graphs in the context of correspondence coloring. First we show there exist planar graphs that are not $3$-defective $3$-correspondable, strengthening a recent result of Cho, Choi, Kim, Park, Shan, and Zhu. Then we construct a planar graph that is $1$-defective $3$-correspondable but not $4$-correspondable, thereby extending a recent result of Ma, Xu, and Zhu from list coloring to correspondence coloring. Finally we show all outerplanar graphs are $3$-defective 2-correspondence colorable, with $3$ defects being best possible.

Finally, we study Borel graphs. We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the 9 finite graphs from the classical result of Beineke together with a 10th infinite graph associated to the equivalence relation $\mathbb{E}_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman--Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.

This includes work coauthored with Anton Bernshteyn and Abhishek Dhawan.

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.