Monthly Archives: April 2021

Online talk: Daniel Bernstein

Posted on by
Reply

Monday, April 19, 3pm ET (8pm BST, 7am Tue NZST)
Daniel Bernstein, MIT
Rigidity of symmetry-forced frameworks

 
Abstract:

The fundamental problem in rigidity theory is to determine whether a given immersion of a graph into $\mathbb{R}^d$ can be continuously deformed, treating the edges as rigid bars that can move freely about their incident vertices. Rigidity is a generic property of each fixed graph $G$, in the sense that almost all immersions of $G$ into $\mathbb{R}^d$ are rigid, or almost all immersions are flexible. The graphs that are generically rigid in $\mathbb{R}^d$ are the spanning sets of a certain matroid. The main result of my talk will be about rigidity in the plane when the graphs and their immersions have certain symmetry constraints.

Online talk: Daryl Funk

Posted on by
Reply

Monday, April 12, 3pm ET (8pm BST, 7am Tue NZST)
Daryl Funk, Douglas College
The class of bicircular matroids has only a finite number of excluded minors

 
Abstract:

We show that the class of bicircular matroids has only a finite number of excluded minors. Key tools used in our proof include representations of matroids by biased graphs and the recently introduced class of quasi-graphic matroids. We show that if $N$ is an excluded minor of rank at least eight, then $N$ is quasi-graphic. Several small excluded minors are quasi-graphic. Using biased-graphic representations, we find that $N$ already contains one of these. We also provide an upper bound, in terms of rank, on the number of elements in an excluded minor, so the result follows.

Online talk: Raphael Steiner

Posted on by
Reply

Monday, April 5, 3pm ET (8pm BST, 7am Tue NZST)
Raphael Steiner, TU Berlin
Directed graphs: Substructures and Coloring

Slides: click here
 
Abstract:

Two popular topics that are classically studied in graph theory are (A) substructures of “dense” graphs and (B) substructures of graphs with large chromatic number. Well-known notions of “substructure” used in this context are (induced) subgraphs, minors, and subdivisions. Unfortunately, interesting generalizations of these concepts to the directed setting, despite being very natural, have received considerably less attentation. In this talk, I want to popularize this topic by surveying some intriguing open problems and known partial results (some of my own) related to the following questions.

(A) Which substructures can be found in digraphs that are very dense? (Meaning that they have large minimum out- and/or in-degree).

(B) Which substructures can be found in digraphs whose dichromatic number is large? (Dichromatic number being an established extension of the chromatic number to directed graphs).