Open Journal of Discrete Mathematics
Vol.07 No.03(2017), Article ID:76702,5 pages
10.4236/ojdm.2017.73011
On Functions of K-Balanced Matroids
Talal Al-Hawary
Department of Mathematics, Yarmouk University, Irbid, Jordan
Copyright © 2017 by author and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: March 31, 2017; Accepted: May 29, 2017; Published: June 1, 2017
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:
K-Balanced, Matroid, Projective Geometry, Threshold Function
1. Introduction
We begin with some background material, which follows the terminology and notation in [1] . Let 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 of rank-n subspaces of the projective
geometry PG (r − 1, q) is
The uniform matroid of rank r and size n is denoted by where
. When r = n, the matroid is called free and when r = n = 0, the matroid 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 , 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 and
(1)
for all non-empty submatroids 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 of the projective geometry is obtained from 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 denotes the probability that 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
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 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 has a submatroid isomorphic to some
member of is .
Proof. Let X and denote the number of submatroids of the matroid and respectively which are isomorphic to some member of . Then
by definition of expectation. Therefore
.
Thus, if , then .
Now suppose that . We need to show that, in this case, . Let be the set of subsets A of for which the
restriction of to A is isomorphic to some member of . Then
(2)
where equals the number of ordered pairs such that and . Thus
We now want to obtain upper bounds on the numbers , so suppose that and where . Then as is k-balanced,
and so . It follows that
and hence where is the floor of .
Now where is the number of ways to choose and is the number of ways to choose so that , having already
been chosen. Clearly . Once has been chosen, there are at
most choices for the subset of . Further, once has been chosen, must be contained in some rank n subspace W of PG(r-1,q) which contain the chosen set . The number δ of such subspaces W is bounded above by
where . Thus . But it was shown above that
; hence Once W has been chosen, there are at most choices for . We conclude that
and hence
(3)
Now as we have by Equation (2), that
.
Hence, by Equation (2),
.
Thus
Since . Thus
(4)
Now consider . We have
Thus . But hence for . It follows from Equation (4) that ; hence . Therefore, by Chebyshev’s Inequality, . We conclude that 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 has an n-element independent set is .
Corollary 2 If m is a fixed positive integer exceeding two, then a threshold
function for the property that has an m-element circuit is .
Corollary 3 If n is a fixed positive integer, then a threshold function for the property that contains a submatroid isomorphic to is
.
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 . Corollary 2 requires one to verify that an m-element circuit is k-balanced; this is precisely the uniform matroid , while in Corollary 3, the projective geometry 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] .
Cite this paper
Al-Hawary, T. (2017) On Functions of K-Balanced Matroids. Open Journal of Discrete Mathema- tics, 7, 103-107. https://doi.org/10.4236/ojdm.2017.73011
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.