Georgia Institute of Technology College of Sciences

Graphs are central objects of study in Discrete Mathematics. A graph consists of a set of vertices, some of which are connected by edges. Their elementary structure makes graphs widely applicable, but the theoretical understanding of graphs is far from complete. Extremal graph theory aims to find connections between global parameters and substructure. A key topic is how a large average or minimum degree of a graph can force certain subgraphs (where the degree is the number of edges at a vertex). For instance, Erdős and Gallai proved in the 1960's that any graph of average degree at least $k$ contains a path of length $k$. Some of the most intriguing open questions in this area concern trees (connected graphs without cycles) as subgraphs. For instance, can one substitute the path from the previous paragraph with a tree? We will give an overview of open problems and recent results in this area, as well as their possible extensions to hypergraphs.

The contact invariant, introduced by Kronheimer and Mrowka,
is an element in the monopole Floer homology of a 3-manifold which is
canonically attached to a contact structure. I will describe an
application of monopole Floer homology and the contact invariant to
study the topology of spaces of contact structures and
contactomorphisms on 3-manifolds. The main new tool is a version of
the contact invariant for families of contact structures.
 

Restricting to symmetric homogeneous polynomials of degree 2d we compare the cones of nonnegative polynomials with the cone of sums of squares when the number of variables goes to infinity. We consider two natural notions of limit and for each we completely characterize the degrees for which the limit cones are equal. To distinguish these limit cones we tropicalize their duals, which we compute via tropicalizing spectrahedra and tropical convexity. This gives us convex polyhedral cones which we can completely describe and from them obtain explicit examples of nonnegative symmetric polynomials that are not sums of squares (in some cases for any number >=4 of variables).

This is joint work with Grigoriy Blekherman, Sebastian Debus, and Cordian Riener.

Microsoft Teams Link

Algebra Student Seminar homepage

Generative networks have made it possible to generate meaningful signals such as images and texts. They were also extended to graphs and applied, for example, to generate molecules. However, the mathematical properties of generative methods are unclear, and training good generative models is difficult. Moreover, some basic and intuitive ideas of generative networks for signals and images do not apply to graphs and we thus focus on this talk on graph generation. An earlier joint work of the speaker generalized Mallat's scattering transform to graphs and later used it as an encoder within an autoencoder for graph generation (while applying a simple Gaussianization procedure to the output of the encoder) . For the graph scattering component, this work proved asymptotic invariance to permutations and stability to graph manipulations. The issue is that the decoder of this graph generation component used two fully connected networks and was not adapted to the graph structure. In fact, many other graph generation methods do not sufficiently utilize the graph structure. In order to address this issue, I will present a new recent joint work that develops a novel and trainable graph unpooling layer for effective graph generation. Given a graph with features, the unpooling layer enlarges this graph and learns its desired new structure and features. Since this unpooling layer is trainable, it can be applied to graph generation either in the decoder of a variational autoencoder or in the generator of a generative adversarial network (GAN). We establish connectivity and expressivity. That is, we prove that the unpooled graph remains connected and any connected graph can be sequentially unpooled from a 3-nodes graph. We apply the unpooling layer within the GAN generator and address the specific task of molecular generation. This is a joint work with Yinglong Guo and Dongmian Zou.