Applied and Computational Algebra and Geometry

Systems biology focuses on modeling complex biological systems, such as metabolic and cell signaling networks. These biological networks are modeled with polynomial dynamical systems that can be described with directed graphs. Analyzing these systems at steady-state results in polynomial ideals with significant combinatorial structure and whose elements can be used for model selection. Focusing on the problem of finding steady-state invariants of an elimination ideal, we explore the algebra of decomposing a larger reaction network into smaller subnetworks. This talk is based on joint work with Heather Harrington, Nicolette Meshkat, and Anne Shiu.

To each torus-equivariant vector bundle over a smooth complete toric variety, we associated a representable matroid (essentially a finite collection of vectors). In this talk, we will describe how the combinatorics of this matroid encodes a resolution of the toric vector bundles by a complex whose terms are direct sums of toric line bundles. With some luck, we will also outline some applications to the equations and syzygies of smooth projective toric varieties.

We study the mínimum distance function of a complete intersection graded ideal in a polynomial ring with coefficients in a field. For graded ideals of dimension one, whose initial ideal is a complete intersection, we use the footprint function to give a sharp lower bound for the minimum distance function. Then we show some applications to coding theory and combinatorics.

The brain represents stimuli via patterns of neural activity. These activity patterns can be described by a neural code, e.g. a collection of indicator vectors showing which neurons co-fire in response to various stimuli. It is believed that the brain can infer many properties of the stimulus space purely from the intrinsic structure of the neural code. In this talk, we present algebraic techniques that enable us to determine if a given neural code is convex, and thus has additional structure that can be used to understand stimulus space structure.

Non-linear rank of a matrix M is the minimal possible rank of a matrix obtained by applying arbitrary monotone-increasing functions to each row of M. The problem of finding the non-linear rank often arises in neuroscience context. In this talk I will explain how the topology of hyperplane arrangements is closely related to the problem of finding a non-linear rank. This relationship is accomplished via a zigzag of combinatorial codes, not unlike the Dowker complex. I will then present an algebraic approach and computational results for estimating the nonlinear rank.

We describe a probabilistic algorithm which solves a polynomial system over the rationals defined by a reduced regular sequence. Its bit complexity is roughly quadratic in the Bézout number of the system and linear in its bit size. Our algorithm solves the input system modulo a prime number $p$ and applies $p$-adic lifting. Our approach is based on a new result on the bit length of a "lucky" prime $p$, namely one for which the reduction of the input system modulo $p$ preserves certain fundamental geometric and algebraic properties of the original system. These results rely on the analysis of Chow forms associated to the set of solutions of the input system and effective arithmetic Nullstellensätze. Joint work with Nardo Giménez.

This talk introduces a combinatorial algebraic framework to encode, compute, and analyze topological summaries of geometric data. The motivating problem from evolutionary biology involves statistics on a dataset comprising images of fruit fly wing veins. The algebraic structures take their cue from graded polynomial rings and their modules, but the theory is complicated by the passage from integer exponent vectors to real exponent vectors. The path to effective methods is built on appropriate finiteness conditions, to replace the usual ones from commutative algebra, and on an understanding of how datasets of this nature interact with moduli of modules. I will introduce the biology and topology from first principles. Joint work with David Houle (Biology, Florida State), Ashleigh Thomas (grad student, Duke Math), Justin Curry (postdoc, Duke Math), and Surabhi Beriwal (undergrad, Duke Math).

The standard Kuramoto model (all-to-all with uniform coupling) is used to describe synchronization behavior of a large set of oscillators. Using algebraic geometry, the equilibria of this model can be computed by solving a system of polynomial equations. We develop an approach which computes only the real solutions to this system of polynomial equations by reducing down to solving a collection of univarite functions. We compare this new approach with other approaches in computational algebraic geometric. The univariate reduction also allows us to prove that, asymptotically, the maximum number of real solutions grows at the same rate as the number of complex solutions.

In the last two decades applied topologists have developed numerous methods for `measuring' and building combinatorial representations of the shape of the data. The most famous example of the former is persistent homology. This adaptation of classical homology assigns a barcode, i.e. a collection of intervals with endpoints on the real line, to a finite metric space. Unfortunately, barcodes are not well-adapted for use by practitioners in machine learning tasks. We can circumvent this problem by assigning numerical quantities to barcodes and these outputs can then be used as input to standard algorithms. I will talk about tropical functions that can be used as coordinates on the space of barcodes. All of these are stable with respect to the standard distance functions (bottleneck, Wasserstein) used on the barcode space.

We consider "symbolic polynomials" that generalize the usual polynomials by allowing multivariate integer valued polynomials as exponents. Earlier we have shown how to compute GCDs, factorizations and functional decomposition of these objects. The present work asks whether it is meaningful to compute Gröbner bases of sets of symbolic polynomials, and, if so, how do these "symbolic" Gröbner bases relate to the usual Gröbner bases when the exponents are specialized.

The brain processes information about the environment via neural codes. The neural ideal was introduced recently as an algebraic object that can be used to better understand the combinatorial structure of neural codes. Every neural ideal has a particular generating set, called the canonical form, that directly encodes a minimal description of the receptive field structure intrinsic to the neural code. On the other hand, for a given monomial order, any polynomial ideal is also generated by its unique (reduced) Gr\"obner basis with respect to that monomial order. How are these two types of generating sets – canonical forms and Gr\"obner bases – related? Our main result states that if the canonical form of a neural ideal is a Gr\"obner basis, then it is the universal Gr\"obner basis (that is, the union of all reduced Gr\"obner bases). Furthermore, we prove that this situation – when the canonical form is a Gr\"obner basis – occurs precisely when the universal Gr\"obner basis contains only pseudo-monomials (certain generalizations of monomials). Our results motivate two questions: (1) When is the canonical form a Gr\"obner basis? (2) When the universal Gr\"obner basis of a neural ideal is not a canonical form, what can the non-pseudo-monomial elements in the basis tell us about the receptive fields of the code? We give partial answers to both questions. Along the way, we develop a representation of pseudo-monomials as hypercubes in a Boolean lattice.

Let $M$ be a non-negative $n\times n$ integer matrix with all the diagonal entries equal to zero. An arithmetical structure (AS) on $M$ is a pair $({\bf d},{\bf r}) \in \mathbb{N}_+^n\times \mathbb{N}_+^n$ such that $\mathrm{gcd}({\bf r}_v\, | \,v\in V(G))=1$ and \[ (\mathrm{diag}({\bf d})-M){\bf r}^t={\bf 0}^t. \] The concept of AS was introduced by Lorenzini as some intersection matrices that arise in the study of degenerating curves in algebraic geometry. If $M$ is the adjacency matrix of a graph $G$ and ${\bf d}$ is its degree vector, then $\mathrm{diag}({\bf d})-M$ is the Laplacian matrix of $G$. It can be proved that $M$ is irreducible if and only if \[ \mathcal{A}(M)=\{({\bf d},{\bf r}) \in \mathbb{N}_+^n\times \mathbb{N}_+^n\, |\, (\mathrm{diag}({\bf d})-M){\bf r}^t={\bf 0}^t\} \] is finite. Recently an explicit description of the arithmetical structures of the path and cycle have been given. Let $X=(x_1,\ldots,x_n)$ be a vector with variables on each one of its entries and \[ f_M(X)=\mathrm{det}(\mathrm{diag}(X)-M). \] It is not difficult to check that if $({\bf d},{\bf r}) \in \mathcal{A}(M)$, then ${\bf d}$ is a solution of the Diophantine equation $f_M(X)=0$. Note that the converse is not true. By Hilbert's tenth problem is not clear that an algorithm to compute the solutions of this class of Diophantine equations or even the arithmetical structures of $M$ exist. In this talk we will present an algorithm to compute the AS on $M$. Finally, if the time permits we will present some details of the implementation of this algorithm. Joint work with Ralihe R. Villagran.

The network inference problem consists in reconstructing the structure or wiring diagram of a dynamic network from time-series data. Even though this problem has been studied in the past, there is no algorithm that guarantees perfect reconstruction of the structure of a dynamic network. In this talk I will present a framework and algorithm to solve the network inference problem for discrete-time networks that, given enough data, is guaranteed to reconstruct the structure with zero errors. The framework uses tools from algebraic geometry.

Many networks in the brain display internally-generated patterns of activity -- that is, they exhibit emergent dynamics that are shaped by intrinsic properties of the network rather than inherited from an external input. While a common feature of these networks is an abundance of inhibition, the role of network connectivity in pattern generation remains unclear. In this talk I will introduce Combinatorial Threshold-Linear Networks (CTLNs), which are simple "toy models" of recurrent networks consisting of threshold-linear neurons with binary inhibitory interactions. The dynamics of CTLNs are controlled solely by the structure of an underlying directed graph. By varying the graph, we observe a rich variety of emergent patterns including: multistability, neuronal sequences, and complex rhythms. These patterns are reminiscent of population activity in cortex, hippocampus, and central pattern generators for locomotion. I will present some theorems about CTLNs, and explain how they allow us to predict features of the dynamics by examining properties of the underlying graph. Finally, I'll show examples illustrating how these mathematical results guide us to engineer complex networks with prescribed dynamic patterns.