<<

. 3
( 3)



Now we have
‘ Z(G[∆]) = Z(G; si ← si + 1 for i = 1, . . . , n),
(a)
∆∈P „¦/G
where P „¦/G denotes a set of orbit representatives for G on the power set
of „¦. This is Theorem 6.2, the Shift Theorem.
(b) If G is an IBIS group, then the ¬xed point set of G(∆) is the ¬‚at spanned by ∆;
so G(∆) is an IBIS group, and ρ(∆) = b(G) ’ b(G(∆) ). In fact, G(∆) is also
an IBIS group, but its base size may be smaller than ρ(∆).
Now we de¬ne the Tutte cycle index of G to be the polynomial in u, v, s1 , . . . , sn
given by
1
‘ u|G∆| vb(G(∆)) Z(G[∆]).
ZT (G) =
|G| ∆⊆„¦
8.7. The Tutte cycle index 69

One obvious ¬‚aw in this de¬nition is that the factors u|G∆ | and vb(G(∆) ) are not
really “local”. Nevertheless, we have the properties we are looking for:

Theorem 8.6 Let G be an IBIS permutation group, with associated matroid M.

ZT (G) (u ← 1, v ← 1) = Z(G; si ← si + 1 for i = 1, . . . , n).
(a)
‚u

(b) |G|ZT (G; u ← 1, si ← t i for i = 1, . . . , n) = t b(G) T (M; x ← v/t + 1, y ← t + 1).

Proof (a) The G-orbit of the subset ∆ has cardinality |G|/|G∆ |. Dividing by this
number has the same effect as choosing one representative set from each orbit.
Now apply point (a) before the Theorem.
(b) Point (b) before the Proposition shows that ρ(∆) = b(G) ’ b(G(∆) ); in
particular, ρ(„¦) = b(G). Also, substituting t i for si in Z(H) gives t n , where n is
the degree of the permutation group H. So the left-hand side is

‘ vρ(„¦)’ρ(∆) t |∆|.
∆⊆„¦

The rest is just manipulation.


Exercises
8.1. Let M be a matroid on E, and A the set of hyperplanes of H. For e ∈ E, let Xe
be the set of hyperplanes containing e. Prove that (Xe : e ∈ E) is an IBIS family
whose associated matroid is M.
8.2. Show that any family of subgroups, all of index p, in an elementary abelian
p-group is an IBIS family. Describe the associated matroid by means of the dual
group.
8.3. Let G be an IBIS group of permutations of „¦.
(a) Let ∆ be an orbit of G. Prove that both the permutation group induced on ∆
and the kernel of the action of G on ∆ are IBIS groups.

(b) Prove that the stabiliser of a point is an IBIS group.

(c) Prove that the group induced on a ¬‚at by its setwise stabiliser is an IBIS
group.
8.4. Let Gi be an IBIS group of permutations of „¦i , for i ∈ I. Prove that the direct
product of the groups Gi , acting on the disjoint union of the sets „¦i , is an IBIS
group.
70 Chapter 8. IBIS groups

8.5. Let p be a prime. Let G be an elementary abelian p-group, and (Hi : i ∈ I)
a family of subgroups of G. If each subgroup Hi has index p in G, prove that
(Hi : i ∈ I) is an IBIS family. Show that this may not be true if not all the subgroups
have index p.
8.6. Prove that, if G is a permutation group in which all two-point stabilisers are
trivial, then either G is semiregular, or G acts as a Frobenius group on one of its
orbits and regularly on all the others. (Hint: Use Frobenius™ Theorem.)
8.7. Prove that M24 is an IBIS group of rank 7.
8.8. Calculate the Tutte cycle indices for the group S4 , in each of its transitive
actions as an IBIS group on 6 points. Hence calculate the Tutte polynomial and
cycle index in each case.
8.9. Say that a base for a permutation group G is strongly irredundant if the
removal of any point results in a sequence which is no longer a base. Show that a
base is strongly irredundant if and only if any ordering of it is irredundant. Give an
example of a permutation group which has strongly irredundant bases of different
sizes.
8.10. Show that a sharply t-transitive group (other than the symmetric group St
of degree t) is a base-transitive group associated with a uniform matroid Ut,n , and
conversely. Why is the free matroid Fn = Un,n not associated with the symmetric
group Sn ?
8.11. Let G be a base-transitive group associated with a q-fold in¬‚ation of the
free matroid Fn (with q > 1. Show that G is the wreath product of a regular group
H of order q with Sn .
8.12. Show that a group G, acting on the coset space G : H, is a Frobenius group
if and only if H © H g = 1 for all g ∈ H.
/
A subgroup H of G is called a TI-subgroup if H © H g = 1 for all g ∈ NG (H),
/
g = H} is the normaliser of H in G. Show that, if H
where NG (H) = {g ∈ G : H
is a non-normal TI-subgroup of G, then G acting on G : H is an IBIS group, for
which the associated matroid is an in¬‚ation of a uniform matroid of rank 2.

Remark TI-subgroups are very common: for example, any subgroup of prime
order is a TI-subgroup. This shows that the procedure of identifying parallel ele-
ments can have dramatic effects in the case of an IBIS group.
Bibliography



[1] K. D. Blaha, Minimal bases for permutation groups: the greedy approxima-
tion, J. Algorithms 13 (1992), 297“306.

[2] N. Boston, W. Dabrowski, T. Foguel, P. J. Gies, J. Leavitt, D. T. Ose and
D. A. Jackson, The proportion of ¬xed-point-free elements of a transitive
permutation group, Commun. Algebra 21 (1993), 3259“3275.

[3] P. J. Cameron, Oligomorphic Permutation Groups, London Math. Soc Lec-
ture Notes 152, Cambridge University Press, Cambridge, 1990.

[4] P. J. Cameron, Permutation Groups, London Math. Soc. Student Texts 45,
Cambridge University Press, Cambridge, 1999.

[5] P. J. Cameron, Cycle index, weight enumerator and Tutte polynomial, Elec-
tronic J. Combinatorics 9 (2002), #N2 (10pp), available from
http://www.combinatorics.org

[6] P. J. Cameron and A. M. Cohen, On the number of ¬xed point free elements
of a permutation group, Discrete Math. 106/107 (1992), 135“138.

[7] P. J. Cameron and D. G. Fon-Der-Flaass, Bases for permutation groups and
matroids, Europ. J. Combinatorics 16 (1995), 537“544.

[8] P. J. Cameron and W. M. Kantor, Random permutations: Some group-
theoretic aspects, Combinatorics, Probability and Computing 2 (1993), 257“
262.

71
72 BIBLIOGRAPHY

[9] P. J. Cameron and S. Majid, Braided line and counting ¬xed points of
GL(d, Fq ), preprint available from
http://lanl.arXiv.org/abs/math/0112258

[10] P. J. Cameron and D. E. Taylor, Stirling numbers and af¬ne equivalence, Ars
Combinatoria 20B (1985), 3“14.

[11] H. H. Crapo, The Tutte polynomial, Aequationes Math. 3 (1969), 211“229.

[12] M. Deza, Perfect matroid designs, Encycl. Math. Appl. 40 (1992), 54“72.

[13] J. D. Dixon and B. Mortimer, Permutation Groups, Springer, New York,
1996.

[14] D. Gewurz, Sui vettori di Parker e concetti correlati, Ph.D. thesis, Universit`
a
di Roma “La Sapienza”, 1999.

[15] D. Gorenstein, Finite Simple Groups: An Introduction to their Classi¬cation,
Plenum Press, New York, 1982.

[16] C. Greene, Weight enumeration and the geometry of linear codes, Studia
Appl. Math. 55 (1976), 119“128.

[17] M. Hall, Jr., Automorphisms of Steiner triple systems, IBM J. Research De-
velop. 4 (1960), 460“472.

[18] F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, New
York, 1973.

[19] A. R. Hammons Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane and
P. Sol´ , The Z4 -linearity of Kerdock, Preparata, Goethals and related codes,
e
IEEE Trans. Inform. Theory 40 (1994), 301“319.

[20] M. R. Jerrum, Computational P´ lya theory, pp. 103“118 in Surveys in Com-
o
binatorics, 1995 (P. Rowlinson, ed.), London Math. Soc. Lecture Notes 218,
Cambridge University Press, Cambridge, 1995.

[21] M. W. Liebeck and A. Shalev, Simple groups, permutation groups, and prob-
ability, J. Amer. Math. Soc. 12 (1999), 497“520.

[22] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting
Codes, North-Holland, Amsterdam, 1977.

[23] T. C. Maund, D.Phil. thesis, University of Oxford, 1989.
73
BIBLIOGRAPHY

[24] E. G. Mphako, Tutte polynomials of perfect matroid designs, Combinatorics,
Probability and Computing 9 (2000), 363“367.

[25] J. G. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.

[26] D. S. Passman, Permutation Groups, Benjamin, New York, 1968.

[27] C. G. Rutherford, Matroids, codes and their polynomial links, Ph.D. thesis,
University of London, 2001.

[28] J.-P. Serre, On a theorem of Jordan, Mathematical Medley (Singapore Math-
ematical Society), to appear. Available from
http://www.math.nus.edu.sg/˜chanhh/JordanMar11.pdf

[29] A. D. Sokal, Bounds on the complex zeros of (Di)chromatic polynomials and
Potts-model partition functions, Combinatorics, Probability and Computing
10 (2001), 41“77.

[30] D. J. A. Welsh, Matroid Theory, Academic Press, London, 1976.

[31] D. J. A. Welsh, Complexity: Knots, Colourings and Counting, London Math-
ematical Society Lecture Notes 186, Cambridge University Press, Cam-
bridge, 1993.

[32] H. Wielandt, Finite Permutation Groups, Academic Press, New York, 1964.

[33] B. I. Zil™ber, The structure of models of uncountably categorical theories,
pp. 359“368 in Proc. Internat. Congr. Math. Vol. 1 (Warsaw 1983).
Index


af¬ne geometry, 22 MDS, 7
af¬ne group, 42 Nordstrom“Robinson, 9
af¬ne independence, 16, 22 Preparata, 9
af¬ne matroid, 16 repetition, 5
algebraic matroid, 16 codeword, 2, 3
almost simple group, 41 Cohen, A. M., 45
alphabet, 3 coloop, 18
complete vector matroid, 16, 22
base, 38, 60 congruence, 40
irredundant, 60 conjugate, 35
base-transitive, 66 coset space, 35
basic, 42 Crapo, H. H., 19
basis, 17 cycle decomposition, 33
Blaha, K., 39 cycle index, 47, 56, 57
block of imprimitivity, 40 Cycle Index Theorem, 49
Boston, N., 52
bridge, 18 Dabrowski, W., 52
degree, 34
Calderbank, A. R., 9
Deza, M., 23
Cartesian product, 35
diagonal group, 42
CFSG, 42, 62, 66
direct product, 35
chain, 12
direct sum, 7
chromatic polynomial, 20, 57
distance-invariant, 9
code, 2, 3
dual code, 3
dual, 3
dual matroid, 17
even-weight, 5, 67
Golay, 5, 8, 24, 63 elementary abelian group, 56, 70
Hamming, 2, 8 even-weight code, 5, 67
Kerdock, 9
linear, 3 Feit, W., 62

74
75
INDEX

¬gure-counting series, 48 independent, 15
¬‚at, 17 in¬‚ation, 55
¬‚at action, 64 intransitive, 34
Foguel, T., 52 irredundant, 60
Fon-Der-Flaass, D. G., 59 Ito, N., 62
free matroid, 17, 22
Jackson, D. A., 52
Frobenius group, 70
Jerrum, M. R., 37
Frobenius™ Theorem, 70
function-counting series, 49
Kantor, W. M., 43
Kerdock code, 9
Gaussian coef¬cients, 65
Kumar, P. V., 9
general linear group, 63
generator matrix, 3
Leavitt, J., 52
Gewurz, D., 51
Lee distance, 10
Gies, P. J., 52
Lee weight, 10
Golay code, 5, 8, 24, 63
Lee weight enumerator, 10, 11
graphic matroid, 16
Liebeck, M. W., 43
Gray map, 10
linear code, 3
Greene™s Theorem, 28
loop, 18
group
af¬ne, 42
MacWilliams, F. J., 5
almost simple, 41
Markov chain, 37
diagonal, 42
Mathieu group, 5, 41, 45, 63, 70
elementary abelian, 56, 70
matroid, 15
Frobenius, 70
af¬ne, 16
general linear, 63
algebraic, 16
Mathieu, 5, 41, 45, 63, 70
complete vector, 16, 22
oligomorphic, 52
dual, 17
Suzuki, 62
free, 17, 22
symmetric, 33, 68, 70
graphic, 16
symplectic, 63
transversal, 16
uniform, 17
Hall triple system, 22
vector, 16
Hall, M. Jr, 22
matroid pair, 31
Hamming code, 2, 8
Maund, T., 66
Hamming distance, 3
MDS code, 7
Hammons, A. R. Jr., 9
minimum weight, 4
hyperplane, 17, 69
Mphako, E. G., 23
IBIS family, 60, 69 multiply transitive, 41
IBIS permutation group, 61
imprimitive, 40 Nordstrom“Robinson code, 9
76 INDEX

normaliser, 70 Rutherford polynomial, 31

O™Nan“Scott Theorem, 42 semiregular, 35
orbit, 34 Serre, J.-P., 37
Orbit-Counting Lemma, 53 Shalev, A., 43
Orbit-Stabiliser Theorem, 34 Shift Theorem, 51
Ose, D. T., 52 shortening, 29
Sloane, N. J. A., 9
P´ lya, G., 47
o Sokal, A. D., 57
parity check matrix, 3 Sol´ , P., 9
e
Parker vector, 51 stabiliser, 34
Passman, D. S., 62 Steiner system, 22, 63
perfect matroid design, 21, 64, 66 Stirling numbers, 50, 65
permutation character, 48 strong generating set, 39
permutation group, 34 Suzuki group, 62
base-transitive, 66 Suzuki, M., 62
basic, 42 symmetric group, 33, 68, 70
IBIS, 61 symmetrised weight enumerator, 11,
imprimitive, 40 57
intransitive, 34 symplectic group, 63
multiply transitive, 41 syndrome decoding, 2
primitive, 40 system of imprimitivity, 40
regular, 35
semiregular, 35 Taylor, D. E., 66
transitive, 34 Thompson, J. G., 62
PMD, 21 TI-subgroup, 70
Preparata code, 9 transitive, 34
primitive, 40 transitive constituent, 35
primitive component, 41 transversal matroid, 16
projective geometry, 22 truncation, 17
puncturing, 29 Tutte cycle index, 68
Pyber, L., 44 Tutte polynomial, 19
quotient, 31 uniform matroid, 17
rank, 17 vector matroid, 16
rank polynomial, 19
weight, 4
rate, 2
weight enumerator, 4, 56
Red¬eld, J. H., 47
Lee, 10, 11
regular, 35
symmetrised, 11, 57
repetition code, 5
representation, 16 Wielandt, H., 62
77
INDEX

word, 3
wreath product, 41

Zassenhaus, H., 62
Zil™ber, B. I., 66

<<

. 3
( 3)