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, not any particular department, university, nor region.
Organizer: Daniel Irving Bernstein
Contact: dibernst@mit.edu, bernstein.daniel@gmail.com
Time: Thursdays at 10AM EST (flexible, depending on speaker's time zone and schedule).
Zoom link: https://mit.zoom.us/j/481638076
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.

Schedule

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 5, 10am EST:

 Slides  Video arXiv
  Speaker: Oliver Clarke (University of Bristol)
  Title: Line Arrangements and Matroid Varieties from Conditional Independence Statements
  Abstract: We will explore the connection between probability distributions satisfying certain conditional independence (CI) constraints, arising from algebraic statistics, and realisation spaces of matroids. For each collection of CI statements, we associate an ideal whose primary decomposition gives a characterisation of the distributions satisfying the original CI statements. Classically these ideals are generated by 2-minors of a matrix of variables, however in the presence of hidden variables the ideals may contain higher degree minors. This leads to the study of the structure of determinantal hypergraph ideals which naturally include CI ideals and whose decomposition can be understood in terms of matroids. We provide a general framework for working with hypergraph ideals and give a number of applications of our method, yielding new families of results and new interpretations of existing results. This presentation is based on two joint works: one with Kevin Grace, Fatemeh Mohammadi and Leonid Monin, and another with Fatemeh Mohammadi and Harshit Motwani.

Nov 12, 10am EST:

 Slides   Video Preprint
  Speaker: Fei Wang (KTH)
  Title: Uniqueness of Low Rank Matrix Completion and Schur Complement
  Abstract: We study the low rank matrix completion problem. We give a sufficient and necessary condition such that the completed matrix is globally unique. We assume the observed entries of the matrix corresponds to a special chordal graph. Under this assumption, the matrix completion problem is either globally unique or it has infinitely many solutions (thus excluding local uniqueness). The proof of the theorems make extensive use of the Schur complement.

Nov 19, 10am EST:

 Slides   Video arXiv
  Speaker: Bernd Schulze (Lancaster University)
  Title: Frameworks with coordinated constraints and a union of matroids
  Abstract: In this talk we will discuss the rigidity of bar-joint frameworks in Euclidean d-space in which specified classes of edges are allowed to change length in a coordinated fashion that requires differences of lengths to be preserved within each class. We show that rigidity for these coordinated frameworks is a generic property, and we characterize the rigid graphs in terms of redundant rigidity in the standard d-dimensional rigidity matroid. We also interpret these results in terms of matroid unions. This is joint work with Hattie Serocold and Louis Theran.

Dec 3, 10am EST:

 Slides   Video arXiv
  Speaker: Sean Dewar (Johann Radon Institute of Computational and Applied Mathematics)
  Title: Homothetic packings of centrally symmetric convex bodies
  Abstract: A centrally symmetric convex body is a convex compact set with non-empty interior that is symmetric about the origin. Of particular interest are those that are both smooth and strictly convex -- known here as regular symmetric bodies -- since they retain many of the useful properties of the d-dimensional Euclidean ball. In this presentation I will prove that for any given regular symmetric body C, a homothetic packing of copies of C with randomly chosen radii will have a (2,2)-sparse planar contact graph. Further, I will prove that the converse (i.e., given a (2,2)-sparse planar graph G, a centrally symmetric body C and a set of radii r_1,...,r_n, there is a non-zero probability that a homothetic packing of n-copies of C with the given radii will have contact graph G) will hold for a comeagre set of centrally symmetric convex bodies.