Abstract
The class spike is an important class of 3-connected matroids. For an integer , each matroid that is obtained by relaxing one of the circuit-hyperplanes of an r-spike (spike with rank r) is isomorphic to another r-spike and repeating this procedure will produce other r-spikes. So it will be useful to characterize the collection of circuit-hyperplanes of a spike. In this paper, we first introduce a technique to characterize the only two ternary r-spikes in terms of their matrix representations, circuit-hyperplanes, and -circuits and then we generalize this technique to characterize the class of r-spikes that is representable over the field GF(p), for all primes p. Moreover, we pose a conjecture which would characterize the class of all r-spikes by using all GF(p)-representable r-spikes.
KEYWORDS:
2000 MSC:
1 Introduction
Spikes play an important role in matroid theory. They have been used as a counterexample for many conjectures. So one needs to find the structure of all -representable spikes with rank r (It is denoted by r-spike and ) in terms of matrix representation and, in particular, circuit-hyperplanes. Wu [Citation6] evaluated the number of GF(p)-representable r-spikes, for p in . He also found the asymptotic value of the number of distinct r-spikes that are representable over GF(p) when p is prime. Moreover, Wu [Citation7] showed that a GF(p)-representable r-spike M is only representable over fields with characteristic p provided that and M is uniquely representable over GF(p). In our first paper about spikes [Citation2], we showed that all binary spikes and many non-binary spikes of each rank can be derived from the Fano matroid by a sequence of es-splitting operations and circuit-hyperplane relaxations. In this paper, our main goal is to find the structure of all GF(p)-representable r-spikes in terms of their collections of circuits and matrix representations.
Let for some . Let and . The set of circuits of every spike on E includes . Let be a, possibly empty, subset of such that no two members of have more than r – 2 common elements. Finally, let be the collection of all -element subsets of E that contain no member of . There is a rank-r matroid M on E whose collection of circuits is [Citation4] and the matroid M is called an r-spike with tip t and legs where for all i. In an arbitrary spike M, each circuit in is also a hyperplane of M and when such a circuit-hyperplane is relaxed, we obtain another spike. If is empty, the corresponding spike is called the free r-spike with tip t.
For , let be an matrix over GF(2) whose columns are labeled, in order, where Jr and are the r × r and matrices of all ones, respectively. This matrix represents the unique binary r-spike. Moreover, if we interchange GF(2) and GF(p), for p prime, then we obtain a matrix representation for one of GF(p)-representable r-spikes. But we cannot apply the es-splitting operation on such r-spikes to construct other -spikes since this operation is only defined for binary matroids.
Let E be the ground set of a GF(p)-representable spike M. We wish to determine what subsets of E are members of or and how we can obtain a matrix representing M. This leads to computing the number of circuit-hyperplanes of M and producing many spikes from M which are not GF(p)-representable, by relaxing operation.
Let be a field and be non-zero elements of . Let be the matrix of all ones, and let (1) (1)
Geelen, Gerards, and Whittle [Citation1] described the following key result for the representability of spikes.
Proposition 1.
Suppose that and is a field. Let M be an -representable r-spike with legs such that is independent. Then every -representation of M is projectively equivalent to a matrix of the form whose columns are labeled, in order, , where Ar is as in (1). Moreover, for , the set is a circuit of M if and only if .
The following result of Oxley and Whittle [Citation5] gives a necessary and sufficient condition for a matroid that is obtained by relaxing operation to be ternary.
Proposition 2.
Let M be a matroid that is obtained by relaxing a circuit-hyperplane H in a ternary matroid N. Then M is ternary if and only if N is isomorphic to the cycle matroid of a graph that is obtained from a cycle with edge set H by adjoining an extra vertex v and then adding some non-zero number of edges from v to the vertices of H.
Proposition 3.
[Citation6] For each integer , there are exactly two distinct ternary r-spikes.
We refer to Oxley [Citation4] for basic definitions not given in this paper such as matrix representations of matroids, properties of circuits and hyperplanes of matroids and good information about spikes.
2 Characterization of ternary spikes
Let r be an integer exceeding two. Let M be the vector matroid of the matrix over GF(p) for p prime where the columns of this matrix are labeled, in order, and Ar is as in (1). Then, by Proposition 1, M is a GF(p)-representable r-spike. We denote this matroid by Mr and call it the r-spike with respect to Ar over GF(p).
Now let p = 3. By Proposition 2 and the fact that there is no graphic spike, we conclude that all spikes that are obtained from an Mr by relaxing operation are non-ternary. Thus we can find the two non-isomorphic ternary r-spikes by changing some of the diagonal entries of Ar from 0 to –1 and vice versa. In this section, we introduce one way to find all members of for Mr. Moreover, if Nr is the r-spike with respect to over GF(3) such that is as in (1) with diagonal entries different from Ar, then, by counting the number of circuit-hyperplanes of Mr and Nr, we can determine whether Mr and Nr are isomorphic or not. This will lead to characterize the two ternary r-spikes.
For this section, we let X and Y be disjoint r-element sets and , respectively. We also let i in , j in {1, 2}, and for p prime, two integers k and are in .
Definition 4.
Let be a prime field GF(p) and r be an integer exceeding two. For each , with we define (2) (2)
For all distinct k and , we have and . So is a partition of . We say that such partition is a GF(p)-partition of r.
Definition 5.
Let be the set defined in Definition 4. For all primes p, the field GF(p) coincides with , the ring of integers modulo p. Thus, all members of are congruent to p – k modulo p. We denote this value by and call it GF(p)-trace of .
Let Mr be an r-spike with respect to Ar over GF(3). Then . Let be the ordered r-tuples of diagonal entries of Ar such that βi is a corresponding entry in the ith row and column of Ar. Then, for all i, we have , so . We denote by the set of non-zero elements of B.
Let be a partition of Y such that if , then , otherwise where Y1 or Y2 may be empty. This partition is unique and we call it GF(3)-partition of Y. Now the GF(3)-partition of r is where (3) (3)
For an r-spike Mr with respect to Ar over GF(p), we denote by -element set the subset of that has cardinality r and contains at most one element of each for all i.
Theorem 6.
Let Mr be an r-spike with respect to Ar over GF(3). Let be the GF(3)-partition of Y. An -element set is a circuit-hyperplane of Mr if and only if it is a member of one of the following sets:
;
; or
.
Proof.
Let Mr be an r-spike with respect to Ar over GF(3). Let be the GF(3)-partition of Y where . For , consider the GF(3)-partition of r which is so that the GF(3)-trace of is (4) (4)
Let for all i, if , then and , and if , then and where βi is a corresponding entry in the ith row and column of Ar. Hence is the number of αi whose values are –1 and is the number of αi whose values are 1.
Let Z be an -element set and let I be the set of all indexes of . Suppose that and . Then, By (4), The numbers and are congruent to 0 and –1 modulo 3, respectively. Therefore (5) (5)
Moreover, the columns of the matrix are labeled, in order, . Hence, the set is an independent set of Mr and so, by Proposition 1, Z is a circuit of Mr. Also, as Mr is an r-spike, the set Z is a hyperplane of Mr. Now let Z be a member of one of the sets listed in (ii) or (iii). Then, a similar argument establishes that Z is a circuit-hyperplane of Mr.
To complete the proof, we need to show that if is an -element set that is not in , then is not a circuit-hyperplane of Mr. Assume the contrary and let . Then the number of αi in diagonal entries of Ar with values 1 and –1 are m and r – m, respectively. Therefore and . Suppose that such that and , and let . Then is a member of one of such that , and . Thus, (6) (6)
Where is the set of all indexes of . By Proposition 1, The set can not be a circuit-hyperplane of Mr; a contradiction. □
Note that, if , then and so the sets of all circuit-hyperplanes of Mr is , and if , then and therefore the sets of all circuit-hyperplanes of Mr is .
Corollary 7.
Let Mr be an r-spike with respect to Ar over GF(3). Let . Then the number of circuit-hyperplanes of M is (7) (7)
Proof.
Since , It follows that and . Thus by Theorem 6, Part (i), the number of h-combinations from m such that is and the number of l-combinations from r – m such that is . Now, the number of all circuit-hyperplanes in Part (i) is equal to the sum over all combinations which is . For a similar reason, the number of circuit-hyperplanes of M in Parts (ii) and (iii) are and , respectively. □
Theorem 8.
Let Mr be an r-spike with respect to Ar over GF(3). Let be the GF(3)-partition of Y. A union of an -element set which is not a circuit-hyperplane and one element of is an -circuit of Mr if and only if it is a member of one of the following sets:
for all ; or
.
Proof.
Let Mr be an r-spike with respect to Ar over GF(3). Let be the GF(3)-partition of Y where . Consider the GF(3)-partition of r which is and let Z be an -element set. Suppose that where for all j in {1, 2} and . By (6), Z is not a circuit-hyperplane of Mr and, by the fact that , the set Z does not contain any leg and circuit of the form for . We conclude that Z is an independent set and Mr has a unique circuit contained in , and this circuit contains z. If z = t, then clearly is an -circuit of Mr. Now suppose that and such that and let . Then and . Clearly, the set does not contain any leg and circuit of the form for and, by (6), the set is not a circuit-hyperplane of Mr. Therefore is an -circuit of Mr. To complete the proof we must show that when , the set is not a circuit of Mr. To see this, assume the contrary and let such that . Then and . Thus, by Theorem 6, is a circuit-hyperplane of Mr; a contradiction. Moreover, if such that , then and and so, by Theorem 6 again, is a circuit-hyperplane of Mr; a contradiction.
Finally, suppose and where , then and . Therefore, the set is a member of one of the sets listed in (ii) and one can continue this process to prove that all members of the set in (ii) are -circuits of Mr. □
Note that, if , then and so the sets of all -circuit of Mr is the union of the sets consists of
;
.
Moreover, if , then and therefore the sets of all -circuits of Mr is the union of the sets consists of
;
.
The proof of the following result can be done using an argument similar to Corollary 7, on Parts (i) and (ii) of Theorem 8.
Corollary 9.
Let Mr be an r-spike with respect to Ar over GF(3). Let and be a pair of numbers such that . Then the number of -circuits of M is (8) (8)
By the fact that there are exactly two ternary r-spikes, any of the summation formulae (7) and (8) has exactly two different values. Next, we establish a characterization of these two ternary spikes.
Definition 10.
[Citation3] For integers q and d such that , the following identity is the sum of binomial coefficients with step c and is called the series multisection. (9) (9)
By Definition 10, one can find the following relations. (10) (10) (11) (11)
and (12) (12)
For an r-spike Mr with respect to Ar, we denote by the number of circuit-hyperplanes of Mr.
Theorem 11.
Let Mr and Nr be two r-spikes with respect to two matrices Ar and Br over GF(3), respectively, where and . Suppose 3 does not divide r. Then .
Proof.
Since 3 does not divide r, we have or , for . First let . As and , On combining Corollary 7 with (10) and (11), we obtain the following. (13) (13) and (14) (14)
Therefore (15) (15)
A similar argument establishes the following result when . (16) (16)
We conclude that , so . □
Theorem 12.
Let Mr, Nr and Or be three r-spikes with respect to three matrices Ar, Br, and Cr over GF(3), respectively. Let and and let 3 divide r. Then .
Proof.
Since 3 divides r, we have , for . Moreover, as and , by Corollary 7, (17) (17) and (18) (18)
and (19) (19)
Clearly, . To complete the proof, it suffices to show that, . By applying the argument in the proof of the Theorem 11, we have (20) (20) and this completes the proof of the theorem. □
As an immediate consequence of the two last theorems, we have the following result
Corollary 13.
Let Mr and Nr be two non-isomorphic ternary spikes. Then .
Proof.
Let Mr, Nr be two non-isomorphic ternary r-spikes with respect to two matrices Ar, Br. We now distinguish two cases:
The number 3 divides r. In this case, by Theorem 11, we let two matrices Ar and Br with and . Thus, by (15) and (16), we have .
The number 3 does not divide r over GF(3). In this case, by Theorem 12, we let two matrices Ar and Br with or 0 and . Thus, by (20), we have .
Finally, suppose that be two ternary r-spikes with respect to two matrices such that where . Then, by applying the argument in Theorems 11, 12, and using Corollary 7 and the series multisection, one can check whether or not two spikes are isomorphic. Now, if , Then and are projectively equivalent to one of Ar and Br in cases (a) and (b). This means . □
3 On GF(p)-representable spikes
In this section, we investigate GF(p)-representable r-spikes for p prime, focusing particularly on the question of whether the algorithm on Section (2) can be generalized to such spikes. In other words, for an r-spike Mr with respect to Ar over GF(p), can we find all circuit-hyperplanes and all -circuits of Mr? Moreover, for , if Nr is another r-spike with respect to Ar over GF(q), then, for which values of r and q, two spikes Mr and Nr are the same matroid?
Let Mr be an r-spike with respect to Ar over GF(p). Then Mr is the vector matroid of the matrix whose columns are labeled, in order, and is the ordered r-tuples of diagonal entries of Ar such that βi is a corresponding entry in the ith row and column of Ar. Thus, B is an r-tuples of distinct non-unit elements of GF(p). Let and be the GF(p)-partition of Y, either of which may be empty, such that if for , then , and if , then , where . We denote by the set of elements of B whose values are 0 and the set of non-zero elements of B whose values are q. Now consider the GF(p)-partition of r which is where (21) (21)
The following lemmas will be useful to answer our questions about the r-spike Mr with the notation defined above. Note that, every circuit-hyperplane of a spike M is an -element set and every -circuit of M is also the union of an -element set Z and one element of . Therefore, we expect readers to identify the -element sets in the following.
Lemma 14.
If , then the collection of all circuit-hyperplanes of Mr is (22) (22)
Proof.
Let Z be a member of (22) and I be the set of all indexes of and let . Then, and . Thus, (23) (23)
Since and , we deduce that modulo p. It is easy to see that modulo p, for non-unit element q of GF(p). Hence, by Proposition 1, the collection of all circuit-hyperplanes of Mr is (22). □
Lemma 15.
If , then the collection of all -circuit of Mr is (24) (24)
Proof.
Let Z be an -element set such that , for and let I be the set of all indexes of . Then and therefore modulo p. Hence, by Proposition 1, the set Z is not a circuit-hyperplane of Mr. Moreover, Z is an independent set since for all i and . Therefore Mr has a unique circuit contained in , and this circuit contains z where . Clearly is an -circuit of Mr. Now suppose that for and where , for . Let . Then . By Lemma 14, the set is not a circuit-hyperplane of Mr and does not contain any leg and circuit of the form for . Thus, is an -circuit of Mr.
To complete the proof, let and . Then, for all yj in , we have and therefore contains a circuit-hyperplane of Mr; a contradiction. We conclude that in this case . Moreover, for , if be in X – Z where , then and so Z is a circuit-hyperplane of Mr or we get a repetitive member of collection in (24). □
On combining the last two lemmas, we obtain the following result to answer the second question that is stated in the first paragraph of this section.
Theorem 16.
Let be the ordered set of prime numbers. Let for some i. Then, for all , the matrix with over GF(q) represents the same matroid if and only if where q, and pi are in P.
Proof.
Let pi be a member of P. Let be the r-spikes with respect to Ar over , respectively, such that and . For all q in , we have (25) (25)
Suppose that is the greatest prime number such that and let . Then . Thus, by Lemma 14, for all l in , the collection of all circuit-hyperplanes of is (26) (26)
Moreover, by using Lemma 15 and applying the above argument, the collection of all -circuits of is (27) (27)
We deduce that . □
Next, we show how Lemmas 14 and 15 can be extended to give a characterization of the circuit-hyperplanes and -circuits of an r-spike Mr with respect to Ar when for .
Lemma 17.
If for , then the collection of all circuit-hyperplanes of Mr is (28) (28)
Proof.
Clearly, and . For all i in , we have . The set is and so . Let Z be a member of (28) and I be the set of all indexes of . Then (29) (29)
Since the inverse of q is unique, by Proposition 1, we conclude that the collection of all circuit-hyperplanes of Mr is (28) □
Lemma 18.
If for , then the collection of all -circuits of Mr is (30) (30)
Proof.
Let be a member of (30). Then, by Lemma 17, Z is not a circuit-hyperplane of Mr and by the fact that , for , Z contains no legs and 4-circuits of Mr. So Z is an independent set and contains a circuit of Mr. Clearly is an -circuit of Mr. Now suppose that for and such that . Then with . By Lemma 17, the set is not a circuit-hyperplane of Mr and so is an -circuit. Moreover, if and such that . Then and so is not an -circuit of Mr. □
Now suppose that Mr is an r-spike with respect to Ar over GF(p) for some prime number p. Let the columns of the matrix are indexed by . The GF(p)-partitions of r and Y where are and , respectively. Let and for all q in . Then (31) (31)
Let be ordered -tuples of distinct members of GF(p) such that for j in . We define as a collection of -element sets of as follows. (32) (32)
Note that, for all k in , the GF(p)-trace of is . So (33) (33)
Summarizing the above discussion, we have the following theorem, one of the main result of this section about Mr.
Theorem 19.
Let Z be a member of . Then it is a circuit-hyperplane of Mr if and only if (34) (34)
Proof.
Let Z be a member of . Then and there is a such that . By Proposition 1, the set Z is a circuit of Mr if and only if . Consider is the ordered r-tuples of diagonal entries of Ar such that βi is a corresponding entry in the ith row and column of Ar. By using the fact , we have when and when , for (finding αi in this case will depend on choice of P). Suppose and be the numbers of βi which is equal to 0 and j, respectively. Then it is straightforward to check that (35) (35)
Moreover, since Mr is an r-spike, the set Z is a circuit-hyperplane. □
The next example illustrates the use of the last theorem to find all circuit-hyperplane of an r-spike with respect to Ar over GF(p).
Example 20.
Let M be a 6-spike with matrix representation over GF(5), whose columns are indexed and let the ordered 6-tuples of diagonal entries of A6 be . Then the GF(5)-partitions of Y with is (36) (36)
This means (37) (37)
Now consider the GF(5)-partitions of r and let be ordered 4-tuples such that where , and . Thus, by (35), (38) (38)
Since , we have . The following table is obtained by combining (38) and (33).
Table
Therefore all circuit-hyperplanes of M are
An interesting application of the existing algorithm in this article for identifying the structure of GF(p)-representable spikes is that we may be able to establish it in the SageMath program, for p prime. For example, one can investigate the structure of a GF(p)-representable r-spike by type the first command as S = matroids.Spike(r,p).
We end this article by proposing a conjecture and a problem that may enable us to prove the conjecture. We know that when a circuit–hyperplane of a spike is relaxed, we obtain another spike and repeating this procedure until all of the circuit–hyperplanes of a spike have been relaxed will produce the free spike. For and some prime p, let be the class of all GF(p)-representable r-spikes such that no members of it are not obtained from another r-spike by a sequence of the relaxing operations. In the following conjecture, we claim that all members of the class of all r-spikes can be constructed from all members of .
Conjecture 21. Let be the class of all r-spikes. Then, by applying a sequence of relaxing operations on circuit-hyperplanes of each member of until we arrive at the free r-spike, we can find all members of .
As an example to illustrate this guess, let r = 3. Then and in , you can see the diagram of the geometric representations of the only six 3-spikes that are obtained by sequences of relaxing operations with starting from the binary 3-spike F7 and ternary 3-spike P7.
The following diagram provides another illustration of Conjecture 21 for finding all r-spike by applying sequences of relaxing operation on members of .
We end this paper with the following problem and we think that this conjecture can be proved if we can solve the following problem about relaxing operation ().
Problem 22.
For p prime, let M be a GF(p)-representable matroid and let H be a circuit-hyperplane of M. Let N be a matroid that is obtained from M by relaxing H. For which filed the matroid N is -representable?
References
- Geelen, J. F., Gerards, A. M. H., Whittle, G. (2002). Branch-width and well-quasi-ordering in matroids and graphs. J. Comb. Theory Ser. B 84(2): 270–290.
- Ghorbani, V., Azadi, G., Azanchiler, H. (2020). On the structure of spikes. AKCE Int. J. Graphs Comb. 17(3): 883–886.
- Gradshteyn, I. S., Ryzhik, I. M. (2014). Table of Integrals, Series, and Products. 8th ed. New York: Academic Press.
- Oxley, J. G. (2011). Matroid Theory. Vol. 21, 2nd ed. New York: Oxford University Press.
- Oxley, J., Whittle, G. (1998). On weak maps of ternary matroids. Eur. J. Comb. 19(3): 377–389.
- Wu, Z. (2003). On the number of spikes over finite fields. Discrete Math. 265(1–3): 261–296.
- Wu, Z., Sun, Z.-W. (2006). On the unique representability of spikes over prime fields. Discrete Math. 306(15): 1798–1804.