Articles of matroids

Matroids: Prove that for circuit $C$ and its cocircuit $C^*$: $|C \cap C^*| \neq 1$

Prove that for circuit $C$ and its cocircuit $C^*$: $|C \cap C^*| \neq 1$ Any hints and assistance would be very nice! Thank you.

How to show the complete graph $K_5$ has no abstract dual

How do you show that the dual of the matroid obtained from the 5-vertex complete graph $K_5$ is not graphic, or equivalently, that $K_5$ has no abstract dual? I assume graphs considered here are simple. I (tried to) show it in the following way: to show it by contradiction, let $G$ be an abstract dual […]

Support of a vector

What is the support of a signed vector? By signed vector, I mean a vector which is determined by considering the signs of the coefficients of the entries of another vector.

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$ […]