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