Virtual seminar on algebraic matroids, rigidity theory, distance geometry, and geometric constraint systems

The COVID-19 pandemic is forcing us all to stay home, foregoing conferences and departmental seminars for the next few months. This weekly virtual seminar is an attempt to patch that departmental-seminar-sized void in our lives until it is safe to resume our more traditional forms of professional networking. Since geographic location matters a lot less for a virtual seminar than for an in-person seminar, this virtual seminar will be defined purely by its mathematical theme, algebraic matroids and rigidity theory, and not any particular department nor region.

Organizer: Daniel Irving Bernstein
Time: Thursdays at 10AM EST (flexible, depending on speaker's time zone and schedule).
Zoom link:
Instructions: If you do not already have Zoom dowloaded, you will need to do so (but you don't need to make an account). Enter the seminar with the Zoom link above. There is a password that I will send to the attendee list. When you enter, your microphone will be muted. If you want to ask a question, you can click the "raise hand" button, or type your question into the chat, or just un-mute yourself and ask.

Click here for videos of talks between March 26 and July 23, 2020.


Sept 10, 10am EST:

Slides   Video arXiv
Speaker: Sean Dewar (Johann Radon Institute of Computational and Applied Mathematics)
Title: Which graphs are rigid in lp spaces?
Abstract: To consider whether a bar-joint framework is rigid or flexible, we model the bars as distance constraints between the joints. We classically use the Euclidean metric to measure these distances, but what happens if we allow other types of metrics? In short, strange things happen; triangles are no longer rigid, and in some cases the very concept of rigidity begins to unravel. In this presentation I will consider the relatively tame class of smooth lq norms. I will give a detailed background on the subject of general normed space rigidity, plus I will classify various types of graphs that are rigid in lq spaces for dimensions 3 and higher. This talk is based on joint work with Derek Kitson and Anthony Nixon.

Sept 17, 11am EST:

Slides   Video arXiv
Speaker: Nikki Meshkat (Santa Clara University)
Title: Identifiability and observability of biological models using algebraic matroids
Abstract: Parameter identifiability analysis addresses the problem of which unknown parameters of a model can be determined from given input/output data. If all of the parameters of a model can be determined from data, the parameters and the model are called identifiable. However, if some subset of the parameters can not be determined from data, the model is called unidentifiable. Another problem is observability, which deals with whether or not the state variables in a model can be recovered from observation of the input and output alone. In the case of "perfect" data, these problems of identifiability and observability are typically solved using a differential algebra approach involving Groebner basis computations. However, for large models, using Groebner bases becomes computationally expensive and other methods are sought after. We demonstrate how algebraic matroids can be used to analyze the problems of identifiability and observability. This is joint work with Zvi Rosen and Seth Sullivant.

Sept 24, 10am EST:

Slides   Video arXiv
Speaker: Tony Nixon (Lancaster University)
Title: Rigidity of linearly constrained frameworks in d-dimensions
Abstract: We consider the problem of characterising the generic rigidity of bar-joint frameworks in d-dimensions in which each vertex is constrained to lie in a given affine subspace. The special case when d=2 was previously solved by Streinu and Theran in 2010. After introducing the basic notions of rigidity theory and describing their result, I will discuss extensions characterising linearly constrained rigidity in d-dimensional space. In particular, the case when each vertex is constrained to lie in an affine subspace of dimension t and d\geq t(t-1) was solved in collaboration with Cruickshank, Guler and Jackson while a new result with Jackson and Tanigawa improves this to apply whenever d\geq 2t.

Oct 22, 10am EST:

Slides   Video arXiv
Speaker: Hao Hu (University of Waterloo)
Title: Facial Reduction for Symmetry Reduced Semidefinite and Doubly Nonnegative Programs
Abstract: We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN, relaxation of many classes ofhard combinatorial problems. We also show that the singularity degree does not increase after SR, and that the DNN relaxations considered here have singularity degree one, that is reduced to zero after FR. The combination of FR and SR leads to a significant improvement in both numerical stability and running time for both the ADMM and interior point approaches. We test our method on various DNN relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than n=500. This translates to a semidefinite constraint of order 250,000 and 625x10^8 nonnegative constrained variables.

Oct 29, 3pm EST

Slides   Video arXiv
Speaker: Elizabeth Gross (University of Hawai'i at Mānoa)
Title: The maximum likelihood threshold of a graph
Abstract: The maximum likelihood threshold of a graph is the smallest number of data points that guarantees that maximum likelihood estimates exist almost surely in the Gaussian graphical model associated to the graph. In this talk, we will show that this graph parameter is connected to the theory of combinatorial rigidity. In particular, if the edge set of a graph G is an independent set in the (n-1)-dimensional generic rigidity matroid, then the maximum likelihood threshold of G is less than or equal to n. This connection allows us to make several new statements regarding the existence of the maximum likelihood estimator in situations of limited data.

Nov 12, 10am EST:

Slides   Video arXiv
Speaker: Fei Wang (KTH)
Title: TBD
Abstract: TBD

Nov 19, 10am EST:

Slides   Video arXiv
Speaker: Bernd Schultze (Lancaster University)
Title: TBD
Abstract: TBD