Representability of Flag Matroids

Daniel Irving Bernstein, Nathaniel Vaduthala · 2025

Read Representability of Flag Matroids by Daniel Irving Bernstein, Nathaniel Vaduthala (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-00267.txt.

Introduction

Daniel Irving Bernstein and Nathaniel Vaduthala study flag matroids, layered structures built from matroids of rising rank, in a paper published in two thousand twenty-five. Their central question is which of these structures can be written with numbers from a given field.

They give a new axiom system that defines flag matroids from scratch. For uniform flag matroids, they pin down exactly when a numeric form exists. For full flag matroids, they list the blocked smaller patterns that rule out a form over the two-element and three-element fields. They also treat the regular case in several matching ways. The results sort out which of these layered structures algebra can actually build.

Catalog record

CREATORDaniel Irving Bernstein, Nathaniel Vaduthala
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-00267

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Representability of Flag Matroids Daniel Irving Bernstein, Nathaniel Vaduthala Abstract We provide a new axiom system for flag matroids, characterize representability of uniform flag matroids, and give forbidden minor characterizations of full flag matroids that are representable over 𝔽 2 \mathbb{F}_{2} and 𝔽 3 \mathbb{F}_{3} along with regular full flag matroids. We also provide different equivalent characterizations for regular full flag matroids. 1 Introduction Matroids were introduced in the 1930s as a combinatorial abstraction of the notion of linear independence in vector spaces. Their conception is often attributed to a 1935 paper of Whitney [ 29 ] but they were also contemporaneously developed by Nakasawa [ 27 ] . Since then, matroid theory has developed into a rich area of combinatorics with deep relevance in many seemingly unrelated areas ranging from optimization to algebraic geometry. Much research within matroid theory has been motivated by the search for elegant combinatorial descriptions of graphic and representable matroids. In broad terms, the goal of this paper is to expand that line of research into a generalization called flag matroids . Just as a matroid is a combinatorial abstraction of a linear subspace of a vector space, a flag matroid is a combinatorial abstraction of a sequence of nested linear subspaces of a vector space. Flag matroids are typically defined to be a sequence of matroids on the same ground set satisfying a particular compatibility condition. They also have other equivalent cryptomorphic definitions [ 6 ] . Our first contribution is a new cryptomorphic axiom system for flag matroids in terms of what we call feasible sets , borrowing terminology and ideas from the theory of greedoids. We then characterize representability for uniform flag matroids, and give forbidden-minor classifications for full flag matroids that are \mathbb{F}_{2} -representable, \mathbb{F}_{3} -representable, and regular. We then provide equivalent characterizations for regular full flag matroids. Flag matroids were first studied in the 1960s and 70s as sequences of strong maps in [ 20 , 22 , 10 , 25 ] . They have connections to the K-theory of flag varieties [ 9 , 13 , 21 ] and have a rich interplay with other combinatorial structures [ 12 , 2 , 1 , 14 ] . Gaussian elimination greedoids , also called Gauss greedoids , are a class of flag matroids that have been studied in the greedoid theory literature [ 23 ] and were recently shown [ 18 , 19 ] to have relevance to Barghava’s theory of P-orderings [ 5 ] . A matroid lift is a particular kind of flag matroid that is of fundamental importance in matroid theory itself (see e.g. [ 28 , Chapter 7] ) and has recently been used to study matroid representability [ 4 ] and rigidity theory [ 3 , 11 ] . The paper is organized as follows. Section 2 covers the necessary matroid theory background. Section 3 begins with some background on flag matroids. We then provide a new cryptomorphic axiom system for flag matroids in Definition 3.4 that can be seen as a simultaneous generalization of the independent set, basis, and spanning set axioms of a matroid (see Remark 3.7 ). We characterize the fields that each uniform flag matroid is representable over in Theorem 3.10 . We review minors and duality for flag matroids and describe how these concepts manifest in our new axiom system. It was shown in [ 24 ] that to every flag matroid, one can associate a certain matroid called a major that encodes the flag matroid in certain minors. We recall this theory of majors, and show in Theorems 3.23 and 3.24 that a flag matroid is graphic/ \mathbb{K} -representable if and only if it has a major which is as well. The main results of Section 4 are Theorem 4.10 , which gives excluded minor characterizations of \mathbb{F}_{2} - and \mathbb{F}_{3} -representable full flag matroids, and Theorem 4.17 , which gives excluded minor characterizations of regular full flag matroids. 2 Matroid theory background We begin with the minimal necessary background on matroid theory; for a more leisurely and comprehensive introduction, see [ 28 ] . Definition 2.1 . A matroid is a pair M=(E,\mathcal{I}) , consisting of a finite set E and a collection \mathcal{I} of subsets of E satisfying 1. \emptyset\in\mathcal{I} 2. for each I^{\prime}\subseteq I , if I\in\mathcal{I} , then I^{\prime}\in\mathcal{I} . 3. for all I,J\in\mathcal{I} such that |J|>|I| , there exists some j\in J\setminus I such that I\cup\{j\}\in\mathcal{I} . Here E is called the ground set and elements of \mathcal{I} are called independent sets . Definitions 2.2 and 2.3 below each give a family of matroids. Definition 2.2 . Let 0\leq r\leq n be integers, let E be a set of size n and let \mathcal{I} consist of all subsets of E of cardinality r or less. Then (E,\mathcal{I}) is a matroid, denoted U_{r,n} . Matroids of the form U_{r,n} are called uniform . Definition 2.3 . Let \mathbb{K} be a field and let A be a matrix with entries in \mathbb{K} . If E is (a set in natural bijection with) the column set of A and \mathcal{I} denotes the subsets of E that are linearly independent, then (E,\mathcal{I}) is a matroid which we denote M(A) . Matroids arising in this way are called \mathbb{K} -representable and a matrix A such that M=M(A) is called a \mathbb{K} -representation of M . We now give two examples illustrating Definitions 2.2 and 2.3 . Example 2.4 . Let \mathbb{K} be a field with at least three elements and let x\in\mathbb{K}\setminus\{0,1\} . Then the following is a \mathbb{K} -representation of U_{2,4} \begin{pmatrix}0&1&1&1\\ 1&0&1&x\end{pmatrix}. Thus U_{2,4} is \mathbb{K} -representable whenever \mathbb{K} has three or more elements. For each prime power q , the field with q elements will be denoted \mathbb{F}_{q} . It is relatively straightforward to show that U_{2,4} is not representable over \mathbb{F}_{2} . Example 2.5 . Consider the following matrix with entries in \mathbb{F}_{2} A=\begin{pmatrix}1&1&1&1&0&0&0\\ 1&1&0&0&1&1&0\\ 1&0&1&0&1&0&1\end{pmatrix}\in\mathbb{F}_{2}^{3\times 7}. The matroid M(A) , often called the Fano matroid and denoted F_{7} , is representable over \mathbb{K} if and only if the characteristic of \mathbb{K} is two [ 28 , Proposition 6.4.8] . We now describe an alternative view of representable matroids. Let \mathbb{K} be a field and let V be a finite dimensional \mathbb{K} -vector space with basis E . For each linear subspace L\subseteq V , let \mathcal{I} denote the subsets I\subseteq E such that the orthogonal projection of L onto the linear space spanned by I has dimension |I| . Then (E,\mathcal{I}) is a matroid which we denote M(L) . Matroids arising in this way are exactly the \mathbb{K} -representable matroids - if A is any matrix whose rows represent a spanning set of L in the basis E , then M(A)=M(L) . The last family of examples of matroids we need to introduce come from graphs. The graph with vertex set V and edge set E will be denoted (V,E) . Definition 2.6 . Let G=(V,E) be a graph with loops and multiple edges allowed, and consider the family \mathcal{I} of subsets of E defined as follows \mathcal{I}:=\{I\subseteq E:(V,I){\rm\ has\ no\ cycles}\}. Then (E,\mathcal{I}) is a matroid, denoted M(G) . If M is a

Read the complete text