Georgia Institute of Technology College of Sciences

This dissertation consists of various topics in nonlinear algebra. Particularly, it focuses on solving algebraic problems and polynomial systems through the use of combinatorial tools. We give a broad introduction and discuss connections to applied algebraic geometry, polyhedral, and tropical geometry. The individual topics discussed are as follows:

• Interaction between tropical and classical convexity, with a focus on the tropical convex hull of convex sets and polyhedral complexes. Amongst other results, we characterize tropically convex sets in any dimension, and give a combinatorial description for the dimension of the tropical convex hull of an ordinary affine space. 
• The steady-state degree and mixed volume of a chemical reaction network. We present three case studies of infinite families of networks. For each family, we give a formula for the steady-state degree and mixed volume of the corresponding polynomial system. 
• Methods for finding the solution set of a generic system in a family of polynomial systems with parametric coefficients. We present a framework for describing monodromy-based solvers in terms of decorated graphs. 

Thesis may be viewed here.

BlueJeans link

The probabilistic method is one of the most powerful tools in combinatorics: it has been used to show the existence of many hard-to-construct objects with exciting properties. It also attracts broad interests in designing and analyzing algorithms to find and construct these objects in an efficient way. In this dissertation we obtain four results using algorithmic approaches in probabilistic method:
1. We study the structural properties of the triangle-free graphs generated by a semirandom variant of triangle-free process and obtain a packing extension of Kim’s famous R(3, t) results. This allows us to resolve a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabo, and answer a problem in extremal graph theory by Esperet, Kang, and Thomasse.
2. We determine the order of magnitude of Prague dimension, which concerns efficient encoding and decomposition of graphs, of binomial random graph with high probability. We resolve conjectures by Furedi and Kantor. Along the way, we prove a Pippenger-Spencer type edge coloring result for random hypergraphs with edges of size O(log n).
3. We analyze the number set generated by r-AP free process, which answers a problem raised by Li and has connection with van der Waerden number in additive combinatorics and Ramsey theory.
4. We study a refined alteration approach to construct H-free graphs in binomial random graphs, which has applications in Ramsey games.

The Bluejeans link of the defense is https://gatech.bluejeans.com/233874892

Costas arrays are useful in radar and sonar engineering and many other settings in which optimal 2-D autocorrelation is needed: they are permutation matrices in which the vectors joining different pairs of ones are all distinct.
In this talk we discuss some of these applications, and prove that the density of Costas arrays among permutation matrices decays exponentially, solving a core problem in the theory of Costas arrays. 
The proof is probabilistic, and combines ideas from random graph theory with tools from probabilistic combinatorics.

Based on joint work in progress with Bill Correll, Jr. and Lutz Warnke.

The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$.  In joint work with Dong Yeap Kang, Daniela Kühn, Abhishek Methuku, and Deryk Osthus, we proved this conjecture for every sufficiently large $n$.  In this talk, I will present the history of this conjecture and sketch our proof in a special case.