Virtual seminar on algebraic matroids and rigidity theory

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
Contact: dibernst@mit.edu, bernstein.daniel@gmail.com
Time: Thursdays at 10AM EST
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, click the "raise hand" button. If the speaker engages you, then unmute your microphone to ask your question. Be sure to re-mute once the speaker has finished addressing your question. There is also a group chat where people can type their questions (and answers).


Schedule

March 26:

 Slides   Video arXiv
  Speaker: Daniel Irving Bernstein (Massachusetts Institute of Technology)
  Title: The algebraic matroid of a Hadamard product of linear spaces
  Abstract: The algebraic matroid underlying a variety $V \subseteq \mathbb{C}^E$ is the combinatorial structure obtained by recording the dimensions of all coordinate projections of V. Understanding the algebraic matroids underlying particular varieties is useful in rigidity theory, matrix completion, and phylogenetics. In this talk, I will show how the algebraic matroid underlying a Hadamard product of two linear spaces can be derived from the matroids underlying each linear space using a construction of Edmonds and Rota. An immediate corollary is Laman's theorem from Rigidity theory.

April 2:

 Slides   Video arXiv1   arXiv2
  Speaker: Alexander Heaton (Max Planck Institute)
  Title: Epsilon local rigidity and numerical algebraic geometry
  Abstract: A well-known combinatorial algorithm can decide generic rigidity in the plane by determining if the graph is of Pollaczek-Geiringer-Laman type. Methods from matroid theory have been used to prove other interesting results, again under the assumption of generic configurations. However, configurations arising in applications may not be generic. We present Theorem 7 and its corresponding Algorithm 1 which decide if a configuration is epsilon-locally rigid, a notion we define. This provides a partial answer to a problem discussed in the 2011 paper of Hauenstein, Sommese, and Wampler. We also use numerical algebraic geometry to find nearby valid configurations which are not obtained by rigid motions. This is joint work with Andrew Frohmader.

April 9:

 Slides   Video arXiv
  Speaker: Ben Hollering (North Carolina State University)
  Title: Identifiability in Phylogenetics using Algebraic Matroids
  Abstract: Identifiability is a crucial property for a statistical model since it implies that distributions in the model uniquely determine the parameters that produce them. In phylogenetics, the identifiability of the tree parameter is of particular interest since it means that phylogenetic models can be used to infer evolutionary histories from data. Typical strategies for proving identifiability results require Gröbner basis computations which become untenable as the size of the model grows. In this talk I'll give some background on phylogenetic algebraic geometry and then discuss a new computational strategy for proving the identifiability of discrete parameters in algebraic statistical models that uses algebraic matroids naturally associated to the models. This algorithm allows us to avoid computing Gröbner bases and is also parallelizable.

April 16:

 Slides   Video Paper
  Speaker: Louis Theran (University of St. Andrews)
  Title: The pure condition of a minimally rigid graph
  Abstract: I'll talk about an old, but not well-known enough (?), result of White and Whiteley that describes when, for a generically minimally rigid graph G, a (necessarily non-generic) framework (G,p) is infinitesimally flexible.

April 23:

 Slides   Video
  Speaker: Eliana Duarte (Otto-von-Guericke Universität Magdeburg)
  Title: Rigidity of 2D and 3D quasicrystal frameworks
  Abstract: Deciding wether a generic 2D rod-and-pinion framework is rigid can be done by checking that its underlying graph satisfies the Laman conditions. For frameworks with a special configuration such as grids of squares, there is a simpler way to associate a graph to the framework and decide if it is rigid or not. In this talk I will consider frameworks that come from Penrose tilings and show that we can decide the rigidity of these frameworks as we do for grids of squares. There is no generalization of Laman conditions for rigidity of 3D graphs but perhaps we can prove (conjecture) a generalization of 2D results for cubical frameworks or 3D quasicrystals. Pictures and real time interactive animations will be present throughout this talk to illustrate important concepts. This talk is based on joint work with George Francis and students from the Illinois Geometry Lab.

April 30:

 Slides   Video arXiv
  Speaker: Jim Cruickshank (NUI Galway)
  Title: Surface graphs, gain sparsity and some applications in discrete geometry
  Abstract: A collection of line segments in the plane forms a 2-contact system if the segments have pairwise disjoint interiors and no pair of segments have an endpoint in common. Thomassen has shown that a graph is the intersection graph of such a 2-contact system if and only if it is a subgraph of a planar Laman graph. Also Haas, Orden, Rote, Francisco, Servatius, Servatius, Souvain, Streinu and Whiteley have shown that a graph admits a plane embedding as a pointed pseudotriangulation if and only if is a planar Laman graph. I will discuss recent work on symmetric versions of these results. In this context the graphs that arise are naturally embedded in the orbifold associated to the action of the symmetry group, and the appropriate sparsity conditions are gain sparsity conditions. Our main tools are new topological inductive constructions for the appropriate classes of surface graphs. All of the work presented here is joint with Bernd Schulze.

May 7:

 Slides   Video arXiv
  Speaker: Tony Nixon (Lancaster University)
  Title: Flexible circuits and d-dimensional rigidity
  Abstract: A framework is a geometric realisation of a graph in Euclidean d-space. Edges of the graph correspond to bars of the framework and vertices correspond to joints with full rotational freedom. The framework is rigid if every edge-length-preserving continuous deformation of the vertices arises from isometries of d-space. Generically, rigidity is a rank condition on an associated rigidity matrix and hence is a property of the graph which can be described by the corresponding row matroid. Characterising which graphs are generically rigid is solved in dimension 1 and 2. However determining an analogous characterisation when d\geq 3 is a long standing open problem, and the existence of non-rigid (i.e. flexible) circuits is a major contributing factor to why this problem is so difficult. We begin a study of flexible circuits by characterising the flexible circuits in d-dimensions which have at most d+6 vertices. This is joint work with Georg Grasegger, Hakan Guler and Bill Jackson.

May 14:

 Notes   Video arXiv1   arXiv2
  Speaker: Manolis Tsakiris (ShanghaiTech University)
  Title: Finiteness of fibers in matrix completion via Plucker coordinates
  Abstract: We describe a family of maximal elements of the algebraic matroid of the determinantal variety of at most rank-r matrices of size m x n over an infinite field k. For this, we formulate matrix completion as a hyperplane sections problem on the Grassmannian Gr(r,m) and use a family of local coordinates on Gr(r,m) induced by linkage matching fields, as described by Sturmfels & Zelevinsky (1993). Along the way we prove a conjecture of Rong, Wang & Xu (2019).

May 21:

 Notes   Video
  Speaker: Jessica Sidman (Mount Holyoke College)
  Title: Frameworks in special position: joints vs edges
  Abstract: Given a fixed graph G we can realize it in R^d where vertices correspond to universal joints and edges correspond to fixed-length bars. Asimow and Roth showed that either almost all realizations of G are rigid or almost all are flexible. In other words, rigidity is a generic property of a graph, depending only on combinatorics and the dimension of the ambient space. In this talk we will discuss different ways of describing the set of nongeneric realizations of a generically minimally rigid graph. In particular, we will compare two points of view. The first is the pure condition of White and Whiteley, which is connected to describing the geometry of configurations of joints which lead to nongeneric behavior. The second point of view (joint work with Rosen, Theran and Vinzant) uses the algebraic matroid on (squared) edge-lengths to describe nongenericity and is related to the edge supports of stresses in frameworks.

May 28:

  
  No speaker

June 4:

  
  No speaker

June 11:

  
  No speaker

June 18:

  
  No speaker

June 25:

 Slides   Video arXiv1   arXiv2
  Speaker: Bill Jackson (Queen Mary University of London)
  Title: Cofactor Matroids and Abstract Rigidity
  Abstract: We verify a conjecture of Walter Whiteley from 1996 that the C^1_2-cofactor matroid is the unique maximal abstract 3-rigidity matroid. We then use this result to obtain a good characterisation of the rank function of this matroid. This is joint work with Katie Clinch and Shin-Ichi Tanigawa.

July 2:

 Slides   Video arXiv
  Speaker: Patrick Lin (University of Illinois at Urbana-Champaign)
  Title: Maxwell-Cremona meets the Flat Torus
  Abstract: We consider three classes of geodesic embeddings of graphs on the plane and the Euclidean flat torus: graphs having a positive equilibrium stress, reciprocal graphs (for which there is an orthogonal embedding of the dual graph), and weighted Delaunay complexes. The classical Maxwell-Cremona correspondence and the well-known correspondence between convex hulls and weighted Delaunay triangulations imply that these three concepts are essentially equivalent for plane graphs. However, this three-way equivalence does not extend directly to geodesic graphs on the torus. Reciprocal and Delaunay graphs are equivalent, and every reciprocal graph is in positive equilibrium, but not every positive equilibrium graph is reciprocal. We establish a weaker correspondence: Every positive equilibrium graph on any flat torus is equivalent to a reciprocal/Delaunay graph on some flat torus. These results appeared in SoCG '20

July 9:

  
  ICERM Workshop

July 16:

 Slides   Video arXiv
  Speaker: Daniel Irving Bernstein (Massachusetts Institute of Technology)
  Title: Generic symmetry-forced infinitesimal rigidity: translations and rotations
  Abstract: Bar and joint frameworks appearing in certain applications (particularly crystallography) are often constrained to have particular symmetries. This motivates the study of symmetric frameworks whose allowable flexes preserve the symmetry. Just as non-symmetric frameworks are represented using graphs, symmetric frameworks are represented using gain graphs, i.e. directed graphs whose arcs are labeled by elements of a group. The main result of this talk is a Laman-like characterization of the gain graphs that are generically infinitesimally symmetry-forced rigid in the plane when the symmetry group consists of translations and rotations.

July 23:

 Slides   Video arXiv
  Speaker: Ryoshun Oba (University of Tokyo)
  Title: Characterizing the Universal Rigidity of Generic Tensegrities
  Abstract: A tensegrity is a structure made from cables, struts and stiff bars. A d-dimensional tensegirty is universally rigid if it is rigid in any dimension d′ with d′≥d. The celebrated super stability condition due to Connelly gives a sufficient condition for a tensegrity to be universally rigid. Gortler and Thurston showed that super stability characterizes universal rigidity when the point configuration is generic and every member is a stiff bar. We extend this result in two directions. We first show that a generic universally rigid tensegrity is super stable. We then extend it to tensegrities with point group symmetry, and show that this characterization still holds as long as a tensegrity is generic modulo symmetry. Our strategy is based on the block-diagonalization technique for symmetric semidefinite programming problems, and our proof relies on the theory of real irreducible representation of finite groups.