Bull. Korean Math. Soc. 52 (2015), No. 3, pp. 955–962 http://dx.doi.org/10.4134/BKMS.2015.52.3.955
H-TREES, RESTRICTIONS OF DOWLING GROUP GEOMETRIES
Eunice Mphako-Banda
Abstract. It has been established that the role played by complete graphs in graph theory is similar to the role Dowling group geometries and Projective geometries play in matroid theory. In this paper, we in- troduce a notion of H-tree, a class of representable matroids which play a similar role to trees in graph theory. Then we give some properties of H-trees such that when q = 0, then the results reduce to the known prop- erties of trees in graph theory. Finally we give explicit expressions of the characteristic polynomials of H-trees, H-cycles, H-fans and H-wheels.
1. Introduction
Matroid theory has been developed mainly out of a deep examination of the properties of independence and dimension in vector spaces. A second origi- nal source for the theory of matroids is graph theory. Hence matroid theory borrows extensively from the terminology of linear algebra and graph theory.
One research area in matroid theory is to extend results from graph theory to matroids. The biggest challenge in this research area is that there is no real notion of a vertex for a matroid. Irrespective of this hurdle, some concepts of graphs have been extended successfully to matroids. For example, the notion of vertex-join has been extended to matroids as q-cones in projective geometries [8] and as H-lifts in Dowling geometries in [5]. Other concepts like Eurelian, bipartite, chromatic polynomial, Tutte polynomial just to mention a few have been defined for matroids, for which we refer the reader to [2, 4, 7].
In graph theory, complete graphs and trees play a big role in the study of graphs. It has been established that the role played by complete graphs in graph theory is similar to the role Dowling group geometries and Projective geometries play in matroid theory. What do we know about classes of matroids playing a role similar to trees in graph theory? It has been established that a
Received June 10, 2014; Revised September 2, 2014.
2010 Mathematics Subject Classification. Primary 05B35, 05C31; Secondary 05C05, 05C07.
Key words and phrases. Dowling group geometry, matroid, tree, characteristic poly- nomial.
Supported wholly by the National Research Foundation of South Africa, Grant no. 86330.
c
2015 Korean Mathematical Society 955
rank r uniform matroid is isomorphic to a cycle matroid of a tree with r edges, but this does not answer our question.
In this paper, we investigate a class of representable matroids playing a role similar to trees in graph theory. We introduce a class of matroids called H- trees, give some properties of H-trees which reduces to known properties of trees in graph theory if q = 0. Then we use the concept of H-trees to define H-cycles, H-fans and H-wheels. Finally, we derive explicit expressions of the characteristic polynomials of these matroids.
2. Representable matroids
We outline the properties of Dowling group geometries that we need in this paper. Then we define a representable matroid and some terminology to be used in the paper. For further details, we refer the reader to [3, 6].
A matroid M (E) is a set E with a rank function r, for which the following properties hold:
(i) If X ⊆ E, then 0 ≤ r(X) ≤ |X|.
(ii) If X ⊆ Y ⊆ E, then r(X) ≤ r(Y ).
(iii) If X and Y are subsets of E, then
r(X ∪ Y ) + r(X ∩ Y ) ≤ r(X) + r(Y ).
A matroid can be defined by its set of independent sets, set of circuits, set of bases, rank function and closure operator. All these different ways of defin- ing a matroid are equivalent. A rank-r Dowling group geometry over a finite group H, denoted by Qr(H), has two kinds of points and three types of lines;
coordinate pointsb1, b2, . . . , br which form a basis, these points are also known as the joints of Qr(H); non-coordinate points hij for every h ∈ H and ev- ery pair of indices 1 ≤ i < j ≤ r such that hij ∈ cl{bi, bj}; coordinate lines bi∨ bj= bi∪ bj∪ {hij|h ∈ H}; transversal lines {hij, gjk, (hg)ik} for each pair h, g ∈ H residing on intersecting coordinate lines and trivial lines connecting any two points not already on a common line. It is clear from this definition that a rank-r Dowling group geometry over a finite group H is a matroid. A matroid M is representable over a group H if M is isomorphic to Qr(H)|S for some subset S.
Note. We will use the following terminology, for any matroid M ∼= Qr(H)|S, a coordinate lineis said to be empty if it has no non-coordinate points, otherwise the coordinate line is said to be non-empty.
We will borrow some terminology from graph theory throughout this paper and define it for representable matroids.
Definition. The degree of a joint, bi, of a representable matroid is the number of non-empty coordinate lines incident with the joint, denoted by d(bi). It is clear from this definition that the degree of each joint for a rank r Dowling geometry is r − 1.
3. H-trees
Trees are a class of graph which plays a central role in graph theory. In this section we mimick the definition and some properties of trees in graph theory for representable matroids. We will start by defining a complete H-tree and then we generalize to what we shall call an H-tree.
Definition. Let Qr(H) be a rank-r Dowling group geometry over a finite group H of order q, with joints b1, b2, . . . , br. Let r ∈ Z such that q ≥ 1, r > 1, u < r and let a rank-r matroid M = Qr(H)|S such that joints b1, b2, . . . , bu∈ S. We define the matroid M to be a complete H-tree if the following properties hold:
(i) there are r − 1 non-empty coordinate lines with exactly q + 2 points;
(ii) for each triple {bi, bj, bk} ⊆ {b1, b2, . . . , br} at least one coordinate line is empty.
We denote a rank r complete H-tree by tqr(H), where q is the order of group H. We define each non-empty coordinate line with q + 2 elements to be an arm of the complete H-tree. From definition, it is clear that we have complete H-trees of rank r which are not isomorphic. Recall that hij represents the q non-coordinate points on the coordinate line bi∨ bj. We define a complete H-star to be a complete H-tree, tqr(H), with elements of the form {b1∪ h12∪ b2∪ h13∪ b3∪ · · · ∪ h1r ∪ br}, denoted by Srq(H). We define a complete H- path to be a complete H-tree, tqr(H), of rank r > 2 with elements of the form {b1∪ h12∪ b2∪ h23∪ b3∪ h34∪ · · · ∪ br−1∪ h(r−1)r∪ br}, denoted by Prq(H).
Two diagrams in Figure 1, clarifies the definition of a complete H-tree of rank r, tqr(H).
0000 1111 00 1101 0000 1111 0 10011
00 11
0000 1111
0 1 00 11 00 11
00 11 00 11 0000 1111 0000 00 1111 11
00 11
00 11
00 11
00 11 00 11 0 1
0000 1111
00 11
00 11
00 11
00 11 00 11 0000 1111 0
1 0
1
00 11
0 1
00 0 11 1 0000
00 1111 11
00 0 11 1
00
11 000000 1111 11 00 0 11 1
00 11
0000 1111 0000 1111
00 11
Figure 1
From the definition, the following basic properties of trees from graph theory can be mimicked.
• If a non-empty coordinate line is added to a rank r H-tree without increasing the rank, the resulting rank r matroid is not an H-tree.
• Non-isomorphic complete H-trees have different degree sequences.
Note. A rank r matroid M ∼= Qr(H)|{b1, b2, . . . , br} is isomorphic to uniform matroid Ur,r. This is what we refer as a special complete H-tree with q = 0
and shall be denoted by t0r(H). Hence all our proposed theory should reduce to the known theory on trees in graph theory when q = 0, because t0r(H) is the cycle matroid of a tree on r + 1 vertices.
Proposition 3.1. Let a matroidM be a complete H-tree of rank r. Then (a) M has r − 1 arms.
(b) M has r coordinate points.
(c) M is a complete H-star if it has one joint of degree r − 1 and all the other joints have degree one.
(d) M is a complete H-path if it has two joints of degree one and all the other joints have degree two.
(e) M is isomorphic to U2,q+2 if r = 2.
The following theorem is one of the basic properties of complete H-trees which reduces to a well known result in graph theory.
Theorem 3.2. Let a matroid M = Qr(H)|S be a complete H-tree of rank r.
Then M has exactly 1 + (r − 1)(q + 1) elements.
Proof. The proof is by induction on the rank r of the H-tree. Let the set of the q non-coordinate points on the coordinate line bi ∨ bj, be labelled as {hij1, hij2, . . . , hijq}. Let M be a rank 2 complete H-tree. Then M is isomor- phic to the uniform matroid U2,q+2, hence M has q + 2 points. Assume it is true for any rank k H-tree. Now we consider any rank k + 1 H-tree. Let M = Qk(H)|S be a rank k complete H-tree and let M′ = Qk+1(H)|S′ be a rank k + 1 complete H-tree. M′can be constructed from M by embedding the matroid M in Qk+1(H) and adding one more arm to M. Choose any one joint bi∈ S, and define the set
S′ = S ∪ bk+1∪ {hi(k+1)1, hi(k+1)2, . . . , hi(k+1)q},
where the joint bk+1 ∈ Qk+1(H) but bk+1 ∈ Q/ k(H). Clearly, the constructed matroid M′ = Qk+1(H)|S′ is a complete H-tree of rank k + 1 by definition.
The number of elements of M′ is
|S′| = |S| + |{bk+1}| + |{hi(k+1)1, hi(k+1)2, . . . , hi(k+1)q}|.
Hence by induction hypothesis we have
|S′| = 1 + (k − 1)(q + 1) + 1 + q = 1 + kq − q + k − 1 + 1 + q = 1 + k(q + 1),
thus proving our theorem.
The following corollary is a well known result in graph theory.
Corollary 3.3. Let the graph tn be a tree on n vertices. Then tn has n − 1 edges.
Proof. The cycle matroid of tn has rank n − 1 and is isomorphic to Un−1,n−1∼= t0n−1(H). Hence E(tn) = 1 + (n − 1 − 1)(0 + 1)1 = n − 1 as required.
Definition. In general a rank r submatroid of a complete H-tree, tqr(H), will be called an H-tree and will be denoted tr(H). Similarly we have an H-star denoted Sr(H) and an H-path denoted Pr(H).
4. Characteristic polynomial of an H-tree
The characteristic polynomial of a tree, has a very simple explicit formula.
In this section we give the characteristic polynomial of a complete H-tree and show that it reduces to the characteristic polynomial of a tree in graph theory when q = 0.
To prove our next result we need the following known Theorem 4.1 found in [1].
Theorem 4.1. Let F be a modular hyperplane of a matroid M and let C∗= E(M ) − F. Then
χ(M ; λ) = (λ − |C∗|)χ(M \F ; λ).
Theorem 4.2. The characteristic polynomial of a completeH-star, Srq(H) is χ(Srq(H); λ) = (λ − 1)(λ − (q + 1))r−1.
Proof. It is clear that a complete H-star, Srq(H), has a modular hyperplane isomorphic to Sr−1q (H). The proof by induction on the number of arms of a
complete H-star is straightforward.
The following result shows that all non-isomorphic complete H-trees are χ- equivalent and when q = 0 it reduces to a well known result in graph theory that all non-isomorphic trees are χ- equivalent.
Theorem 4.3. Let a matroidM = Qr(H)|S be a complete H-tree tqr(H). Then the characteristic polynomial of M is
χ(M ; λ) = (λ − 1)(λ − (q + 1))r−1.
Proof. Let M = Qr(H)|S = tqr(H), where q is the order of group H and r is the rank of M. By definition it is clear that a complete H-tree of any rank r has r − 1 arms and r joints. It is also clear that non-isomorphic complete H-trees have different degree sequences. We show that we can construct χ- equivalent non-isomorphic complete H-trees of any rank r. The proof is by induction on n, the number of joints of deg > 1 of M. When n = 1 and any rank r ≥ 2, we have a special complete H-tree called a complete H-star and by Theorem 4.2 the result is true.
We assume it is true when n = k < r − 2 and any rank r ≥ 2. We now construct a rank r complete H-tree with k+1 joints of deg > 1. Let b1, b2, . . . , bk
be the k joints of deg > 1 in a rank r − 1 complete H-tree, tqr−1(H). Without loss of generality, consider that the coordinate line bk−1∨ bk is an arm of the H-tree, tqr−1(H). There are q + 2 points on this line. Now, add another joint bk+1 and the q points, hk,k+11, hk,k+12, . . . , hk,k+1q so that the coordinate line bk∨ bk+1 have q + 2 points. Since the joint bk+1 ∈ t/ qr−1(H), by definition, we
have constructed a rank r, H-tree, tqr(H). From this construction it is clear that tqr(H)\{hk,k+11, hk,k+12, . . . , hk,k+1q} is isomorphic to tqr−1(H). Moreover tqr(H)\{hk,k+11, hk,k+12, . . . , hk,k+1q} is a modular hyperplane of tqr(H). Hence by applying Theorem 4.1 and induction assumption, we have
χ(tqr(H); λ) = (λ − (q + 1))χ(tqr(H)\{hk,k+11, hk,k+12, . . . , hk,k+1q}; λ)
= (λ − (q + 1))χ(tqr−1(H); λ)
= (λ − (q + 1))(λ − 1)(λ − (q + 1))r−2
= (λ − 1)(λ − (q + 1))r−1.
By repeated application of the construction in this proof, we can construct a complete H-tree of any degree sequence possible, from a rank 2 complete H- tree. Hence by induction, the theorem is true for any complete H-tree tqr(H)
with any degree sequence.
Corollary 4.4. The characteristic polynomial of a graph tn is(λ − 1)n−1. 5. Characteristic polynomial of an H-cycle
In this section we define an H-cycle based on the definition of an H-tree.
We then give some properties and an explicit expression of the characteristic polynomial of an H-cycle.
Definition. We define a complete H-cycle of rank r > 2 to be a matroid with elements of the form {b1∪ h12∪ b2∪ h23∪ b3∪ h34∪ · · · ∪ br−1∪ h(r−1)r∪ br∪ h1r}, denoted by Crq(H), i.e., it is formed by adding the non-coordinate points between the two joints of degree one of an H-path.
An example of a complete H-cycle, Crq(H) is shown in Figure 1. If a non- empty coordinate line is added to a rank r H-tree, an H-cycle is created.
Proposition 5.1. Let a matroidM be a complete H-cycle of rank r. Then (a) M has r arms.
(b) M has r coordinate points.
(c) all the joints have degree 2.
(d) deletion of one arm results into an H-path.
We need the following theorem given in [4] to prove our next result.
Theorem 5.2. Let Qr(H) be a rank-r Dowling group geometry over a finite group H of order q. Then the characteristic polynomial of Qr(H) is
χ(Qr(H); λ) = (λ − 1)(λ − q − 1)(λ − 2q − 1) · · · (λ − (r − 1)q − 1).
Theorem 5.3. Let a matroid M = Qr(H)|S be a complete Dowling cycle Crq(H) and r ≥ 3. Then the characteristic polynomial of M is
χ(M ; λ) = (λ − q − 1)r+ (−1)rqr−1(λ − 1).
Proof. The proof is by induction on r. Let r = 3, then C3q(H) = Q3(H). Hence by Theorem 5.2, we get
χ(C3q(H); λ) = χ(Q3(H); λ)
= (λ − 1)(λ − q − 1)(λ − 2q − 1)
= (λ − q − 1)3− q2(λ − 1).
Therefore the result is true for r = 3. Assume it is true for some r = k. Now consider Ck+1q (H). By repeated application of the deletion and contraction formula and applying Theorem 4.3 and the induction assumption, we get
χ(Ck+1q (H); λ) = χ(tqk+1(H); λ) − qχ(Ckq(H); λ)
= (λ − 1)(λ− (q + 1))k+1−q(λ − q − 1)k+ (−1)kqk−1(λ− 1)
= (λ − 1)(λ − (q + 1))k[(λ − q − 1)] + (−q)(−1)kqk−1(λ − 1)
= (λ − q − 1)k+1+ (−1)k+1qk(λ − 1).
The result is true for any complete H-cycle Crq(H). Note that when q = 0 for a complete H-cycle Crq(H), we get Ur,r and this verifies the characteristic polynomial of a graph tn is (λ − 1)n−1.
6. Characteristic polynomials of an H-fan and an H-wheel In this section we define an H-fan and an H-wheel and we give explicit expressions of the characteristic polynomials of these matroids. An operation similar to a vertex-join of a graph was defined for representable matroids in [5]
as an H-lift.
Definition ([5]). Let {b1, b2, . . . , br−1} be the set of joints of Qr(H). Let A ⊆ cl{b1, b2, . . . , br−1}. An H-lift in Qr(H) is the matroid Qr(H)|A ∪ {br} ∪ hir : h ∈ H, 1 ≤ i ≤ r − 1. The set A is called the base of the H-lift.
We define a rank-r H-fan to be an H-lift of a rank-(r − 1) H-path and is denoted by Frq(H). We define a rank-r H-wheel to be an H-lift of a rank- (r − 1) H-cycle and is denoted by Wrq(H). We need the following theorem before stating our next results.
Theorem 6.1 ([5]). Let the matroid M be an H-lift with base A. Then the characteristic polynomial of M is
χ(M ; λ) = (λ − 1)χ(A; λ − q + 1).
The following results are derived by applying Theorem 4.3, Theorem 5.3, Theorem 6.1 and the definitions.
Theorem 6.2. The characteristic polynomial ofFrq(H), an H-fan of rank r is χ(Frq(H); λ) = (λ − 1)(λ − q)(λ − 2q)r−2.
Theorem 6.3. The characteristic polynomial of Wrq(H), an H-wheel of rank r is
χ(Wrq(H); λ) = (λ − 1)(λ − 2q)r−1+ (−1)r−1qr−2(λ − q) . References
[1] T. H. Brylawski, Modular constructions for combinatorial geometries, Trans. Amer.
Math. Soc. 203 (1975), 1–44.
[2] H. H. Crapo, The Tutte polynomial, Aequationes Math. 3 (1969), 211–229.
[3] T. A. Dowling, A class of geometric lattices based on finite groups, J. Combin. Theory Ser. B. 14 (1973), 61–86. erratum, J. Combin. Theory Ser. B. 15 (1973), 211.
[4] J. P. S. Kung, Critical problems, Matroid theory (Seattle, WA, 1995), 1–127, Contemp.
Math., 197, Amer. Math. Soc., Providence, RI, 1996.
[5] E. G. Mphako, H-lifts of tangential k-blocks, Discrete Math. 285 (2004), no. 1-3, 201–210.
[6] J. G. Oxley, Matroid Theory, Oxford University Press, New York, 1992.
[7] D. J. A. Welsh, Euler and bipartite matroids, J. Combin. Theory 6 (1969), no. 4, 375–377.
[8] G. P. Whittle, q-lifts of tangential k-blocks, J. London Math. Soc. (2) 39 (1989), no. 1, 9–15.
The John Knopfmacher Centre for Applicable Analysis and Number Theory School of Mathematics
University of the Witwatersrand
P/Bag 3, WITS, 2050, Republic of South Africa E-mail address: Eunice.Mphako-Banda@wits.ac.za
