Georgia Institute of Technology College of Sciences

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.

The goal of this talk is to explore curve graphs, which are combinatorial tools that encode topological information about surfaces. We focus on variants of the fine curve graph of a surface. The fine curve graph has its vertices essential simple closed curves on the surface and its edges connect pairs of curves that are disjoint. We will mention a sampling of related theorems which were proven in collaboration with various coauthors and then prove several results regarding the finitary curve graph, which has as its vertices essential simple closed curves while its edges connect pairs of curves that intersect at finitely many points.

In this talk, we will prove that the finitary curve graph has diameter 2 (geometry), that the flag complex induced by the finitary curve graph is contractible (topology), and that the automorphism group of the finitary curve graph is naturally isomorphic to the homeomorphism group of the surface (combinatorics).

Work mentioned in the talk will be a subset of independent work and of collaborations with Katherine Booth, Ryan Dickmann, Dan Minahan, and Alex Nolte. The talk will be aimed at a non-expert audience.

I will talk about the application of algebra and algebraic geometry to matroid theory. Baker and Bowler developed the notions of weak and strong matroids over tracts. Later, Baker and Lorscheid developed the notion of foundation of a matroid, which characterize the representability of the matroid. I will introduce a variety of topics under this theme. First, I will talk about a condition which is sufficient to guarantee that the notions of strong and weak matroids coincide. Next, I will describe a software program that computes all representations of matroids over a field, based on the theory of foundations. Finally, I will define a notion of rank for matrices over tracts in order to get uniform proofs of various results about ranks of matrices over fields.

Zoom link.  Meeting ID: 914 2801 6313, Passcode: 501018

We examine the relationship between Dupire's functional derivative and a variant of the functional derivative developed by Kim for analyzing functionals in systems with delay. Our findings demonstrate that if Dupire's space derivatives exist, differentiability in any continuous functional direction implies differentiability in any other direction, including the constant one. Additionally, we establish that co-invariant differentiable functionals can lead to a functional Ito formula in the Cont and Fournié path-wise setting under the right regularity conditions.

Next, our attention turns to functional extensions of the Meyer-Tanaka formula and the efforts made to characterize the zero-energy term for integral representations of functionals of semimartingales. Using Eisenbaum's idea for reversible semimartingales, we obtain an optimal integration formula for Lévy processes, which avoids imposing additional regularity requirements on the functional's space derivative, and extends other approaches using the stationary and martingale properties of Lévy processes.

Finally, we address the topic of integral representations for the delta of a path-dependent pay-off, which generalizes Benth, Di Nunno, and Khedher's framework for the approximation of functionals of jump-diffusions to cases where they may be driven by a process satisfying a path-dependent differential equation. Our results extend Jazaerli and Saporito's formula for the delta of functionals to the jump-diffusion case. We propose an adjoint formula for the horizontal derivative, hoping to obtain more tractable formulas for the Delta of strongly path-dependent functionals.

Committee 

• Prof. Christian Houdré - School of Mathematics, Georgia Tech (advisor)
• Prof. Michael Damron - School of Mathematics, Georgia Tech
• Prof. Rachel Kuske - School of Mathematics, Georgia Tech
• Prof. Andrzej Święch - School of Mathematics, Georgia Tech
• Prof. José Figueroa-López - Department of Mathematics and Statistics, Washington University in St. Louis
• Prof. Bruno Dupire - Department of Mathematics, New York University