2
$\begingroup$

Valuated matroids can be defined in terms of valuated vectors. I'm wondering whether is there an equivalent definition for ordinary matroids?

Below I include two standard definitions of valuated matroids.

Let $V$ be a finite set. If $X$ is an element of $(\mathcal{R}\cup\{\infty\})^V$, let $X_i$ denote the $i$-th element of the $\vert V \vert$-tuple and $\underline{X}$ denote the support of $X$, that is, the set of entries in the $\vert V \vert$-tuple which are not $\infty$.

A valuated matroid on $V$ is a family $\mathcal{X}\subseteq (\mathcal{R}\cup\{\infty\})^V$ such that

  1. $(\infty,\ldots,\infty)\notin\mathcal{X}$,
  2. if $X,Y\in\mathcal{X}$ with $\underline{X}\neq \underline{Y}$ then $\underline{X} \nsubseteq \underline{Y}$,
  3. for $X\in \mathcal{X}$ and $\alpha\in \mathcal{R}$, $X+\alpha\textbf{1}\in\mathcal{X}$ holds,
  4. for $X,Y\in\mathcal{X}$ and $u,v\in V$ with $X_u=Y_u\neq \it$ and $X_v<Y_v$, there exists $Z\in\mathcal{X}$ such that $Z_u=\infty$, $Z_v=X_v$ and $Z\geq\min (X,Y)$.

We call the set $\mathcal{X}$ the valuated circuits. Now let us consider $\underline{\mathcal{X}}: = \{\underline{X} \mid X\in \mathcal{X} \}$. Then $\underline{\mathcal{X}}$ is a circuit family for an ordinary matroid on $V$.

Valuated matroids can be described equivalently in terms of valuated vectors in the following way.

Let $V$ be a finite set. A valuated matroid on $V$ is a family of $|V|$-tuples $\mathcal{V}\subseteq (\mathcal{R}\cup\{\infty\})^V$ such that

  1. $(\infty,\ldots,\infty)\in \mathcal{V}$,
  2. if $X,Y \in \mathcal{V}$, then $\min(X,Y)\in\mathcal{V}$, where the minimum is taken coordinate-wise,
  3. for $X\in \mathcal{V}$ and $\alpha \in \mathcal{R}$, we have $X+\alpha\textbf{1}\in\mathcal{V}$, where $\textbf{1} = (1,\ldots,1)$,
  4. for $X,Y\in\mathcal{V}$ and $u\in V$ with $X_u=Y_u\neq\infty$, there is $Z\in \mathcal{V}$ such that $Z_u=\infty$, $Z\geq\min(X,Y)$ and $Z_i=\min(X_i,Y_i)$ for all $i$ with $X_i\neq Y_i$.

So my question is whether is there an equivalent definition of an ordinary matroid in terms of the set $\underline{\mathcal{V}}: = \{\underline{V} \mid X\in \mathcal{V} \}$?

$\endgroup$

1 Answer 1

1
$\begingroup$

For matroids, these are sometimes known as the set of vectors of a matroid. Other ways of characterizing the vectors of a matroid are:

  • $X$ is a vector of $M$ if and only if $X$ intersects no cocircuit of $M$ in exactly one element.
  • $X$ is a vector of $M$ if and only if the complement of $X$ is a flat of $M^*$.
  • $X$ is a vector of $M$ if and only if $X$ is a union of circuits of $M$.

The last property generalizes to valuated matroids as well: the vectors of a valuated matroid are exactly the tropical linear combinations of the circuits of a valuated matroid.

A bit of shameless self-promotion: a paper of mine with Colin Crowley and Noah Giansiracusa investigated matroidal interpretations of various constructions coming from valuated matroids. It can be found here: https://arxiv.org/abs/1712.03440

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .