Georgia Institute of Technology College of Sciences

Abstract: While spectral methods provide far-ranging insights on graph structure, there remain significant challenges in their application to real data. Most notably, spectral methods do not incorporate information that maybe available beyond adjacency.  A common approach to incorporating such additional information is encode this information in an ad-hoc manner into weights associated with the edges. Not only does this have limited expressivity, but is also restricted by graph structure: if two vertices are not adjacent, then edge weights cannot capture any closeness implied by metadata.

We address this issue by introducing the inner product Hodge Laplacian for an arbitrary simplicial complex.  Within this framework we prove generalizations of foundational results in spectral graph theory, such as the Cheeger inequality and the expander mixing lemma, and show our framework recovers the usual combinatorial and normalized Laplacians as special cases. Our framework allows for the principled synthesis of combinatorial approaches in network science with more metadata driven approaches by using latent space encodings of the metadata to define an inner product both the vertices and the edges.

(Coffee will be available at 3:30 before this talk, following the speaker's Professional Development Seminar at 2:30pm.)

In this talk, I will discuss my recent research on the asymptotic stability and inviscid damping of 2D monotone shear flows with non-constant density in inhomogeneous ideal fluids within a finite channel. More precisely, I proved that if the initial perturbations belong to the Gevrey-2- class, then linearly stable monotone shear flows in inhomogeneous ideal fluids are also nonlinear asymptotically stable. Furthermore, inviscid damping is proved to hold, meaning that the perturbed velocity converges to a shear flow as time approaches infinity.

The dynamic shortest path problem seeks to maintain the shortest paths/distances between pairs of vertices in a graph that is subject to edge insertions, deletions, or weight changes. The aim is to maintain that information more efficiently than naive recomputation via, e.g., Dijkstra's algorithm.
We present the first fully dynamic algorithm maintaining exact single source distances in unweighted graphs. This resolves open problems stated in [Demetrescu and Italiano, STOC'03], [Thorup SWAT'04], [Sankowski, COCOON 2005] and [vdBrand and Nanongkai, FOCS 2019].
In this talk, we will see how ideas from fine-grained complexity theory, computer algebra, and graph theory lead to insights for dynamic shortest paths problems.

Oriented matroids are matroids with extra sign data, and they are useful in the tropical study of real algebraic geometry. In order to study the topology of real algebraic hypersurfaces constructed from patchworking, Renaudineau and Shaw introduced an algebraically defined filtration of the tope space of an oriented matroid based on Quillen filtration. We will prove the equality between their filtration (together with the induced maps), the topologically defined Kalinin filtration, and the combinatorially defined Varchenko-Gelfand dual degree filtration over Z/2Z. We will also explain how the dual degree filtration can serve as a Z-coefficient version of the other two in this setting. This is joint work with Kris Shaw.