{"id":464,"date":"2013-11-25T20:20:27","date_gmt":"2013-11-26T01:20:27","guid":{"rendered":"http:\/\/matroidunion.org\/?p=464"},"modified":"2013-11-26T07:23:52","modified_gmt":"2013-11-26T12:23:52","slug":"rado-matroids","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=464","title":{"rendered":"Rado matroids"},"content":{"rendered":"

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’\u00a0notes on Rado matroids<\/a>\u00a0and partly [Oxley11, Sections 11.1-11.3].<\/p>\n

Let $G$ be a bipartite graph, with bipartition $(X,Y)$. Denote by\u00a0$N(S)$ the set of neighbours of vertices in $S$ that are in $V(G)-S$.\u00a0Suppose 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\u00a0subsets of $X$ satisfying $|S|>r(N(S))+t$.\u00a0With this definition we have the following proposition. The proof is short, so I’ll include it.<\/p>\n

Proposition 1:\u00a0<\/strong>$\\mathcal{C}$ is the set of circuits of a matroid on $X$.<\/i><\/p>\n

proof:<\/strong>\u00a0From 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$.\u00a0Using (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$.<\/p>\n

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

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$<\/p>\n

I’ll call a matroid defined this way a Rado matroid.<\/i>\u00a0Rado defined these matroids for $t=0$, so in this case I will call the matroid a standard Rado matroid<\/em>. 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\u00a0$|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.<\/p>\n

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).<\/p>\n

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.<\/p>\n