Georgia Institute of Technology College of Sciences

A class of graphs is said to be $\chi$-bounded with binding function $f$ if for every such graph $G$, it satisfies $\chi(G) \leq f(\omega(G)$, and polynomially $\chi$-bounded if $f$ is a polynomial. It was conjectured that chair-free graphs are perfectly divisible, and hence admit a quadratic $\chi$-binding function. In addition to confirming that chair-free graphs admit a quadratic $\chi$-binding function, we will extend the result by demonstrating that $t$-broom free graphs are polynomially $\chi$-bounded for any $t$ with binding function $f(\omega) = O(\omega^{t+1})$. A class of graphs is said to satisfy the Vizing bound if it admits the $\chi$-binding function $f(\omega) = \omega + 1$. It was conjectured that (fork, $K_3$)-free graphs would be 3-colorable, where fork is the graph obtained from $K_{1, 4}$ by subdividing two edges. This would also imply that (paw, fork)-free graphs satisfy the Vizing bound. We will prove this conjecture through a series of lemmas that constrain the structure of any minimal counterexample.

 In first-passage percolation (FPP), we let $\tau_v$ be i.i.d. nonnegative weights on the vertices of a graph and study the weight of the minimal path between distant vertices. If $F$ is the distribution function of $\tau_v$, there are different regimes: if $F(0)$ is small, this weight typically grows like a linear function of the distance, and when $F(0)$ is large, the weight is typically of order one. In between these is the critical regime in which the weight can diverge but does so sublinearly. This talk will consider a dynamical version of critical FPP on the triangular lattice where vertices resample their weights according to independent rate-one Poisson processes. We will discuss results that show that if the sum of $F^{-1}(1/2+1/2^k)$ diverges, then a.s. there are exceptional times at which the weight grows atypically, but if the sum of $k^{7/8} F^{-1}(1/2+1/2^k)$ converges, then a.s. there are no such times. Furthermore, in the former case, we compute the Hausdorff and Minkowski dimensions of the exceptional set and show that they can be but need not be equal. Then we will consider what the model looks like when the weight of a long path is unusually small by considering an analogous construction to Kesten's incipient infinite cluster in the FPP setting. This is joint work with M. Damron, J. Hanson, W.-K. Lam.

Finally, we discuss a result related to work of Damron-Lam-Wang ('16) that the growth of the passage time to distance $n$ ($\mathbb{E}T(0,\partial B(n))$, where $B(n) = [-n,n]^2$)  has the same order (up to a constant factor) as the sequence $\mathbb{E}T^{\text{inv}}(0,\partial B(n))$. This second passage time is the minimal total weight of any path from 0 to $\partial B(n)$ that resides in a certain embedded invasion percolation cluster. We discuss a result that claims this constant factor cannot be taken to be 1. This result implies that the time constant for the model is different than that for the related invasion model, and that geodesics in the two models have different structures. This was joint work with M. Damron. 

 

 

Dissertation defense information

Date and Time: July 22, 2022, 08:30 am - 10:30 am (EST)

Location:

• Skiles 006 (In-person)
• Zoom meeting (Online): https://gatech.zoom.us/j/96755126860

 

Summary

This dissertation consists of two topics concerning algebraic and semi-algebraic invariants on quadrics.

 The ranks of the minimal graded free resolution of square-free quadratic monomial ideals can be investigated combinatorially. We study the bounds on the algebraic invariant, Castelnuovo-Mumford regularity, of the quadratic ideals in terms of properties on the corresponding simple graphs. Our main theorem is the graph decomposition theorem that provides a bound on the regularity of a quadratic monomial ideal. By combining the main theorem with results in structural graph theory, we proved, improved, and generalized many of the known bounds on the regularity of square-free quadratic monomial ideals.

 The Hankel index of a real variety is a semi-algebraic invariant that quantifies the (structural) difference between nonnegative quadrics and sums of squares on the variety. This project is motivated by an intriguing (lower) bound of the Hankel index of a variety by an algebraic invariant, the Green-Lazarsfeld index, of the variety. We study the Hankel index of the image of the projection of rational normal curves away from a point. As a result, we found a new rank of the center of the projection which detects the Hankel index of the rational curves. It turns out that the rational curves are the first class of examples that the lower bound of the Hankel index by the Green-Lazarsfeld index is strict.

 

Advisor: Dr. Grigoriy Blekherman, School of Mathematics, Georgia Institute of Technology

Committee:

• Dr. Matthew Baker, School of Mathematics, Georgia Institute of Technology
• Dr. Anton Leykin, School of Mathematics, Georgia Institute of Technology
• Dr. Rainer Sinn, Institute of Mathematics, Universität Leipzig
• Dr. Josephine Yu, School of Mathematics, Georgia Institute of Technology

 

ABSTRACT: This manuscript explores many convolution (restricted summation) type sequences via certain types of matrix based factorizations that can be used to express their generating functions. These results are a main focus of the author's publications from 2017-2021. The last primary (non-appendix) section of the thesis explores the topic of how to best rigorously define a so-termed "canonically best" matrix based factorization for a given class of convolution sum sequences. The notion of a canonical factorization for the generating function of such sequences needs to match the qualitative properties we find in the factorization theorems for Lambert series generating functions (LGFs). The expected qualitatively most expressive expansion we find in the LGF case results naturally from algebraic constructions of the underlying LGF series type. We propose a precise quantitative requirement to generalize this notion in terms of optimal cross-correlation statistics for certain sequences that define the matrix based factorizations of the generating function expansions we study. We finally pose a few conjectures on the types of matrix factorizations we expect to find when we are able to attain the maximal (respectively minimal) correlation statistic for a given sum type. COMMITTEE:

• Dr. Josephine Yu, Georgia Tech
• Dr. Matthew Baker, Georgia Tech
• Dr. Rafael de la Llave, Georgia Tech
• Dr. Jayadev Athreya, University of Washington
• Dr. Bruce Berndt, University of Illinois at Urbana-Champaign

HYBRID FORMAT LOCATIONS:

• In-person location: Skiles 006
• Online GT Zoom link: GT Zoom -- Meeting ID (999 9743 8538) -- Passcode (057722)

LINKS:

• Thesis manuscript (PDF format): thesis-manuscript-2022.06.21-v1.pdf