Georgia Institute of Technology College of Sciences

Tropicalization involves passing to an ordered group M, usually taken to be (R, +) or (Q, +), and viewed as a semifield. Although there is a rich theory arising from this viewpoint, idempotent semirings possess a restricted algebraic structure theory, and also do not reflect important valuation-theoretic properties, thereby forcing researchers to rely often on combinatoric techniques. Our research in tropical algebra has focused on coping with the fact that the max-plus’ algebra lacks negation, which is used throughout the classical structure theory of modules. At the outset one is confronted with the obstacle that different cosets need not be disjoint, which plays havoc with the traditional structure theory. Building on an idea of Gaubert and his group (including work of Akian and Guterman), we introduce a general way of artificially providing negation, in a manner similar to the construction of Z from N but with one crucial difference necessitated by the fact that the max-plus algebra is not additively cancelative! This leads to the possibility of defining many auxiliary tropical structures, such as Lie algebras and exterior algebras, and also providing a key ingredient for a module theory that could enable one to use standard tools such as homology.

We discuss applications of Hodge theory which is a part of algebraic geometry to problems in combinatorics, in particular to Rota's Log-concavity Conjecture. The conjecture was motivated by a question in enumerating proper colorings of a graph which are counted by the chromatic polynomial. This polynomial's coefficients were conjectured to form a unimodal sequence by Read in 1968. This conjecture was extended by Rota in his 1970 ICM address to assert the log-concavity of the characteristic polynomial of matroids which are the common combinatorial generalizations of graphs and linear subspaces. We discuss the resolution of this conjecture which is joint work with Karim Adiprasito and June Huh. The solution draws on ideas from the theory of algebraic varieties, specifically Hodge theory, showing how a question about graph theory leads to a solution involving Grothendieck's standard conjectures. This talk is a preview for the upcoming workshop at Georgia Tech.

A significant achievement of modern probability theory is the development of sharp connections between the boundedness of random processes and the geometry of the underlying index set. In particular, the generic chaining method of Talagrand provides in principle a sharp understanding of the suprema of Gaussian processes. The multiscale geometric structure that arises in this method is however notoriously difficult to control in any given situation. In this talk, I will exhibit a surprisingly simple but very general geometric construction, inspired by real interpolation of Banach spaces, that is readily amenable to explicit computations and that explains the behavior of Gaussian processes in various interesting situations where classical entropy methods are known to fail. (No prior knowledge of this topic will be assumed in the talk.)

The eigendecomposition of an adjacency matrix provides a way to embed a graph as points in finite dimensional Euclidean space. This embedding allows the full arsenal of statistical and machine learning methodology for multivariate Euclidean data to be deployed for graph inference. Our work analyzes this embedding, a graph version of principal component analysis, in the context of various random graph models with a focus on the impact for subsequent inference. We show that for a particular model this embedding yields a consistent estimate of its parameters and that these estimates can be used to accurately perform a variety of inference tasks including vertex clustering, vertex classification as well as estimation and hypothesis testing about the parameters.

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process.We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians, a generalization of Laplacian matrices that arise in many problems inimage and signal processing.We also prove that every connection Laplacian has a linear sized approximate inverse. This is an LU factorization with a linear number of nonzero entries that is a strong approximation of the originalmatrix. Using such a factorization one can solve systems of equations in a connection Laplacian in linear time. Such a factorization was unknown even for ordinary graph Laplacians.Joint work with Rasmus Kyng, Yin Tat Lee, Sushant Sachdeva, and Daniel Spielman. Manuscript at http://arxiv.org/abs/1512.01892.

I will give a broad overview of the Hard Lefschetz property and the Hodge-Riemann relations in the theory of polytopes, complex manifolds, invariants, algebraic varieties, and tropical varieties.

A one day workshop on the proof of Rota's conjecture on the log concavity of coefficients of the characteristic polynomial of a matroid. Please register: https://www.math.gatech.edu/hodge2016