Rado matroids

In this post I’ll discuss a way of constructing matroids from other matroids. A simpler form of this construction was first introduced by Rado. I will follow partly Matt DeVos’ notes on Rado matroids and partly [Oxley11, Sections 11.1-11.3].

Let $G$ be a bipartite graph, with bipartition $(X,Y)$. Denote by $N(S)$ the set of neighbours of vertices in $S$ that are in $V(G)-S$. Suppose that $M$ is a matroid on ground set $Y$ with rank function $r$. Let $t$ be any integer and define $\mathcal{C}$ to be the set of minimal non-empty subsets of $X$ satisfying $|S|>r(N(S))+t$. With this definition we have the following proposition. The proof is short, so I’ll include it.

Proposition 1: $\mathcal{C}$ is the set of circuits of a matroid on $X$.

proof: From the definition we immediately have that the first two circuit axioms are satisfied. Now consider distinct $C_1, C_2 \in \mathcal{C}$ and an element $e \in C_1 \cap C_2$. Using (in the last inequality) the fact that $C_1\cap C_2$ does not contain any member of $\mathcal{C}$, we have that $\\|C_1 \cup C_2| + |C_1 \cap C_2| = |C_1| + |C_2|\\ \geq r(N(C_1))+r(N(C_2))+2t+2\\ \geq r(N(C_1)\cup N(C_2)) + r(N(C_1) \cap N(C_2)) +2t +2\\ \geq r(N(C_1 \cup C_2))+r(N(C_1 \cap C_2)) +2t +2\\ \geq r(N(C_1 \cup C_2))+|C_1 \cap C_2|-t +2t +2$.

Therefore $r(N(C_1 \cup C_2)) \leq |C_1 \cup C_2|-t-2$. Let $C’=(C_1 \cup C_2)-e$.

Then $r(N(C))\leq kr(N(C_1 \cup C_2))\leq |C_1 \cup C_2|-t-2=|C|-t-1$. Hence $r(N(C))< |C|-t$, so $C$ contains an element of $\mathcal{C}$. $\hspace{2 cm} \Box$

I’ll call a matroid defined this way a Rado matroid. Rado defined these matroids for $t=0$, so in this case I will call the matroid a standard Rado matroid. We may make the definition above more general by adding a parameter $k \geq 1$ and defining $\mathcal{C}$ to be the minimal non-empty sets satisfying $|S|>kr(N(S))+t$. Then the proposition above still holds (with the same proof). However, all the examples I’m going to introduce here have $k=1$, so I will stick to the simpler definition.

Note that, strictly speaking, every matroid is a Rado matroid: if $N$ is any matroid on ground set $E$, then we can obtain it as a standard Rado matroid on $G$ with bipartition $(E,E)$, where every vertex is adjacent to its copy (and the matroid on $Y=E$ is $N$). However, seeing a matroid as a Rado matroid is sometimes useful, for example in the case of the hypergraphic matroids (which I will define later).

Lots of matroids may be constructed as Rado matroids (in a non-trivial way). Since there are many objects involved in the definition of a Rado matroid and I’m a bit lazy, in the following examples I will always assume that $G, X, Y, M$ and $t$ are as above and I’ll denote just by $R$ the Rado matroid.

  • If $t \leq -r(M)$, then $R=U_{0,n}$.
  • If $t \geq |Y|$, then $R=U_{n,n}$.
  • If $M$ is a free matroid, then the standard Rado matroid is a transversal matroid (with respect to the sets $N(v)$ for $v \in X$).
  • If $H$ is a graph and $G$ has bipartition $(E(H),V(H))$, where $e \in E(H)$ is adjacent to $v \in V(H)$ if $v \in e$, and $M$ is a free matroid, then the standard Rado matroid is the bicircular matroid of $H$. Thus we see that bicircular matroids are transversal matroids [Mat77].
  • Define $G$ from $H$ as above and let $M$ be a free matroid again. If now we choose $t=-1$ we obtain as a Rado matroid the graphic matroid of $H$.

We can generalise the construction above to hypergraphs. Suppose that $H=(V,F)$ is a hypergraph and define $G$ as the graph with bipartition $(F,V)$, where $f \in F$ is adjacent to $v \in V$ if $v \in f$. Let $M$ be a free matroid and set $t=-1$. Then $R$ is the hypergraphic matroid, defined by Lorea [Lor75]. We can also see hypergraphic matroids as standard Rado matroids, with this alternative definition. Our starting hypergraph is still $H=(V,F)$. We define the bipartition of $G$ to be $(F,E)$, where $E$ is the edge set of $K_V$, the complete graph on $V$. For $f \in F$ and $e=uv \in E$, we set $e$ to be adjacent to $f$ if $u,v \in f$. Now if we choose $M$ to be the graphic matroid on $K_V$ then the standard Rado matroid is again the hypergraphic matroid of $H$. The advantage of this alternative definition is that Rado [Rado42] proved the following result for standard Rado matroids (where again $G, X, Y$ and $M$ are as in definition above). Call a matching independent if the set of vertices it covers in $Y$ is independent in $M$.

Theorem 2: If $R$ is a standard Rado matroid then a set $S \subseteq X$ is independent in $R$ if and only if there is an independent matching in $G$ covering $S$ (i.e. $S$ may be matched to an independent set of $M$).

From the definition of standard Rado matroids, we immediately have that a set $S \subseteq X$ is independent in $R$ exactly when $|S’|\leq r(N(S’))$ for every $S’$ contained in $S$. Thus Rado’s theorem is saying that this condition is satisfied exactly when $S$ may be matched to an independent set of $M$. This result looks suspiciously similar to P. Hall’s marriage theorem [Hall35]: in fact we obtain Hall’s marriage theorem from Theorem 2 when $M$ is a free matroid. A proof of Theorem 2 may be found, for example, in Matt DeVos’ notes on Rado matroids. In the same notes you may also find a proof of the following generalisation of König’s Theorem for bipartite graphs.

Theorem 3: There exists $A$ contained in $X$ such that the size of the largest independent matching is equal to $|X-A|+r(N(A))$.

Corollary 4: In a standard Rado matroid, the rank of $S\subseteq X$ is equal to $$min_{A \subseteq S} \{|S-A|+r(N(A))\}.$$

Going back to our definition of a hypergraphic matroid as a standard Rado matroid, Theorem 2 tells us that a set of hyperedges $I$ is independent in this matroid if and only if we may replace every $f \in I$ with an edge $uv$, for $u,v \in f$, so that the resulting graph is a forest. This result was proved in [FKK03] (using the first definition of hypergraphic matroids).

Another interesting application of Rado’s construction is that we may obtain the Matroid Union Theorem (so relevant to our blog) as a consequence.  In fact, let $N_1,\ldots,N_k$ be matroids on a common ground set $E$, and let $M$ be the direct sum of $N_1,\ldots,N_k$. Define a bipartite graph $G$ with bipartitions $E$ and $E_1\cup \cdots\cup E_k$, where each $E_i$ is a copy of $E$ (seen as the ground set of $N_i$). Any element $e \in E$ is adjacent to each of its copies in $E_1,\ldots,E_k$. Then the standard Rado matroid is just the union matroid $N_1 \vee \cdots \vee N_k$, first introduced by Nash-Williams [N-W66]. As expected, Corollary 4 implies that the rank of a set $S$ in $N_1 \vee \cdots \vee N_k$ is $$min_{A \subseteq S} \{|S-A|+r_1(A)+\cdots +r_k(A)\},$$ where $r_i(A)$ is the rank of $A$ in $N_i$.

I was first introduced to Rado matroids while working on a paper [DMP13] with Matt DeVos and Jessica McDonald. Another nice theorem that we used in that paper is a result by Király, Lau and Singh [KLS08]. Basically this theorem says that, if $M$ has a fractional basis satisfying some constraints, then it has an actual basis almost satisfying those constraints. This theorem has nothing to do with Rado matroids, but I think it’s a nice result so I’m going to go ahead and end my post on it. First let me define what I mean by a fractional basis.

Let $M$ be a matroid on $E$ with rank function $r$ and let $x \in \mathbb{R}^E$ be a vector satisfying the following three constraints:

  1. $0 \leq x(e) \leq 1$, for every $e \in E$.
  2. $x(S) \leq r(S)$, for every $S \subseteq E$.
  3. $x(E)=r(E)$.

Then we say that $x$ is a fractional basis of $M$. The name is justified by the following result of Edmonds’ [Edm69].

Theorem 5: If a vector $x$ satisfies 1. and 2. above, then $x$ is a convex combination of incidence vectors of independent sets of $M$.

Thus a fractional basis is a convex combination of incidence vectors of bases of $M$. The last result of this post (from [KLS08]) may be used, for example, to prove the existence of a bounded degree spanning tree in a graph if a bounded degree fractional spanning tree exists.

Theorem 6: Let $M$ be a matroid on $E$, let $x$ be a fractional basis of $M$, and let $\mathcal{F}$ be a collection of subsets of $E$ so that every $e \in E$ is contained in at most $d$ members of $\mathcal{F}$. Then $M$ has a basis $B$ such that every $F \in \mathcal{F}$ satisfies $|B \cap F| \leq \lceil x(F) \rceil +d -1$.

References

[DMP13] M. DeVos, J. McDonald, I. Pivotto, Packing Steiner trees, submitted. (available on the ArXiv)

[Edm69] J. Edmonds, Submodular functions, matroids and certain polyhedra, Com- binatorial structures and their applications (Proc. Calgary Internat. Conf. 1969), 69-87. Gordon and Breach, New York.

[FKK03] A. Frank, T. Király, and M. Kriesell, On decomposing a hypergraph into $k$ connected sub-hypergraphs, Discrete Appl. Math. 131 (2003), 373-383.

[Hall35] P. Hall, On representatives of subsets, Quart. J. London Math. Soc. 10 (1935), 26-30.

[KLS08] T. Király, L. C. Lau, and M. Singh, Degree bounded matroids and submodular flows, Proceedings of 13th International Conference IPCO 2008, LNCS 5035 (2008), 259-272.

[Lor75] M. Lorea, Hypergraphes et matroides, Cahiers Centre Etud. Rech. Oper. 17 (1975), 289-291.

[Mat77] L.R. Matthews, Bicircular Matroids, Quart. J. Math. Oxford (2), 28 (1977), 213-228.

[N-W66] C. St. J. A, Nash-Williams, An application of matroids to graph theory, In Theory of Graphs (Internat. Sympos. Rome) (1966), 263-265. Dunod, Paris

[Oxley11] J. Oxley, Matroid Theory, Oxford University Press, New York (2011).

[Rado42] R. Rado, A theorem on independence relations, Quart. J. Math. Oxford 13 (1942), 83-89.

One thought on “Rado matroids

  1. In the representable case, matroid induction corresponds to multiplying a free matrix (representing a transversal matroid) on the right by another matrix (representing the matroid that we are inducing).

    Using this picture, back in the 1970’s, Schrijver and I (independently) discovered a generalization of this, replacing the free matrix with a “bimatroid” or “linking system.” There is probably a lot of work left to be done here. …

    References.
    A. Schrijver, Matroids and linking systems, JCTB 26 (1979) 349-369.
    JPS Kung, Bimatroid and invariants, Adv. Math. 30 (1978) 238-249

Leave a Reply

Your email address will not be published. Required fields are marked *