Convex geometry has played a role in matroid theory for at least fifty years, while toric and tropical geometry have been more recent contributors. Results over the last decade have highlighted the power of various geometric or geometrically inspired techniques in matroid theory. I will survey some recent progress in this direction, with the aim of strengthening connections with other aspects...
We know the excluded minors for the matroids representable over GF(2), GF(3) and GF(4). What are the chances of explicitly finding the excluded minors for matroids representable over GF(5)?
We have an excellent understanding of the classes that arise when we consider matroids representable over GF(2) and other fields. We also have an algebraic understanding of the classes that arise for...
A matroid is regular if it is representable over every field. Characterisations of regular matroids are known (Tutte, 1958) in terms of excluded minors, having a totally unimodular representation, and representability over GF(2) and some field of characteristic not two. A matroid is near-regular if it is representable over every field of size at least three. Characterisations of near-regular...
Matroids introduced by H. Whitney abstract some properties of linear independence among vectors in a vector space over a field. Nevertheless, it is well-known that almost all matroids are non-representable as a set of vectors over a field. It is one of the most significant problems to determine whether a given matroid is representable over some field. In this talk, we propose some...
Rota's famous conjecture for representable matroids says that when F is a finite field, there are only finitely many minimal obstructions for the class of matroids that are linearly-representable using vectors with F as the field of scalars. A proof has been announced by Geelen, Gerards, and Whittle.
Gain-graphic matroids are analogues to matroids represented by vectors: instead of...
A graph matroid family $\mathcal{M}$ is a family of matroids $\mathcal{M}(G)$ defined on the edge set of each finite graph $G$ in a compatible and isomorphism-invariant way. We say that $\mathcal{M}$ has the Whitney property if there is a constant $c$ such that every $c$-connected graph $G$ is uniquely determined by $\mathcal{M}(G)$. Similarly, $\mathcal{M}$ has the *Lovász-Yemini...
There are at least two well-studied ways to extend matroids to more general objects - one can allow the ground set to be infinite, or instead define the concept of independence on a lattice other than a set lattice. I will give several cryptomorphic definitions of an object that generalizes a matroid in both these ways at once, and argue that they are (in some ways) nicer than the usual finite...
The goal of the talk is to introduce the theory of unbounded matroids. These are possibly unbounded Polyhedra in R^d whose vertices are 01 whose edge directions are of the form $e_i - e_j$. We will explore some cryptomorphic variations of these definitions involving linear extensions of posets and relate them to matroids and polymatroids. We will discuss how these objects can be used to study...
Tropical ideals are combinatorial objects introduced with the aim of giving tropical geometry a solid algebraic foundation. They can be thought of as combinatorial generalizations of the possible collections of subsets arising as the supports of all polynomials in an ideal of the polynomial ring. In general, the structure of tropical ideals is dictated by a sequence of 'compatible' matroids....
We discuss the interplay between certain properties of pairs of matroids and intersection theory of their Bergman fans, which has been extensively studied during the last decade. This provides another connection between tropical algebraic geometry and combinatorics of matroids.
In the first part of the talk, we formulate the theorem claiming that the proper amalgam of two matroids $M_1$ and...
In 2009, looking to bound the face vectors of matroid subdivisions and tropical linear spaces, Speyer introduced the g-invariant of a matroid. He proved its coefficients nonnegative for matroids representable in characteristic zero and conjectured this in general. Later, Shaw and Speyer and I reduced the question to positivity of the top coefficient. In work in progress with Berget, we prove...
In this talk, we discuss the tropicalization of the space of symmetric rank two matrices. Analogous to the result of Markwig and Yu for general tropical rank two matrices, it has a simplicial complex structure as the space of symmetric bicolored trees. As properties of this simplicial complex, we point out that this space is shellable and give several descriptions of the algebraic matroid of...
Baker and Bowler (2019) showed that the Grassmannian can be defined over a tract, a field-like structure generalizing both partial fields and hyperfields.
This notion unifies theories for matroids over partial fields, valuated matroids, and oriented matroids.
We extend Baker-Bowler theory to the Lagrangian Grassmannian which is the set of maximal isotropic subspaces in a $2n$-dimensional...
q-Matroids, the q-analogue of matroids, have been intensively invest-
igated in recent years in coding theory due to their close connection with rank metric codes. Indeed, in 2018 it was shown by Jurrius and Pellikaan that a rank metric code induces a q-matroid that captures many of the code’s invariants. In this talk we will deal with the direct sum of q-matroids, a concept recently...
The $q$-analoge of a combinatorial object arises by replacing finite sets with finite dimensional vector spaces. In particular we can view $q$-matroids as $q$-analogues of matroids. One motivation to study $q$-matroids stems from coding theory, as the representable $q$-matroids arise from rank-metric codes. In the matroidal setting Peter Nelson proved in 2018 that asymptotically almost all...
A Steiner system is characterized with the subsets (called blocks) satisfying that all $t$-subsets are included in exactly one block. A perfect matroid design (PMD) is a matroid whose flats of the same rank have the same size. Recently, E. Byrne et. al. proposed a $q$-analogue of PMDs (namely $q$-PMDs) and constructed a non-trivial $q$-PMD from a $q$-analogue of a Steiner system. In this...
In recent years, q-polymatroids have drawn interest because of their connection with rank-metric codes. For a special class of q-polymatroids called q-matroids, the fundamental notion of a cyclic flat has been developed as a way to identify the key structural features of a q-matroid. In this talk, we will see a generalisation of the definition of a cyclic flat that can apply to q-polymatroids,...
By ``cutting out'' the edges and vertices of a graph cellularly embedded in a surface, we obtain a ribbon graph. A partial Petrial is obtained from a ribbon graph by selecting a subset of the ribbon edges adding a half-twist to each. Delta-matroids generalize ribbon graphs similarly to the way that matroids generalize graphs. The ribbon graph partial Petrial is the analogue of a more...
Critical groups are groups associated with graphs. They are well-established in combinatorics; closely related to the graph Laplacian and arising in several contexts such as chip firing and parking functions. The critical group of a graph is finite and Abelian, and its order is the number of spanning trees in the graph, a fact equivalent to Kirchhoff’s Matrix--Tree Theorem.
What happens if...
Given $\ell$ and $t$ positive integers, we will give a singly exponential bound on the number of points a $U_{2,\ell}$-minor-free matroid with can have without containing $M(K_t)$ as a minor.
In 1961, Dirac showed that chordal graphs are exactly the graphs that can be constructed from complete graphs by a sequence of clique-sums. By analogy with Dirac's result, we define the class of $GF(q)$-chordal matroids as those matroids that can be constructed from projective geometries over $GF(q)$ by a sequence of generalized parallel connections across projective geometries over $GF(q)$....
We prove that, for any integer $k$, there are only finitely many excluded minors for the class of matroids of path-width $k$. This result is obtained as a consequence of a well-quasi-ordering result on connectivty systems of bounded path-width. This is joint work with Rutger Campbell.
In 1941, Melchior proved that the average size of a line in a simple rank-3 real-representable matroid is less than three. A similar theorem for the complex-representable matroids was proved by Hirzebruch in 1983. In this talk, we discuss the problem of extending these results to flats of higher rank. We show that, in every simple rank-4 real-representable matroid which is not the direct sum...
Building sets were introduced in the study of wonderful compactifications
of hyperplane arrangement complements and were later generalized to finite meet-
semilattices. Convex geometries, the duals of antimatroids, offer a robust combinatorial
abstraction of convexity. Supersolvable convex geometries and antimatroids appear in
the study of poset closure operators, Coxeter groups, and...
Boundary algebras are an important tool in the categorification, by Jensen--King--Su and by Pressland, of cluster structures on positroid varieties, defined by Scott and by Galashin--Lam. Each connected positroid has a corresponding boundary algebra. We give a combinatorial description of the set of algebras which arise as the boundary algebra of some positroid. Using this combinatorial...
A sequence of nonnegative real numbers $a_1, a_2, \ldots, a_n$, is log-concave if $a_i^2 \geq a_{i-1}a_{i+1}$ for all $i$ ranging from 2 to $n-1$. Log-concavity naturally arises in various aspects of mathematics, each characterized by different underlying mechanisms. Examples range from inequalities that are readily provable, such as the binomial coefficients $a_i = {n\choose i}$, to intricate...
Chow rings and augmented Chow rings of matroids were considered and played important roles in the settlement of the Heron-Rota-Welsh conjecture and the Dowling-Wilson top-heavy conjecture. Their Hilbert series have been extensively studied since then. It was shown by Ferroni, Mathern, Steven, and Vecchi, and indepedently by Wang, that the Hilbert series of Chow rings of matroids are γ-positive...
The Chow ring of the graphical matroid of the complete graph with n-1 vertices (with respect to the minimal building set) is isomorphic to that of the moduli space of n-pointed rational curves. Therefore, it is naturally a graded representation of the n-th symmetric group.
In this talk, we provide a closed-form formula for this representation, in terms of weighted rooted trees, which we...
We’ll discuss the gamma vector, which is an invariant of (reciprocal) polynomials whose positivity lies somewhere between unimodality and real-rootedness. It shows up in many seemingly unrelated contexts including permutation statistics, signs of Euler characteristics vs. curvatures of (piecewise Euclidean) manifolds, and Chow rings of matroids. Before asking about positivity, a natural...
We use two dual Lawrence polytopes $P$ and $P^*$ of a graph $G$ to study the graph. The $h$-vector of the graphic (resp. cographic) matroid complex associated to $G$ coincides with the $h^*$-vector of the Lawrence polytope $P$ (resp. $P^*$). In general, the $h$-vector is an invariant defined for an abstract simplicial complex, which encodes the number of faces of different dimensions. The...
A binary function is a function $f:2^E\rightarrow\mathbb{C}$ for which $f(\emptyset)=1$, where $E$ is a finite ground set. Binary functions are closely related to quantum registers. They generalise binary matroids in the sense that any indicator function of a linear space over GF(2) is a $\{0,1\}$-valued binary function (using the natural correspondence between subsets of $E$ and their...
Surprisingly many interesting invariants of graphs, hyperplane arrangments and matroids are valuative. The two most prominent examples of valuative matroid invariants are the Tutte polynomial and the $\mathcal{G}$-invariant. The relevance of the $\mathcal{G}$-invariant steams from its universal property that any other valuative invariant can be obtained as a specialization. Nevertheless, the...
A valuation of a matroid $M$ with set of bases $\mathcal{B}$ is a function $\nu:\mathcal{B}\rightarrow\mathbb{R}$ so that
- (V) for all $B, B'\in \mathcal{B}$ and all $e\in B\setminus B'$ there exists an $f\in B'\setminus B$ such that
$ \nu(B)+\nu(B')\geq \nu(B-e+f)+\nu(B'+e-f).$
The Dressian $\mathcal{D}(M)$ is defined as the set of all valuations of $M$. The Dressian of $M$...
Oriented matroids are matroids with extra sign data, and they are useful in the tropical study of real algebraic geometry. In order to study the topology of real algebraic/tropical hypersurfaces constructed from patchworking, Renaudineau and Shaw introduced an algebraically defined filtration of the tope spaces of oriented matroids (for a real hyperplane arrangement, the tope space is the...
It is well known that the class of transversal matroids is not closed under contraction or duality. The complexity of deciding whether a minor or dual of a transversal matroid remains transversal is in $\Sigma_2$ and thus far there has been no improvement on this bound. We explore this issue, providing a polynomial time algorithm for determining whether a single element contraction of a...
Tutte showed that wheels and whirls are precisely the 3-connected matroids in which every element is contained in a 3-element circuit and a 3-element cocircuit. In fact, wheels and whirls have the stronger property that there is a circular ordering of their ground set such that every two consecutive elements are contained in a 3-element circuit and a 3-element cocircuit. In this talk, we...
A matroid is frame if it may be extended such that it possesses a basis $B$ (a frame) such that every element is spanned by at most two elements of $B$. This gives frame matroids natural graphical representations as biased graphs.
We characterise the inequivalent graphical representations of 3-connected frame matroids that have a fixed element $\ell$ in their frame $B$. One consequence is a...
Quasi-graphic matroids provide a common generalisation of frame and lifted graphic matroids, with better algorithmic properties. We explain how to efficiently construct a framework for a quasi-graphic matroid given a schema for dividing that framework into pieces, each of which is graphic. This is joint work with James Davies, Daryl Funk, Jim Geelen and Peter Nelson.
A $2$-dimensional framework $(G,p)$ is an embedding of a graph $G=(V,E)$ into $2$-dimensional space, such that each vertex $v$ is assigned a pair of coordinates $p(v) = (x_v,y_v)\in\mathbb{R}^2$. A framework is rigid if the only motions of the vertices in the plane that preserve all edge lengths are isometries of the plane. It is well-known (since at least the 1920s) that when the set of...
An induced packing of cycles in a graph is a set of vertex-disjoint cycles with no edges between them. We generalise the classic Erdős-Pósa theorem to induced packings of cycles. More specifically, we show that there exists a function ${f(k) = \mathcal{O}(k \log k)}$ such that for every positive integer ${k}$, every graph $G$ contains either an induced packing of $k$ cycles or a set $X$ of at...
Let $D$ be a directed graphs with distinguished sets of sources $S\subseteq V(D)$ and sinks $T\subseteq V(D)$.
A tripod in $D$ is a subgraph consisting of the union of two $S$-$T$-paths that have distinct start-vertices and the same end-vertex, and are disjoint apart from sharing a suffix.
This talk presents a proof that tripods in directed graphs exhibit the Erdős-Pósa property.
More...
In recent years, combinatorial reconfiguration problems have attracted great attention due to their connection to various topics such as optimization, counting, enumeration, or sampling. One of the most intriguing open questions concerns the exchange distance of two matroid basis sequences, a problem that appears in several areas of computer science and mathematics. White (1980) proposed a...
Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a...
