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.

Online talk: Tony Huynh (CMSA Seminar)

Next week, Tony Huynh is giving a talk in the Combinatorial Mathematics Society of Australasia Seminar which many of our readers may be interested in. Here is the info. The announcement for next week’s Graphs and Matroids talk will follow soon.

Tuesday, October 6, 9pm ET (11am AEST)
Tony Huynh, Monash U
Idealness of k-wise intersecting families
Zoom/password: see CMSA website

 

Abstract:
A clutter is a hypergraph such that no hyperedge is contained in another hyperedge. It is $k$-wise intersecting if every $k$ hyperedges intersect, but there is no vertex contained in all the hyperedges. We conjecture that every $4$-wise intersecting clutter is not ideal. Idealness is an important geometric property, which roughly says that the minimum covering problem for the clutter can be efficiently solved by a linear program. As evidence for our conjecture, we prove it for the class of binary clutters. Our proof combines ideas from the theory of clutters, graphs, and matroids. For example, it uses Jaeger’s $8$-flow theorem for graphs, and Seymour’s characterization of the binary matroids with the sums of circuits property. We also show that $4$ cannot be replaced by $3$ in our conjecture, where the counterexample of course comes from the Petersen Graph.


This is joint work with Ahmad Abdi, Gérard Cornuéjols, and Dabeen Lee.

Online talk: Dan Cranston

Monday, September 28, 3pm ET (8pm BST, 7am Tue NZST)
Dan Cranston, Virginia Commonwealth U
Vertex Partitions into an Independent Set and a Forest with Each Component Small
Youtube

 

Abstract:
For each integer $k \ge 2$, we determine a sharp bound on $\text{mad}(G)$ such that $V(G)$ can be partitioned into sets $I$ and $F_k$, where $I$ is an independent set and $G[F_k]$ is a forest in which each component has at most $k$ vertices. For each $k$ we construct an infinite family of examples showing our result is best possible. Hendrey, Norin, and Wood asked for the largest function $g(a,b)$ such that if $\text{mad}(G)<g(a,b)$ then $V(G)$ has a partition into sets $A$ and $B$ such that $\text{mad}(G[A])<a$ and $\text{mad}(G[B])<b$. They specifically asked for the value of $g(1,b)$, which corresponds to the case that $A$ is an independent set. Previously, the only values known were $g(1,4/3)$ and $g(1,2)$. We find the value of $g(1,b)$ whenever $4/3<b<2$. This is joint work with Matthew Yancey.

Online talk: Alexey Pokrovskiy (non-standard day & time!)

We’re really excited to have Alexey Pokrovskiy speak on his fantastic recent result on Rota’s Basis Conjecture this upcoming week. This talk has been moved to be a part of the Tutte Colloquium at Waterloo and so will be held at a different day and time than usual. Here are the full details.

Friday, September 25, 1pm ET (6pm BST, 5am Tue NZST)
Alexey Pokrovskiy, Birkbeck, University of London
Rota’s Basis Conjecture holds asymptotically
Youtube

 

Abstract:
Rota’s Basis Conjecture is a well known problem, that states that for any collection of $n$ bases in a rank $n$ matroid, it is possible to decompose all the elements into $n$ disjoint rainbow bases. Here an asymptotic version of this is will be discussed – that it is possible to find $n – o(n)$ disjoint rainbow independent sets of size $n – o(n)$.