Articles of matroids

Show that a matched set of nodes forms a matroid

Let $G=(V,E)$ denote a graph. We call a subset of nodes $V^\prime\subset V$ matched if there is a matching $M\subset E$ in $G$ such that $M$ contains all nodes in $V^\prime$. We define the family of sets $U=(V,\mathcal{I})$ with $$\mathcal{I}:=\{I\subset V\;:\;I\textrm{ is matched regarding }G\}.$$ Show that $U$ is a matroid. I have quite some […]

What structure does the set of all the matchings in a graph have?

In a graph, the class of all the sets of vertices that can be covered by some matching forms a matroid. I wonder what kind of structure the class of all the matchings in a graph can have? Or does it not have any usual structure? It seems to me that it is close to […]

Intuitive explation for oriented matroids?

Where can you find intuitive explanation on oriented matroids? Other perhaps relevant questions on this How do you get the chirotope of a oriented matroid from the signed circuits? (other than just work backwards) Also is there any nice characterization on the chirotope of a directed graph or the signed circuit structure of a linear […]

Submodularity of the product of two non-negative, monotone increasing submodular functions

I’m trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, $f:2^{\Omega}\rightarrow \mathbb{R}$ and for every $S, T \subseteq \Omega$ we have that $f(S)+f(T)\geq f(S\cup T)+f(S\cap T)$. We also have that $f$ and $g$ are non-negative: $f(.) \geq 0$ […]