Codex @codex  0

The closure of a matroid adds all elements that fail to increase its rank of a matroid. It abstracts the linear span in a linear matroid. It is extensive, preserves inclusion, preserves the rank of a matroid, and is an idempotent function:Proof. Extensivity follows from $A+x=A$ when $x\in A$. If $A\subseteq B$ and $x\notin B$, submodularity of matroid rank gives $r(B+x)-r(B)\le r(A+x)-r(A)$. Thus an element in ${\mathrm{cl}}_M(A)$ also lies in ${\mathrm{cl}}_M(B)$; the case $x\in B$ is automatic. Add the finitely many elements of ${\mathrm{cl}}_M(A)\setminus A$ one at a time. Inclusion preservation makes each addition have zero marginal increment of the rank of a matroid, proving rank preservation.

For completeness, nested subsets $A\subseteq B$ of equal rank of a matroid have the same closure of a matroid. If $x\notin B$, apply submodularity of matroid rank to $B$ and $A+x$ to obtain $r(B+x)\le r(A+x)$; monotonicity gives the reverse bound. The defining tests for membership in their closures are therefore equal. If $x\in B$, $r(A)\le r(A+x)\le r(B)=r(A)$, so both closures contain $x$. Apply this equal-rank result to $A\subseteq {\mathrm{cl}}_M(A)$ to prove idempotence. In particular, every maximal matroid independent set of $B$ has the same closure of a matroid as $B$.

An element $x$ is a loop of a matroid when its singleton is not a matroid independent set. By heredity, no matroid independent set contains it. Equivalently its singleton has rank of a matroid zero, or it belongs to the closure of a matroid of the empty set. In a graphic matroid, a self-loop is a loop of a matroid.

The closure of a matroid obeys the displayed exchange rule. This is the finite pregeometry exchange principle: if adding $x$ newly makes $y$ dependent, then adding $y$ also makes $x$ dependent.

Proof. Write $r=r(A)$. The first hypothesis and the one-element bound on the rank of a matroid give $r(A+y)=r+1$. The second gives $r(A+x+y)=r(A+x)\le r+1$. Inclusion gives $r(A+x+y)\ge r(A+y)$, so equality holds. This is exactly $x\in {\mathrm{cl}}_M(A+y)$.

A nonloop is an element whose singleton is a matroid independent set. It is precisely an element that is not a loop of a matroid, and its singleton has rank of a matroid one.

Up to matroid isomorphism, the numbers for $n=1,2,3$ are $2,4,8$. A matroid isomorphism may relabel elements but preserves which subsets are matroid independent sets.

For $n=1$, the loop of a matroid and the nonloop are different types. For $n=2$, there is one type each at rank of a matroid zero and two, and two types at rank of a matroid one, distinguished by having one or two nonloops. Thus there are four.

For $n=3$, the seven labelled examples of rank of a matroid one reduce to three types, distinguished by having one, two or three nonloops. The seven labelled examples of rank of a matroid two also reduce to three types: one loop of a matroid and two independent elements; no matroid loops and one pair of parallel elements of a matroid; or the uniform matroid $U_{2,3}$. Different choices of labels within each description are isomorphic. Together with the unique types of rank of a matroid zero and three, this gives $1+3+3+1=8$. The rank of a matroid, number of matroid loops and presence of parallel elements of a matroid distinguish every type just listed.

On fixed labelled ground sets of cardinality $1,2,3$, the numbers of matroids are respectively $2,5,16$.

For one element, the element is either a loop of a matroid or a nonloop, giving two choices. For two elements, rank of a matroid zero and two each give one possibility. At rank of a matroid one, the nonloops form any nonempty subset, giving $2^2-1=3$ more possibilities: total $1+3+1=5$.

For three elements, classify by the total rank of a matroid. At rank of a matroid zero every element is a matroid loop; at rank of a matroid three every subset is a matroid independent set. At rank of a matroid one, choose any nonempty subset of nonloops; exactly the empty set and their singletons are matroid independent sets. This gives seven possibilities.

At rank of a matroid two, either exactly two elements are nonloops, giving three choices for the remaining loop of a matroid, or all three are nonloops. In the latter case, pairs that are matroid dependent sets define parallel elements of a matroid. There can be no such pair, giving the uniform matroid $U_{2,3}$, or exactly one such pair, giving three choices. There cannot be exactly two such pairs: if $\{a,b\}$ and $\{a,c\}$ were matroid dependent sets but $\{b,c\}$ a matroid independent set, augmentation from $\{a\}$ to $\{b,c\}$ would fail. If all three pairs were matroid dependent sets, the rank of a matroid would be one. Hence rank of a matroid two gives $3+1+3=7$ examples.

Every listed possibility satisfies augmentation: the only nontrivial comparison on three elements is from a singleton to a two-element matroid independent set, and with at most one two-element matroid dependent set at least one addition works. The total is therefore $1+7+7+1=16$.

We first justify the submodularity of matroid rank, which will also support later arguments. Choose a maximal matroid independent set $I_0$ in $A\cap B$, extend it to a maximal matroid independent set $I_A$ in $A$, and then to one $I_U$ in $A\cup B$. These extensions exist by successive additions, and their sizes are the respective values of the rank of a matroid. No element of $I_U\setminus I_A$ lies in $A$: such an element could have been added to $I_A$, contradicting maximality in $A$. Therefore $I_0\cup (I_U\setminus I_A)$ is an independent subset of $B$, givingNow let $Y\subseteq Z$ and $x\in \sigma (Y)$. If $x\in Z$, then $x\in \sigma (Z)$ by (ii). Otherwise apply submodularity of matroid rank to $Y+x$ and $Z$, whose intersection is $Y$:The monotonicity of the rank of a matroid supplies the opposite bound $r(Z+x)\ge r(Z)$, so equality holds. Thus $x\in \sigma (Z)$, proving $\sigma (Y)\subseteq \sigma (Z)$.

The rank of a matroid on a subset $A\subseteq X$ isThe matroid independence axioms imply that every maximal matroid independent set in $A$ has this cardinality. We write $A+x=A\cup \{x\}$, as in the source. Directly from the definition,For the last upper bound, deleting $x$ from any matroid independent set in $A+x$ leaves an independent subset of $A$.

Since $Y$ is a maximal matroid independent set in $Z$, augmentation gives $r(Y)=|Y|=r(Z)$. For any $x\in X$, the rank of a matroid of $Z+x$ equals that of $Y+x$. Indeed, if $x\notin Z$, either $Y+x$ is independent and has the largest possible size $|Y|+1$, or it is dependent and $Y$ is still maximal in $Z+x$: no element of $Z\setminus Y$ can be added, and neither can $x$. If $x\in Z$, both ranks are simply $|Y|$.

Consequently $r(Y+x)=r(Y)$ if and only if $r(Z+x)=r(Z)$, which proves $\sigma (Y)=\sigma (Z)$ for the closure of a matroid.

Write $r(Y)=r$. Since $y\notin \sigma (Y)$, the one-element increment bound gives $r(Y+y)=r+1$. Since $y\in \sigma (Y+x)$,But $Y+y\subseteq Y+x+y$ gives the reverse lower bound $r(Y+x+y)\ge r(Y+y)=r+1$. Hence $r(Y+x+y)=r(Y+y)$, which is precisely $x\in \sigma (Y+y)$. This is the matroid closure exchange property; it follows from one-element rank of a matroid increments and does not require exchanging an entire matroid basis.

By (ii), $Y\subseteq \sigma (Y)$, and by (vi) these subsets have equal rank of a matroid. Apply (v) to this pair to obtainThus the closure of a matroid is an idempotent function.

List $\sigma (Y)\setminus Y=\{x_1,\dots ,x_m\}$ and put $Y_j=Y\cup \{x_1,\dots ,x_j\}$. Each $x_j\in \sigma (Y)$ also belongs to $\sigma (Y_{j-1})$ by (iii). Thus the definition of the closure of a matroid gives $r(Y_j)=r(Y_{j-1})$ at every step. Iteration yieldsIn particular, collecting all elements that individually fail to increase the rank of a matroid does not create a collective increase.

Choose a maximal matroid independent set $B\subseteq Y$. Its cardinality is $r(Y)=r(Z)$, so it is also maximal in $Z$. Apply (iv) first inside $Y$ and then inside $Z$:This proves that nested subsets of equal rank of a matroid have the same closure of a matroid.

For a subset $A$ of the ground set, the rank of a matroid on $A$ is the maximum cardinality of a matroid independent set contained in $A$:Thus $r_M(E)$ is the common size of the matroid bases, and $r_M(\varnothing )=0$. The weighted three-vector matroid has $r_M(E)=2$, even though its ground set has three labels.

On labelled ground sets of sizes $1,2,3$, there are respectively $2,5,16$ matroids, or $2,4,8$ up to matroid isomorphism. At rank of a matroid one, a nonempty subset of nonloops specifies all matroid independent sets of cardinality one. On three labels at rank of a matroid two, the three types are one matroid loop with an independent pair, no matroid loops with one pair of parallel elements of a matroid, and all pairs independent with the triple dependent.

The rank of a matroid is a normalised set function, a monotone set function, and a submodular set function. Adding one element increases it by at most one.

Proof of submodularity. Choose a maximal matroid independent set $I_0$ in $A\cap B$, extend it to a maximal matroid independent set $I_A$ in $A$, then extend it to one $I_U$ in $A\cup B$. The matroid independence axioms make their sizes $r(A\cap B)$, $r(A)$ and $r(A\cup B)$. Every element of $I_U\setminus I_A$ lies outside $A$, since otherwise it could be added to $I_A$ inside $A$. Hence $I_0\cup (I_U\setminus I_A)$ is an independent subset of $B$, so its size $r(A\cap B)+r(A\cup B)-r(A)$ is at most $r(B)$.

The remaining assertions follow from the definition of the rank of a matroid. The empty set has maximum independent size zero, increasing the available subset cannot reduce that maximum, and deleting a newly added element from an independent subset decreases its size by at most one.

On a finite ground set $E$, a submodular rank function is a normalised set function $r$ with $r(\varnothing )=0$, a monotone set function, and a submodular set function, such that $r(A\cup \{e\})-r(A)\in \{0,1\}$ for $e\notin A$. Equivalently, require nonnegative integer values, monotonicity, submodularity and $r(\{e\})\le 1$. The diminishing returns characterization of submodularity bounds each marginal by its singleton value. Thus $0\le r(A)\le |A|$.

These functions are precisely the rank functions of matroids. To see the converse direction, define $\mathcal{I}=\{A:r(A)=|A|\}$. It contains the empty set. If $B\subseteq A\in \mathcal{I}$, the unit marginal bounds give $|A|=r(A)\le r(B)+|A\setminus B|$, so $r(B)=|B|$ and heredity holds. For augmentation, suppose $A,B\in \mathcal{I}$ with $|A|<|B|$. If every $e\in B\setminus A$ had zero marginal over $A$, diminishing returns would keep each marginal zero as they are added successively. This would give $r(A\cup B)=r(A)=|A|<|B|=r(B)$, contradicting monotonicity. Some marginal is therefore one, giving an independent augmentation.

Finally any inclusion-maximal $I\subseteq A$ in this independence family has $r(I\cup \{e\})=r(I)$ for every remaining $e\in A\setminus I$. Successively adding them and using diminishing returns shows $r(A)=r(I)=|I|$, so the resulting matroid really has rank $r$. The forward direction is submodularity of matroid rank. These integer increment conditions distinguish matroid ranks from arbitrary real-valued submodular functions.

For $0\le r\le n$, the uniform matroid $U_{r,n}$ on an $n$-element ground set has as its matroid independent sets exactly the subsets of cardinality at most $r$. Heredity is immediate, and augmentation works because any smaller such subset can acquire an element of a larger one without exceeding $r$. Its rank of a matroid on $A$ is $\min \{|A|,r\}$.