2
$\begingroup$

Let $G = (V,E)$ be a graph and let $w:E\to\mathbb{R}$ be a weight function. Given $F\subseteq E$ we can consider the independent sets in $F$. Such an independent set is called a base of $F$ if it's maximal (inclusion wise). I'm interested in whether or not the maximum weight spanning trees form the bases of a matroid.

What I've got thus far:

I think it's impossible for the maximum weight spanning trees to form the bases of a matroid. If the maximum weight spanning trees form the bases of a matroid, then we must have that the independent sets that are not maximum weight spanning trees don't form a base right? In this case the independent sets can't be defined to be spanning trees, because that would mean that it were possible for a non maximum weight spanning tree to be a base, right? Take for instance $I,J \in \mathcal{I}$ where sets in $\mathcal{I}$ are spanning trees. If $I$ is a non maximum weight spanning tree and $J$ is a maximum weight spanning tree, it is very possible that $I\nsubseteq J$ and hence $I$ would possibly be a base.

If my reasoning is correct -which I doubt- we would have that the maximum weight spanning trees are not the bases of a matroid, because we would have that $\emptyset\notin \mathcal{I}$.

Question: Is my solution correct? If it's not, which is more likely, what am I doing wrong/in what direction do I need to look?

Thanks in advance!

$\endgroup$
6
  • $\begingroup$ It's not impossible for the max weight spanning trees of a graph $G$ to form the bases of a matroid. Two infinite families are given by $(G, w)$ where (1) $G$ is a tree and $w$ is arbitrary or (2) $G$ is a cycle and $w$ is constant. $\endgroup$
    – Aaron Dall
    Commented Nov 27, 2017 at 22:08
  • $\begingroup$ @AaronDall Thanks for you reply Aaron. It's not really clear what you mean to me, based on your comment. Could you elaborate? $\endgroup$
    – titusAdam
    Commented Nov 30, 2017 at 14:59
  • $\begingroup$ For the first family, let $G$ be a tree and $w$ be any weight function. Then $G$ is the unique maximum-weight spanning tree. The corresponding matroid is the uniform matroid $U_{e,e}$ where $e$ is the number of edges of $G$. $\endgroup$
    – Aaron Dall
    Commented Nov 30, 2017 at 17:13
  • $\begingroup$ It's a trivial example, but an example nonetheless. $\endgroup$
    – Aaron Dall
    Commented Nov 30, 2017 at 17:16
  • $\begingroup$ @AaronDall I'm sorry but I don't understand your notation. Let me show you by taking one of your two examples: the family given by $(G,w)$ where $G$ is a tree and $w$ is arbitrary. What would $(G,w)$ mean? It's not a graph right, because $G$ is a set of edges instead of a set of nodes. $\endgroup$
    – titusAdam
    Commented Dec 1, 2017 at 8:59

1 Answer 1

2
$\begingroup$

Note: The following is essentially taken from Section 2 of The Bergman complex of a matroid and phylogenetic trees by Ardila and Klivans.

Given a matroid $M = (E, \mathcal{B})$ and a weight function $w:E \to \mathbb{R}$, the set system $M_w$ consisting of those bases of $M$ maximized by $w$, that is, those bases for which the sum $\sum_{e\in B}w(e)$ is maximized.

Theorem 1: $M_w$ is a matroid for any matroid $M$ and any weight function $w$.

One miraculous feature of matroids is that they can be defined in many ways. This fact is not only a novelty: some facts about matroids that are very hard to prove starting with one definition can be deduced relatively easily when starting with another definition. The original post is just such a problem.

Let's start with two definitions of matroids.

First, a matroid is a pair $(E, \mathcal{B})$ consisting of a ground set $E$ and a nonempty collection of bases $\mathcal{B}$ such that $\mathcal{B}$ is a clutter satisfying the following exchange condition: For any $A,B \in \mathcal{B}$ and any $e \in A \setminus B$ there is an $f \in B \setminus A$ such that $A \setminus e \cup f \in \mathcal{B}$.

Here is a very different definition of a matroid: a matroid is a convex polytope $P$ with vertices in the standard unit cube whose edges are translates of differences of standard unit vectors, that is, every edge of $P$ is a translate of a vector of the form $\mathbf{e}_i - \mathbf{e}_j$.

It is a nice exercise to prove these two definitions of a matroid are equivalent (or see the references in the paper cited earlier). A polytope that is also a matroid (in the sense of the second definition above) is called a matroid polytope.

Now, the vertices of a matroid polytope $P \subset \mathbb{R}^n$ are the characteristic vectors of the set of bases of a matroid $M ([n], \mathcal{B})$ (in the sense of the first definition above), where $[n] = \{1,2,\dots,n\}$ as usual.

Let $w$ be any weight function on $[n]$. Let $\mathbf{n} = \left[w(1), \dots, w(n)\right] \in (\mathbb{R}^n)^*$ be the corresponding linear functional. Then Theorem 1 follows by applying the following general facts about convex polytopes to the matroid polytope $P$ and the weight function $w$:

  1. Every face of a polytope is a polytope; and
  2. If $P$ is a polytope and $\mathbf{n}$ a linear functional, then the subset of $P$ consisting of points maximized by $\mathbf{n}$ is a face of $P$.
$\endgroup$

You must log in to answer this question.

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