Georgia Institute of Technology College of Sciences

The Matroid Minors Project of Geelen, Gerards, and Whittle describes the structure of minor-closed classes of matroids representable by a matrix over a fixed finite field. To use these results to study specific classes, it is important to study the matroids in the class containing spanning cliques. A spanning clique of a matroid M is a complete-graphic restriction of M with the same rank as M.

In this talk, we will describe the structure of dyadic matroids with spanning cliques. The dyadic matroids are those matroids that can be represented by a real matrix each of whose nonzero subdeterminants is a power of 2, up to a sign. A subclass of the dyadic matroids is the signed-graphic matroids. In the class of signed-graphic matroids, the entries of the matrix are determined by a signed graph. Our result is that dyadic matroids with spanning cliques are signed-graphic matroids and a few exceptional cases.

The main results in this talk will come from joint work with Ben Clark, James Oxley, and Stefan van Zwam. This talk will include a brief introduction to matroids.

We'll talk about problems of optimizing a quadratic function subject to quadratic constraints, in addition to a sparsity constraint that requires that solutions have only a few nonzero entries. Such problems include sparse versions of linear regression and principal components analysis. We'll see that this problem can be formulated as a convex conical optimization problem over a sparse version of the positive semidefinite cone, and then see how we can approximate such problems using ideas arising from the study of hyperbolic polynomials. We'll also describe a fast algorithm for such problems, which performs well in practical situations.

Given n points on a disk, we will describe how to build an A-infinity category based on the instanton Floer complex of links, and explain why it is finitely generated. This is based on work in progress with Ko Honda.

This talk is part of the Atlanta Combinatorics Colloquium. Note the time (4pm) and location (Instructional Center 105).

It is easy to partition the vertices of any graph into two sets where each vertex has at least as many neighbours across as on its own side; take any maximal cut! Can we do the opposite? This is not possible in general, but Füredi conjectured in 1988 that it should nevertheless be possible on a random graph. I shall talk about our recent proof of Füredi's conjecture: with high probability, the random graph $G(n,1/2)$ on an even number of vertices admits a partition of its vertex set into two parts of equal size in which $n−o(n)$ vertices have more neighbours on their own side than across.