On Functions of K-Balanced Matroids

Show more

1. Introduction

We begin with some background material, which follows the terminology and notation in [1] . 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 [2] ) 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 [1] - [15] . 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{\left|M\right|}{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\u2291M$ 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)=\{\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 [16] [17] .

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 [16] and to Theorem 1.1 of Kelly and Oxley [17] .

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}={\displaystyle {\sum}_{{A}_{1}\in {D}_{m,n}}{\displaystyle {\sum}_{{A}_{2}\in {D}_{m,n}}{p}^{\left|{A}_{1}\cup {A}_{2}\right|}}}={{\displaystyle \sum}}_{i=0}^{m}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{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 $\left|{A}_{1}\cap {A}_{2}\right|=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}+{{\displaystyle \sum}}_{i=0}^{m-1}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{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 $\left|{A}_{1}\cap {A}_{2}\right|=m-i$ where $0\le i\le m-1$ . Then as $PG\left(r-1,q\right)|A$ is k-balanced,

$\left(\left|{A}_{1}\cap {A}_{2}\right|\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 \lfloor \left(in\right)/m\rfloor $ where $\lfloor \left(in\right)/m\rfloor $ 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 $\left|{A}_{1}\cap {A}_{2}\right|=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 \lfloor \left(in\right)/m\rfloor $ ; hence $\delta \le {q}^{r\lfloor in/m\rfloor}.$ 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\lfloor in/m\rfloor}{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\lfloor in/m\rfloor}.$ (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}+{{\displaystyle \sum}}_{i=0}^{m-1}\text{\hspace{0.05em}}{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}+{{\displaystyle \sum}}_{i=0}^{m-1}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{p}^{i-m}\left[\begin{array}{c}r\\ n\end{array}\right]{B}_{m,n}^{2}\left({}_{m-i}{}^{m}\right){q}^{r\lfloor \frac{in}{m}\rfloor}.$ .

Thus $\frac{E{X}^{2}}{{\left(EX\right)}^{2}}\le 1+{{\displaystyle \sum}}_{i=0}^{m-1}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{p}^{i-m}\left({}_{m-i}{}^{m}\right)\frac{{q}^{r\lfloor \frac{in}{m}\rfloor}}{\left[\begin{array}{c}r\\ n\end{array}\right]}\le 1+{{\displaystyle \sum}}_{i=0}^{m-1}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{p}^{i-m}\left({}_{m-i}{}^{m}\right)\frac{{q}^{r\lfloor \frac{in}{m}\rfloor}}{{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+{{\displaystyle \sum}}_{i=0}^{m-1}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{p}^{i-m}{q}^{-rn+r\lfloor \frac{in}{m}\rfloor}\left({}_{m-i}{}^{m}\right){q}^{{n}^{2}}.$ (4)

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

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

Thus ${p}^{i-m}{q}^{-rn+r\lfloor \frac{in}{m}\rfloor}\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 [2] .

References

[1] White, N. (1986) Theory of Matroids. Cambridge University Press, New York.

[2] Oxley, J. (1992) Matroid Theory. Oxford University Press, Oxford.

[3] Al-Hawary, T. (2007) A New Class of Matroids. African Diaspora of Math, 4, 87-91.

[4] Al-Hawary, T. (2017) Certain Classes of Fuzzy Graphs. European Journal of Pure and Applied Mathematics, 10, 552-560.

[5] Al-Hawary, T. (2002) Characterizations of Certain Matroids via Flats. Journal of Automata, Languages and Combinatorics, 7, 295-301.

[6] Al-Hawary, T. (2001) Characterization of Matroids via OFR-Sets. Turkish Journal of Math, 24, 1-11.

[7] Al-Hawary, T. and McNulty, J. (2001) Closure Matroids. Congressuss Nemerantuem, 148, 93-95.

[8] Al-Hawary, T. (2004) Closure Matroid Properties. Mu’tah Lil-Buhuth Wad-Dirasat, 19, 35-43.

[9] Al-Hawary, T. (2003) Feeble-Matroids. Italian Journal of Pure and Applied Mathematics, 14, 87-94.

[10] Al-Hawary, T. (2000) On Balanced Graphs and Balanced Matroids. Mathematical Sciences Research Hot-Line, 4, 35-45.

[11] Al-Hawary, T. (2001) On k-Balanced Matroids. Mu’tah Lil-Buhuth wad-dirasat-Natural and Applied Sciences Series, 16, 15-22.

[12] Al-Hawary, T. and Horani, B. (2016) On Product Fuzzy Graphs. Annals of Fuzzy Mathematics and Informatics, 12, 279-294.

[13] Al-Hawary, T. and Horani, B. (2017) On Product Intuitionistic Fuzzy Graphs. Italian Journal of Pure and Applied Mathematics.

[14] Narayanan, H. and Vartak, M. (1981) On Molecular and Atomic Matroids. In: Combinatorics and Graph Theory, Vol. 885, Springer, New York, 358-364.

[15] White, N. (1992) Matroid Applications. Cambridge University Press, Cambridge.

[16] 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

[17] 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.