On Functions of K-Balanced Matroids
Talal Al-Hawary

Abstract

In this paper, we prove an analogous to a result of Erdös and Rényi and of Kelly and Oxley. We also show that there are several properties of k-balanced matroids for which there exists a threshold function.

Keywords

Share and Cite:

Al-Hawary, T. (2017) On Functions of K-Balanced Matroids. Open Journal of Discrete Mathematics, 7, 103-107. doi: 10.4236/ojdm.2017.73011.

1. Introduction

We begin with some background material, which follows the terminology and notation in  . Let $M=\left(E,F\right)$ denote the matroid on the ground set E with flats F. All matroids considered in this paper are loopless. In particular, if M is a matroid on a set E and X ⊆ E, then r(X) will denote the rank of X in M. We shall be considering projective geometries over a fixed finite field GF(q), recalling that

(see, for example  ) the number $\left[\begin{array}{c}r\\ n\end{array}\right]$ of rank-n subspaces of the projective

geometry PG (r − 1, q) is

$\frac{\left({q}^{r}-1\right)\left({q}^{r-1}-1\right)\cdots \left({q}^{r-n+1}-1\right)}{\left({q}^{n}-1\right)\left({q}^{n-1}-1\right)\cdots \left(q-1\right)}.$

The uniform matroid of rank r and size n is denoted by ${U}_{r,n}$ where

$r=0,1,\cdots ,n$ . When r = n, the matroid ${U}_{r,r}$ is called free and when r = n = 0, the matroid ${U}_{0,0}$ is called the empty matroid. For more on matroid theory, the reader is referred to  -  . Let k be a nonnegative integer. The k-density of a

matroid M with rank greater than k is given by ${d}_{k}\left(M\right)=\frac{|M|}{r\left(M\right)-k}$ , where |M|

is the size of the ground set of M and r(M) is the rank of the matroid M. A matroid M is k-balanced if $r\left(M\right)>\left(k\left(k+1\right)\right)/2$ and

${d}_{k}\left(M\right)\le {d}_{k}\left(M\right)$ (1)

for all non-empty submatroids $H⊑M$ and strictly k-balanced if the inequality is strict for all such H ≠ M. When k = 0, M is called balanced and when k = 1, M is called strongly balanced.

A random submatroid ${\omega }_{r}$ of the projective geometry $PG\left(r-1,q\right)$ is obtained from $PG\left(r-1,q\right)$ by deleting elements so that each element has, independently of all other elements, probability 1 − p of being deleted and probability 1 − p of being retained. In this paper, we take p to be a function p(r) of r. Let A be a fixed property which a matroid may or may not possess and ${P}_{r,p}\left(A\right)$ denotes the probability that ${\omega }_{r}$ has property A. We shall show that there are several properties A of k-balanced matroids for which there exists a function t(r) such that

$\underset{r\to \infty }{\mathrm{lim}}{P}_{r,p}\left(A\right)=\left\{\begin{array}{l}0,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\underset{r\to \infty }{\mathrm{lim}}\frac{P}{t\left(r\right)}=0\\ 1,\text{\hspace{0.17em}}\text{\hspace{0.17em}}\underset{r\to \infty }{\mathrm{lim}}\frac{P}{t\left(r\right)}=\infty \end{array}$

If such a function exists, it is called a threshold function for the property A. For more on these notions, the reader is referred   .

2. K-Balanced Matroids

In this section, we prove the following main result which is analogous to Theorem 1 of Erdös and Rényi  and to Theorem 1.1 of Kelly and Oxley  .

Theorem 1. Let m and n be fixed positive integers with n ≤ m and suppose that ${B}_{n,m}$ denote a non-empty set of k-balanced simple matroids, each of which have m elements and rank n and is representable over GF(q). Then a threshold function for the property B that ${\omega }_{r}$ has a submatroid isomorphic to some

member of ${B}_{n,m}$ is ${q}^{\frac{-rn}{m}}$ .

Proof. Let X and ${B}_{n,m}$ denote the number of submatroids of the matroid ${\omega }_{r}$ and $PG\left(n-1,q\right)$ respectively which are isomorphic to some member of ${B}_{n,m}$ . Then

${P}_{r,p}\left(B\right)=P\left(X\ne 0\right)\le EX$

by definition of expectation. Therefore

${P}_{r,p}\left(B\right)\le \left[\begin{array}{c}r\\ n\end{array}\right]{B}_{n,m}{p}^{m}\le {B}_{n,m}{p}^{m}{q}^{rn}\le {B}_{n,m}{\left(\frac{p}{{q}^{-\frac{rn}{m}}}\right)}^{m}$ .

Thus, if ${\mathrm{lim}}_{r\to \infty }\frac{p}{{q}^{-\frac{rn}{m}}}=0$ , then $\underset{r\to \infty }{\mathrm{lim}}{P}_{r,p}\left(B\right)=0$ .

Now suppose that ${\mathrm{lim}}_{n\to \infty }\frac{p}{{q}^{-\frac{rn}{m}}}=\infty$ . We need to show that, in this case, $\underset{n\to \infty }{\mathrm{lim}}{P}_{r,p}\left(B\right)=1$ . Let ${D}_{m,n}$ be the set of subsets A of $PG\left(r-1,q\right)$ for which the

restriction $PG\left(r-1,q\right)|A$ of $PG\left(r-1,q\right)$ to A is isomorphic to some member of ${B}_{n,m}$ . Then

$E{X}^{2}={\sum }_{{A}_{1}\in {D}_{m,n}}{\sum }_{{A}_{2}\in {D}_{m,n}}{p}^{|{A}_{1}\cup {A}_{2}|}={\sum }_{i=0}^{m}\text{ }\text{ }{p}^{m+i}{\propto }_{i}$ (2)

where ${\propto }_{i}$ equals the number of ordered pairs $\left({A}_{1},{A}_{2}\right)$ such that ${A}_{1},{A}_{2}\in {D}_{m,n}$ and $|{A}_{1}\cap {A}_{2}|=m-i$ . Thus

$E{X}^{2}\le {p}^{2m}\left[{\left({B}_{m,n}\left[\begin{array}{c}r\\ n\end{array}\right]\right)}^{2}+{\sum }_{i=0}^{m-1}\text{ }\text{ }{p}^{i-m}{\propto }_{i}\right].$

We now want to obtain upper bounds on the numbers ${\propto }_{0},{\propto }_{1},\cdots ,{\propto }_{m-1}$ , so suppose that ${A}_{1},{A}_{2}\in {D}_{m,n}$ and $|{A}_{1}\cap {A}_{2}|=m-i$ where $0\le i\le m-1$ . Then as $PG\left(r-1,q\right)|A$ is k-balanced,

$\left(|{A}_{1}\cap {A}_{2}|\right)/\left(r\left({A}_{1}\cap {A}_{2}\right)-k\right)\le m/\left(n-k\right)$

and so $r\left({A}_{1}\cap {A}_{2}\right)\ge \left(\left(m-i\right)\left(n-k\right)\right)/m+k$ . It follows that

$\begin{array}{c}r\left({A}_{2}\right)-r\left({A}_{1}\cap {A}_{2}\right)\le n-\left(\left(m-i\right)\left(n-k\right)\right)/m-k\\ =\left(i\left(n-k\right)\right)/m\le \left(in\right)/m\end{array}$

and hence $r\left({A}_{2}\right)-r\left({A}_{1}\cap {A}_{2}\right)\le ⌊\left(in\right)/m⌋$ where $⌊\left(in\right)/m⌋$ is the floor of $\left(in\right)/m$ .

Now ${\propto }_{i}={\beta }_{i}{\gamma }_{i}$ where ${\beta }_{i}$ is the number of ways to choose ${A}_{1}$ and ${\gamma }_{i}$ is the number of ways to choose ${A}_{2}$ so that $|{A}_{1}\cap {A}_{2}|=m-i$ , ${A}_{1}$ having already

been chosen. Clearly ${\beta }_{i}={B}_{m,n}\left[\begin{array}{c}r\\ n\end{array}\right]$ . Once ${A}_{1}$ has been chosen, there are at

most $\left({}_{m-i}{}^{m}\right)$ choices for the subset ${A}_{1}\cap {A}_{2}$ of ${A}_{1}$ . Further, once ${A}_{1}\cap {A}_{2}$ has been chosen, ${A}_{2}$ must be contained in some rank n subspace W of PG(r-1,q) which contain the chosen set ${A}_{1}\cap {A}_{2}$ . The number δ of such subspaces W is bounded above by

$\left(\left({q}^{r}-{q}^{s}\right)/\left(q-1\right)\right)\left(\left({q}^{r}-{q}^{s+1}\right)/\left(q-1\right)\right)\cdots \left(\left({q}^{r}-{q}^{n-1}\right)/\left(q-1\right)\right),$

where $s=r\left({A}_{1}\cap {A}_{2}\right)$ . Thus $\delta \le {q}^{r\left(n-1\right)}$ . But it was shown above that

$n-s\le ⌊\left(in\right)/m⌋$ ; hence $\delta \le {q}^{r⌊in/m⌋}.$ Once W has been chosen, there are at most ${B}_{m,n}$ choices for ${A}_{2}$ . We conclude that

${\gamma }_{i}\le \left({}_{m-i}{}^{m}\right){q}^{r⌊in/m⌋}{B}_{m,n}$

and hence

${\alpha }_{i}\le \left[\begin{array}{c}r\\ n\end{array}\right]{B}_{m,n}^{2}\left({}_{m-i}{}^{m}\right){q}^{r⌊in/m⌋}.$ (3)

Now as $EX=\left[\begin{array}{c}r\\ n\end{array}\right]{B}_{m,n}{p}^{m},$ we have by Equation (2), that

$\frac{E{X}^{2}}{{\left(EX\right)}^{2}}\le 1+{\left({B}_{m,n}\left[\begin{array}{c}r\\ n\end{array}\right]\right)}^{-2}+{\sum }_{i=0}^{m-1}\text{ }{p}^{i-m}{\propto }_{i}$ .

Hence, by Equation (2),

$\frac{E{X}^{2}}{{\left(EX\right)}^{2}}\le 1+{\left({B}_{m,n}\left[\begin{array}{c}r\\ n\end{array}\right]\right)}^{-2}+{\sum }_{i=0}^{m-1}\text{ }\text{ }{p}^{i-m}\left[\begin{array}{c}r\\ n\end{array}\right]{B}_{m,n}^{2}\left({}_{m-i}{}^{m}\right){q}^{r⌊\frac{in}{m}⌋}.$ .

Thus $\frac{E{X}^{2}}{{\left(EX\right)}^{2}}\le 1+{\sum }_{i=0}^{m-1}\text{ }\text{ }{p}^{i-m}\left({}_{m-i}{}^{m}\right)\frac{{q}^{r⌊\frac{in}{m}⌋}}{\left[\begin{array}{c}r\\ n\end{array}\right]}\le 1+{\sum }_{i=0}^{m-1}\text{ }\text{ }{p}^{i-m}\left({}_{m-i}{}^{m}\right)\frac{{q}^{r⌊\frac{in}{m}⌋}}{{q}^{n\left(r-n\right)}}$

Since $\left[\begin{array}{c}r\\ n\end{array}\right]\ge {q}^{n\left(r-n\right)}$ . Thus

$\frac{E{X}^{2}}{{\left(EX\right)}^{2}}\le 1+{\sum }_{i=0}^{m-1}\text{ }\text{ }{p}^{i-m}{q}^{-rn+r⌊\frac{in}{m}⌋}\left({}_{m-i}{}^{m}\right){q}^{{n}^{2}}.$ (4)

Now consider ${p}^{i-m}{q}^{-rn+r⌊\frac{in}{m}⌋}$ . We have

${q}^{-rn+r⌊\frac{in}{m}⌋}\le {q}^{-r\left(n-\frac{in}{m}\right)}={\left({q}^{rn/m}\right)}^{i-m}.$

Thus ${p}^{i-m}{q}^{-rn+r⌊\frac{in}{m}⌋}\le {\left(p{q}^{\frac{rn}{m}}\right)}^{i-m}$ . But ${\mathrm{lim}}_{r\to \infty }p{q}^{\frac{rn}{m}}=\infty ,$ hence ${\mathrm{lim}}_{r\to \infty }{\left(p{q}^{rn/m}\right)}^{i-m}=0$ for $0\le i\le m-1$ . It follows from Equation (4) that ${\mathrm{lim}}_{r\to \infty }\mathrm{sup}\frac{E{X}^{2}}{{\left(EX\right)}^{2}}\le 1$ ; hence ${\mathrm{lim}}_{r\to \infty }\frac{E{X}^{2}}{{\left(EX\right)}^{2}}=1$ . Therefore, by Chebyshev’s Inequality, ${\mathrm{lim}}_{r\to \infty }P\left(X\ne 0\right)=1$ . We conclude that ${q}^{\frac{-rn}{m}}$ is indeed a threshold function for the property B.

Corollary 1 If n is a fixed positive integer, then a threshold function for the property that ${\omega }_{r}$ has an n-element independent set is ${q}^{-r}$ .

Corollary 2 If m is a fixed positive integer exceeding two, then a threshold

function for the property that ${\omega }_{r}$ has an m-element circuit is ${q}^{\frac{-r\left(m-1\right)}{m}}$ .

Corollary 3 If n is a fixed positive integer, then a threshold function for the property that ${\omega }_{r}$ contains a submatroid isomorphic to $PG\left(n-1,q\right)$ is

${q}^{\frac{-rn\left(q-1\right)}{{q}^{n}-1}}$ .

To show that the preceding three results are valid, we are required to check that the appropriate submatroids are k-balanced. For example, in Corollary 1, the n-element independent set must be k-balanced; this is the free matroid ${U}_{n,n}$ . Corollary 2 requires one to verify that an m-element circuit is k-balanced; this is precisely the uniform matroid ${U}_{m-1,m}$ , while in Corollary 3, the projective geometry $PG\left(n-1,q\right)$ needs to be k-balanced. For a more thorough discussion of this material, the reader is referred to Proposition 2 and Theorem 5 in  .

Conflicts of Interest

The authors declare no conflicts of interest.

  White, N. (1986) Theory of Matroids. Cambridge University Press, New York.  Oxley, J. (1992) Matroid Theory. Oxford University Press, Oxford.  Al-Hawary, T. (2007) A New Class of Matroids. African Diaspora of Math, 4, 87-91.  Al-Hawary, T. (2017) Certain Classes of Fuzzy Graphs. European Journal of Pure and Applied Mathematics, 10, 552-560.  Al-Hawary, T. (2002) Characterizations of Certain Matroids via Flats. Journal of Automata, Languages and Combinatorics, 7, 295-301.  Al-Hawary, T. (2001) Characterization of Matroids via OFR-Sets. Turkish Journal of Math, 24, 1-11.  Al-Hawary, T. and McNulty, J. (2001) Closure Matroids. Congressuss Nemerantuem, 148, 93-95.  Al-Hawary, T. (2004) Closure Matroid Properties. Mu’tah Lil-Buhuth Wad-Dirasat, 19, 35-43.  Al-Hawary, T. (2003) Feeble-Matroids. Italian Journal of Pure and Applied Mathematics, 14, 87-94.  Al-Hawary, T. (2000) On Balanced Graphs and Balanced Matroids. Mathematical Sciences Research Hot-Line, 4, 35-45.  Al-Hawary, T. (2001) On k-Balanced Matroids. Mu’tah Lil-Buhuth wad-dirasat-Natural and Applied Sciences Series, 16, 15-22.  Al-Hawary, T. and Horani, B. (2016) On Product Fuzzy Graphs. Annals of Fuzzy Mathematics and Informatics, 12, 279-294.  Al-Hawary, T. and Horani, B. (2017) On Product Intuitionistic Fuzzy Graphs. Italian Journal of Pure and Applied Mathematics.  Narayanan, H. and Vartak, M. (1981) On Molecular and Atomic Matroids. In: Combinatorics and Graph Theory, Vol. 885, Springer, New York, 358-364.  White, N. (1992) Matroid Applications. Cambridge University Press, Cambridge.  Erdös, P. and Rényi, A. (1961) On the Strength of Connectedness of a Random Graph. Acta Mathematica Academiae Scientiarum Hungaricae, 12, 261-267. https://doi.org/10.1007/BF02066689  Kelly, D. and Oxley, J. (1981) Threshold Functions for Some Properties of Random Subsets of Projective Spaces. The Quarterly Journal of Mathematics, 32, 463-469.     customer@scirp.org +86 18163351462(WhatsApp) 1655362766  Paper Publishing WeChat 