A new matroid constructed by the rank function of a matroid

Abstract

In this article, we construct a submodular function using the rank function of a matroid and study induced matroid with constructed polymatroid, then we relate some properties of connectivity of new matroid with the main matroid.

Keywords:

• Submodular function
• Polymatroid
• Connected matroid

1 Introduction

For a set $E$, a function $f$ from $2^E$ into $\mathbb{R}$ is submodular if $f\left(X\right)+f\left(Y\right)\ge f(X\cup Y)+f(X\cap Y)$ for all subsets $X$ and $Y$ of $E$. Such a function is increasing if $f\left(X\right)\le f\left(Y\right)$ whenever $X\subseteq Y$. As an example of a submodular function, the rank function of a matroid $M$ is a submodular function. Edmonds and Rota [1] proved the following result. There is a more accessible proof in Oxley [2].

Proposition 1

Let $f$ be an increasing submodular function from $2^E$ into $\mathbb{Z}$. Let $\mathcal{C}\left(f\right)=\left\{C\subseteq E:C\text{is minimal}\text{and non-empty such that}f\left(C\right)<\left|C\right|\right\}$. Then $\mathcal{C}\left(f\right)$ is the collection of circuits of a matroid on $E$.

This matroid is denoted by $M\left(f\right)$ and it is called induced matroid by $f$. When $f\left(\varnothing \right)=0$ the submodular function $f$ has been called polymatroid function. For instance, the rank function of a matroid is a polymatroid. Oxley [2] has proved when $f$ is a polymatroid, the rank function of $M\left(f\right)$ is given by; (1) $$r_f\left(X\right)=min\{f\left(Y\right)+|X-Y|:Y\subseteq X\}.$$(1)

In splitting matroids we choose a subset $T$ of ground set of matroid, $E$, and then apply the splitting operation on $M$ with respect to $T$ and attain a new matroid. For more details one can see [3,4]. We are going to use almost the same method on the rank function of $M$, that means we assume a subset $T\subseteq E\left(M\right)$ and define a function as follows; (2) $$f_T\left(X\right)=\left\{\begin{array}{cc}r\left(X\right)\hfill & \text{if}X\cap T=\varnothing \hfill \\ r\left(X\right)+1\hfill & \text{if}X\cap T\ne \varnothing \hfill \end{array}\right.$$(2) It is not difficult to check that this function is a submodular function. Furthermore, defined function is actually a polymatroid. Therefore by Proposition 1, $f_T$ induces a matroid that is $M\left(f_T\right)$ where it has the same ground set with $M$. Connectivity of submodular functions properties is investigated in [5], this was an inspiration to us to carry out our investigations. First, we shall specify the collection of circuits and independent sets and determine the rank function of the new matroid, then we shall prove some more connectivity properties related between $M$ and $M\left(f_T\right)$.

2 Preliminary theorems

In the next theorem, we show that the $M\left(f_T\right)$ can be characterized in terms of circuits. The proof of this theorem will use the following proposition.

Proposition 2

Oxley [2] Let $\mathcal{X}$ and $\mathcal{Y}$ be collections of subsets of a finite set $E$ such that every member of $\mathcal{X}$ contains a member of $\mathcal{Y}$ , and every member of $\mathcal{Y}$ contains a member of $\mathcal{X}$ . Then the minimal members of $\mathcal{X}$ are precisely the minimal members of $\mathcal{Y}$ .

Theorem 3

Let $M$ be a matroid and $T\subseteq E$. Let $${\mathcal{C}}_0=\left\{C\in \mathcal{C}\left(M\right)|C\cap T=\varnothing \right\}{\mathcal{C}}_1=\left\{C_1\cup C_2:\text{it is minimal such that}{C}_1,C_2\in \mathcal{C}\left(M\right),C_i\cap T\ne \varnothing fori\in \{1,2\},|(C_1\cup C_2)\cap T|\ge 2and{C}_1\cup C_2\text{has no any circuit in}{\mathcal{C}}_0\right\}$$Then $\mathcal{C}={\mathcal{C}}_0\cup {\mathcal{C}}_1$ is the set of circuits of $M\left(f_T\right)$.

Proof

We shall prove that each element of ${\mathcal{C}}_0\cup {\mathcal{C}}_1$ is a minimal dependent element of $M\left(f_T\right)$ and each circuit of $M\left(f_T\right)$ contains an element of ${\mathcal{C}}_0\cup {\mathcal{C}}_1$. Suppose $C\in {\mathcal{C}}_0$. Since $C\cap T=\varnothing$ and $C\in \mathcal{C}\left(M\right)$, thus $f_T\left(C\right)=r\left(C\right)<\left|C\right|$. Then $f_T\left(C\right)$ is a dependent set in $M\left(f_T\right)$. Now assume $X\in {\mathcal{C}}_1$, where $X=C_1\cup C_2$. As $C_1$ and $C_2$ are two distinct circuits of $M$, $r(C_1\cup C_2)\le |C_1\cup C_2|-2$, also $X\cap T\ne \varnothing$, hence $f_T(C_1\cup C_2)=r(C_1\cup C_2)+1$. Therefore $f_T(C_1\cup C_2)<|C_1\cup C_2|$. Then $X$ is a dependent set in $M\left(f_T\right)$.

Conversely, let $X$ be a circuit of $M\left(f_T\right)$, that means $f_T\left(X\right)<\left|X\right|$ and it is minimal with this property. First note that, we may assume that $X$ is a union of circuits of $M$, since if $X$ contains many coloops in $M$, by deleting them we attain a proper subset $Y$ of $X$ in which $f_T\left(Y\right)<\left|Y\right|$ and this contradicts with minimality of $X$. Now if there is a circuit $C$ in $M|X$ such that $C\cap T=\varnothing$, then $X$ contains an element of ${\mathcal{C}}_0$. Hence we can assume that, every circuit of $M|X$ has a non-empty intersection with $T$. $M|X$ is not able to contain just a circuit of $M$, otherwise, let $C$ be the only circuit of $M|X$ (in fact $X=C$), since $$r\left(C\right)=\left|C\right|-1,C\cap T\ne \varnothing ⟹f_T\left(C\right)=\left|C\right|\text{or}{f}_T\left(X\right)=\left|X\right|$$contradicting that $f_T\left(X\right)<\left|X\right|$. Then $M|X$ contains at least two circuits of $M$. Suppose that $C_1$ and $C_2$ are two circuits of $M|X$. First let $C_1\cap C_2\ne \varnothing$. If $|(C_1\cup C_2)\cap T|=1$ then the only element of this set, named $a$, belongs to $C_1\cap C_2$ where $a\in T$. So by using $\left(C3\right)$ of circuit axioms, there is a circuit $C_3$ such that it is contained in $M|X$ and does not meet $T$, a contradiction. Thus $|(C_1\cup C_2)\cap T|\ge 2$. When $C_1\cap C_2=\varnothing$, it is clear that $|(C_1\cup C_2)\cap T|\ge 2$. Therefore, in any case $X$ contains an element of ${\mathcal{C}}_1$. Now the theorem follows immediately from Proposition 2.

We specified the collection of circuits of $M\left(f_T\right)$. Next theorem specifies the collection of independent sets of $M\left(f_T\right)$. Note that a consequence of Proposition 1 is that independent sets of $M\left(f\right)$ are precisely those subsets of $E$, named $I$, such that $f\left(I^{\prime }\right)\ge \left|I^{\prime }\right|$ for all non-empty subsets $I^{\prime }$ of $I$.

Theorem 4

Let $M$ be a matroid and $T\subseteq E$. Let $${\mathcal{I}}_0=\left\{I:I\in \mathcal{I}\left(M\right)\right\}{\mathcal{I}}_1=\left\{I\cup C:I\in \mathcal{I}\left(M\right),C\in \mathcal{C}\left(M\right);C\cap T\ne \varnothing \text{and}M|(I\cup C)\text{just contains}C\text{as a circuit}\right\}.$$Then $\mathcal{I}={\mathcal{I}}_0\cup {\mathcal{I}}_1$ is the set of independent sets of $M\left(f_T\right)$.

Proof

It is clear that if $I\in {\mathcal{I}}_0$, then $I$ is independent in $M\left(f_T\right)$. Let $X$ be an element of ${\mathcal{I}}_1$. For every subset $Y$ of $X$, $f_T\left(Y\right)\ge \left|Y\right|$, therefore $X$ is an independent set of $M\left(f_T\right)$.

Conversely, let $X$ be an independent set of $M\left(f_T\right)$. If $X$ contains at least two distinct circuits $C_1$ and $C_2$ of $M$, then $r(C_1\cup C_2)\le |C_1\cup C_2|-2$. So $f_T\left(Y\right)<\left|Y\right|$, where $Y=C_1\cup C_2$ is a subset of independent set $X$, a contradiction. Hence every independent set of $M\left(f_T\right)$ contains at most one circuit of $M$. Now if $X$ has no circuit of $M$ it belongs to ${\mathcal{I}}_0$ and if it contains a circuit of $M$, obviously it must meet $T$. Thus, in this case, $X\in {\mathcal{I}}_1$.

Corollary 5

The set of bases of $M\left(f_T\right)$ is; $$\mathcal{B}\left(M\left(f_T\right)\right)=\left\{B\cup \left\{e\right\}:B\in \mathcal{B}\left(M\right),e\in E\left(M\right)-B;C(e,B)\cap T\ne \varnothing \right\}.$$

Another consequence of the last theorem is the following result.

Corollary 6

Let $X$ be a subset of $E\left(M\right)$. The rank function of $M\left(f_T\right)$ is given by; $$r_{M\left(f_T\right)}\left(X\right)=\left\{\begin{array}{cc}{r}_M\left(X\right)+1\hfill & \text{if}M|X\text{contains a circuit}C\text{of}M\text{such that}C\cap T\ne \varnothing \hfill \\ r_M\left(X\right)\hfill & \text{otherwise}\hfill \end{array}\right.$$

In view of the last result, if an element of $T$ lies on a circuit of $M$, then the rank of $M\left(f_T\right)$ increased by one. Therefore if $M$ contains coloops and we choose a subset of them as $T$, then $M\left(f_T\right)=M$.

The next result specifies the set of hyperplans of constructed matroid.

Corollary 7

If $M\left(f_T\right)\ncong M$, then the set of hyperplans of $M\left(f_T\right)$ is equal to; $$\mathcal{H}\left(M\left(f_T\right)\right)=\left\{B\cup \{e_1,e_2,\dots ,e_n\};B\in \mathcal{B}\left(M\right),e_i\in E\left(M\right)-B\text{and}C(B,e_i)\cap T=\varnothing ;i\in \{1,\dots ,n\}\text{where}1\le n\le |E\left(M\right)-B|\right\}.$$

The following example can illustrate last results.

Example 8

Let $G$ be the graph shown in the following figure and let $M=M\left(G\right)$. Suppose $T=\{a,b,c\}$. One can easily show that, for example by Theorem 3, every $5$ elements set of the ground set of $M$ is a circuit of $M\left(f_T\right)$ and this is the collection of circuits of $M\left(f_T\right)$, so $M\left(f_T\right)$ is the uniform matroid $U_{4,6}$.

3 Main results

By definition, when $T=\varnothing$, the matroid $M\left(f_T\right)$ is equal to $M$. Furthermore $M\left(f_T\right)=M$ if and only if no circuit of $M$ meets $T$.

If $\left|T\right|=1$ and $M$ has no coloop, then $M\left(f_T\right)=M\setminus T\oplus U_{n,n}$, where $n$ is the number of elements that are in the common series class with $T$. It is obtained by this fact, every circuit of $M$ contains $T$ is not a circuit of new matroid anymore and note that ${\mathcal{C}}_1$ will be empty.

But when $\left|T\right|\ge 2$, we shall have significant results.

Example 9

Let $M\cong U_{m,n}$ and $m<n-1$. One can easily check that if $\left|T\right|\ge n-m$ then $M\left(f_T\right)\cong U_{m+1,n}$.

Theorem 10

Let $M$ be a disconnected coloopless matroid having $n$ connected components, called $M_1,M_2,\dots ,M_n$. Let $T=\{t_1,t_2,\dots ,t_n\}\subseteq E\left(M\right)$, where $t_i\in E\left(M_i\right)$ for $1\le i\le n$. Then $M\left(f_T\right)$ is connected.

Proof

As $M$ is disconnected so $n\ge 2$. It is sufficient to prove for each circuit $C_1$ and $C_2$ belonging to two different components of $M$ in which both of them meet $T$, $C_1\cup C_2$ is a circuit of $M\left(f_T\right)$. Since $C_1$ and $C_2$ are in distinct component, so $|(C_1\cup C_2)\cap T|=2$ and $C_1\cup C_2$ does not contain circuit $C^{\prime }$ of $M$ where $C^{\prime }\cap T=\varnothing$. Moreover each proper set of $C_1\cup C_2$ could not be dependent in $M\left(f_T\right)$, therefore it is a circuit of $M\left(f_T\right)$. Now let $a$ and $b$ be two distinct elements of $M$. It is not difficult to see that there is a circuit in $M\left(f_T\right)$ containing both.

The rank function of $M\left(f_T\right)$ gives us interesting properties of $k$-connectedness. Next lemma specifies one of these features.

Lemma 11

Let $M$ be an $n$-connected matroid where $3\le n<\infty$and let $T\subseteq E$ such that $\left|T\right|\ge n$. Then $M\left(f_T\right)$ is an $(n-1)$-connected matroid.

Proof

If $\left|E\left(M\right)\right|<2(n-1)$, then $M$ has infinite Tutte connectivity, hence we may assume that $\left|E\left(M\right)\right|\ge 2(n-1)$. We must prove that for every $k<n-1$, $M\left(f_T\right)$ has no $k$-separation. For convenience we relabel $M\left(f_T\right)$ with $M^{\prime }$. Suppose $(X,Y)$ be a partition of $E\left(M^{\prime }\right)$, where $min\{\left|X\right|,\left|Y\right|\}=k$ for $k<n-1$. Without loss of generality let $\left|X\right|=k$. Since $M$ is $n$-connected it has no circuit or cocircuit with less than $n$ elements, hence $X$ is independent in $M$ and so does $M^{\prime }$. As $\left|T\right|\ge n$, then $Y$ meets $T$, and $M|Y$ does not have coloops, since if it contains coloops, as regards $\left|X\right|=k<n-1$ then $M$ has a cocircuit with less than $n$ elements, a contradiction. Thus $r_{M^{\prime }}\left(Y\right)=r_M\left(Y\right)+1$ and $r_{M^{\prime }}\left(E\right)=r_M\left(E\right)+1$. Therefore $$r_{M^{\prime }}\left(X\right)+r_{M^{\prime }}\left(Y\right)-r_{M^{\prime }}\left(E\right)=r_M\left(X\right)+r_M\left(Y\right)+1-r_M\left(E\right)-1={\lambda }_M\left(X\right)\ge k.$$This means that $M^{\prime }$ has no $k$-separation for $k<n-1$, then $M\left(f_T\right)$ is $(n-1)$-connected.

We note here that the last lemma does not hold if $M$ is a matroid with infinite Tutte connectivity. For example, consider $U_{4,8}$ and let $\left|T\right|=4$, by Example 9, $M\left(f_T\right)\cong U_{5,8}$. The first matroid is a matroid with infinite Tutte connectivity, while the Tutte connectivity of the second matroid is $4$. Therefore throughout this article we assume $M$ has no infinite Tutte connectivity. Evidently, if $n=2$, then $M\left(f_T\right)$ might be disconnected, so with putting special condition the lemma is true in this case.

The next theorem specifies the connectivity of $M\left(f_T\right)$ when $M$ is not $3$-connected. We have utilized following proposition and lemma to prove the theorem.

Proposition 12

Every matroid that is not 3-connected can be constructed from 3-connected proper minors of itself by a sequence of the operations of direct sum and 2-sum.

Lemma 13

Let $M$ be a matroid such that $M=M_1{\oplus }_2{M}_2$ and it contains at least two circuits. Let $T\subseteq E\left(M\right)$ in which $\left|T\right|\ge 2$ and $E\left(M_i\right)\cap T\ne \varnothing$ for $i\in \{1,2\}$. Then $M\left(f_T\right)$ is connected.

Proof

The definition of $2$-sum is $M=M_1{\oplus }_2{M}_2=P(M_1,M_2)\setminus p$, where $P(M_1,M_2)$ is parallel connection of $M_1$ and $M_2$, and $\left\{p\right\}=E\left(M_1\right)\cap E\left(M_2\right)$. Let $C_i$, $i\in \{1,2\}$, be circuits of $M_i$ containing $p$. By definition $C=(C_1-p)\cup (C_2-p)$, is a circuit of $M$. If $C_i\cap T=\varnothing$, then $C$ is a circuit of $M\left(f_T\right)$. Thus, if one of $C_1$ and $C_2$ meets $T$, as both of $M_1$ and $M_2$ are connected, we may assume that the other meets $T$ too. Hence $C_i\cap T\ne \varnothing$ and $|C\cap T|\ge 2$. Since $M$ contains at least two circuits, either $M_1$ or $M_2$ contains two circuits. Without loss of generality we may assume that, it is $M_2$. Then there is a circuit $C_2^{\prime }$ in $M_2$ that contains $p$, such that it is distinct from $C_2$. So $C^{\prime }=(C_1-p)\cup (C_2^{\prime }-p)$ is a circuit of $M$. We shall now show that $C\cup C^{\prime }$ is a circuit of $M\left(f_T\right)$. Obviously $|(C\cup C^{\prime })\cap T|\ge 2$. Let $X$ be a circuit of $M$ contained in $C\cup C^{\prime }$, where $X\cap T=\varnothing$. It is clear that $X\cap C_i\ne \varnothing$, so $X$ is union of two circuits $X_1$ and $X_2$ of $M_1$ and $M_2$, respectively. Hence $X=(X_1-p)\cup (X_2-p)$. Since $X_i$ does not contain $T$ but $C_i$ does, $X_i$ are proper subsets of $C_i$ respectively, a contradiction. Thus $C\cup C^{\prime }$ does not contain an element of ${\mathcal{C}}_0$. In a similar way, one can easily show that $C\cup C^{\prime }$ is minimal. Then $C\cup C^{\prime }$ is a circuit of $M\left(f_T\right)$.

Now if $a$ and $b$ are two arbitrary elements of $M$, considering various cases one can easily see that there is a circuit of $M\left(f_T\right)$ that contains $a$ and $b$, therefore $M\left(f_T\right)$ is connected.

Theorem 14

Let $M$ be a connected matroid and contains at least two distinct circuits, then there is a subset $T\subseteq E$, where $\left|T\right|\ge 2$, for which $M\left(f_T\right)$ is connected.

Proof

If $M$ is 3-connected then by Lemma 11, $M\left(f_T\right)$ is connected with mentioned situation, we may assume that, $M$ is not 3-connected. Therefore by Proposition 12, $M\cong M_1{\oplus }_2{M}_2{\oplus }_2\dots {\oplus }_2{M}_n$, where $M_i$ is 3-connected. We choose an element $t_i$ of $M_i$ and consists of subset $T$ of $M$. We argue by induction on $n$ to achieve result. If $n=2$ by Lemma 13, the result is obtained. Now let it be true for $k<n$. Obviously $M_1{\oplus }_2{M}_2{\oplus }_2\dots {\oplus }_2{M}_k$ is connected. Then by using Lemma 13 again on $(M_1{\oplus }_2{M}_2{\oplus }_2\dots {\oplus }_{2}k){\oplus }_2{M}_{k+1}$, the result is proven by induction.