Online talk: Rose McCarty

Monday, October 26, 3pm ET (8pm BST, 8am Tue NZDT)
Rose McCarty, University of Waterloo
Colouring pseudo-visibility graphs
Zoom:
[Email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password]
 
 
Abstract:

The visibility graph of a finite set of points $S$ on a Jordan curve $\mathcal{J}$ has vertex set $S$, and two points in $S$ are adjacent if the (open) segment between them is contained in the interior of $\mathcal{J}$. To obtain a pseudo-visibility graph, we instead start with a pseudolinear drawing of the complete graph with vertex set $S$ on $\mathcal{J}$. We show that any pseudo-visibility graph with clique number $\omega$ is $\left(3\cdot 4^{\omega-1}\right)$-colourable. This talk will also focus on connections between 1) developing efficient algorithms for recognizing these graphs and 2) constructing uniform, rank-$3$ oriented matroids which represent the pseudolinear drawing.

This is joint work with James Davies, Tomasz Krawczyk, and Bartosz Walczak.

Online talk: Erik Panzer

Monday, October 19, 3pm ET (8pm BST, 8am Tue NZDT)
Erik Panzer, Oxford
The Hepp bound of a matroid: flags, volumes and integrals
Zoom:
[Email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password]
 
 
Abstract:

Invariants of combinatorial structures can be very useful tools that capture some specific characteristics, and repackage them in a meaningful way. For example, the famous Tutte polynomial of a matroid or graph tracks the rank statistics of its submatroids, which has many applications, and relations like contraction-deletion establish a very close connection between the algebraic structure of the invariant (e.g. Tutte polynomials) and the actual matroid itself.

I will present an invariant, called the Hepp bound, that associates to a matroid a rational function in many variables (one variable for each element of the matroid). This invariant behaves nicely with respect to duality and 2-sums, and the residues at its poles factorize into the Hepp bounds of sub- and quotient matroids. It can be specialized to Crapo’s beta invariant and it is also related to Derksen’s invariant. The construction is motivated by the tropicalization of Feynman integrals from the quantum field theory of elementary particles physics. In the case of graphs, the Hepp bound therefore obeys further interesting relations that are known for Feynman integrals.

Due to this rich structure, the Hepp bound can be viewed from several distinct perspectives, each making certain properties emerge more directly than others. I will sketch 3 definitions:
1) enumerative – as a certain sum over flags of submatroids,
2) analytic – as an integral,
3) geometric – as a volume of a polytope.

Online talk: Lorenzo Traldi

Monday, October 5, 3pm ET (8pm BST, 8am Tue NZDT)
Lorenzo Traldi, Lafayette College
Isotropic matroids and circle graphs
Zoom:
[Email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password]
 
 
Abstract:

Let $A=A(G)$ be the adjacency matrix of a simple graph $G$, considered as a matrix with entries in $GF(2)$. The binary matroid represented by the partitioned matrix $IAS(G)=\begin{pmatrix} I & A & A+I \end{pmatrix}$ is the isotropic matroid of $G$, denoted $M[IAS(G)]$. ($I$ is the identity matrix.) The matroid has three elements corresponding to each vertex of $G$.

Isotropic matroids have many interesting properties. One is the fact that two graphs are locally equivalent (up to isomorphism) if and only if their isotropic matroids are isomorphic. A special case underscores the difference between isotropic matroids and cycle matroids: two forests are isomorphic if and only if their isotropic matroids are isomorphic.

Another interesting property is that the isotropic matroid of $G$ contains two other kinds of structures associated with $G$, the delta-matroid and the isotropic system. Isotropic matroids allow us to use binary matroids to study the delta-matroids and isotropic systems of graphs.

After discussing these general properties, I’ll talk about joint work with Robert Brijder involving isotropic matroids of circle graphs. A circle graph $G$ is defined from an Euler circuit in a 4-regular graph $F$, and it turns out that in this case there is a precise relationship between the ranks of transversals in $M[IAS(G)]$ — a transversal is a subset that contains precisely one of the three matroid elements for each vertex — and the sizes of circuit partitions in $F$. This relationship is encoded in the often rediscovered circuit-nullity formula, which will celebrate the centennial of its first discovery next year (if it has not done so already). There are many different ways to characterize circle graphs using their isotropic matroids. The most striking of these characterizations is a multimatroid analogue of regularity: $G$ is a circle graph if and only if the ranks of the transversals of $M[IAS(G)]$ can be duplicated within a matroid representable over a field of characteristic other than 2.