Monday, November 2, 3pm ET (8pm GMT, 9am Tue NZDT)
Attila Joó, University of Hamburg
The Matroid Intersection Conjecture of Nash-Williams

YouTube

Abstract:

Rado initiated a program in the 1960s  to find the “right” infinite generalization of the matroid concept. The results of Higgs and Oxley and more recently Bruhn et al. led eventually to a positive answer for Rado’s question.  One of the most important open problems in the theory of infinite matroids is the Matroid Intersection Conjecture of Nash-Williams which is a structural infinite generalization of the well-known Intersection Theorem of Edmonds. It says that if $M$ and $N$ are (finitary) matroids on the common edge set $E$, then they admit a common independent set $I$ that has a bipartition $I=I_M \cup I_N$ with $cl_M(I_M) \cup cl_N(I_N)=E$. The restriction of the conjecture to partition matroids (known as ‘König’s Theorem for infinite bipartite graphs’) was proven by Aharoni, Nash-Williams and Shelah and is a deep result in infinite matching theory. In the main part of the talk we give a proof overview of our partial result which decides affirmatively the conjecture whenever $E$ is countable. Finally we reveal an unpublished conjecture of Aharoni about the intersection of more than two matroids which is wide open even for three finite matroids.

Monday, October 26, 3pm ET (8pm BST, 8am Tue NZDT)
Rose McCarty, University of Waterloo
Colouring pseudo-visibility graphs
Youtube

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.

Monday, October 19, 3pm ET (8pm BST, 8am Tue NZDT)
Erik Panzer, Oxford
The Hepp bound of a matroid: flags, volumes and integrals

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.

Since next Monday is Thanksgiving in Canada, we’re moving the online talk for next week to a later week. The Talks page has been updated. See you on the 19th for Erik Panzer’s talk: “The Hepp bound of a matroid: flags, volumes and integrals”.