‘ 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