Isbell’s Conjecture

Yesterday a small birthday celebration took place.

Our department was founded on 15 February 1983, and each year we mark the anniversary by a couple of lectures by newly appointed or promoted members of staff followed by a dinner. It used to be a kind of rite of passage for new staff, but now the department is so large that not all new staff can be fitted in, and some kind of selection procedure has to take place.

This year, the celebrations were a bit muted. Our large lecture room is being refurbished, so we had to trek across campus to the Biology lecture theatre; the restaurants on campus are being refurbished (and the only decent local restaurant, l’Oasis, has closed), so we had a party instead of a dinner. Attendance was quite a bit lower than usual, partly for these reasons (perhaps also because of the coffee machine effect, who knows?)

Anyway, the highlight for me was a beautiful lecture by Peter Keevash on “Voting Paradoxes”.

He began by showing us Condorcet’s paradox: majority voting can lead to deadlock. In a society with three voters, each of whom can express a preference about three candidates A, B, C, if voter 1 orders them as (A,B,C), candidate 2 as (B,C,A) and candidate 3 as (C,A,B), then on majority voting A beats B (since voters 1 and 3 prefer A to B), and similarly B beats C, and C beats A. So we have the situation of “paper, scissors, stone”.

Peter told us about McGarvey’s Theorem, which says that any directed graph can be represented as the preference graph for some set of voter preferences. (The example just given represents the 3-cycle in this way.)

Further bad news for preferential voting is the Muller–Satterthwaite Theorem, a voting version of Arrow’s paradox: two reasonable rules that a voting system should satisfy can only hold if there is a dictator, whose preferred candidate is elected no matter what the other voters think.

Let us examine this a bit more. A winning coalition is a collection F of subsets of the set {1,…,n} with the property that, given any set A in F, any set B which contains A is also in F. It is called strong if, for any set A, either A or its complement is in F. I shall abbreviate “strong winning coalition” to SWC.

Now, if n is odd, then the collection of all subsets containing more than half of the elements of {1,…,n} is a SWC, corresponding to majority voting. Also, for any element d of {1,…,n}, the collection of all subsets containing d is a SWC, corresponding to the case where d is a dictator.

One strategy for ruling out a dictator is to ensure that the SWC is fair, in the sense that all the n electors are treated in the same way. In 1959, John Isbell proposed that the right concept of fairness is symmetry: so we say that a SWC F is fair if there is a group G of permutations of {1,…,n} which acts transitively on this set and preserves the collection F. Now, if n is odd, the collection of all majorities is a fair SWC. Isbell asked: for which even n does a fair SWC exist?

Another piece of terminology. If p is a prime number, I will say that “If p is dominant in n then …” to mean that if the power of p dividing n is a sufficiently large part of n then the conclusion holds. Formally it means “There is a function f(p,b) such that, if n=pa.b and af(p,b), then …”.

Isbell conjectured:

Suppose that 2 is dominant in n. Then there is no fair SWC on the set {1,…,n}.

This conjecture is more than 50 years old and still unproved.

The conjecture can be translated as follows. A permutation group G fixes a SWC if and only if G contains no permutation with all its cycles even. To see this, note that if g has all its cycles even, then we can colour the points red and blue alternately round the cycles, so that g maps the set of red points into the set of blue points; so a G-invariant collection must contain both or neither of the sets of red and blue points; but by definition a SWC must contain exactly one of these two sets.

Now, if a permutation has all its cycles even, then some (odd) power of it has 2-power order with no fixed points. So Isbell’s conjecture can be stated as follows:

Suppose that 2 is dominant in n. Then every transitive permutation group on {1,…,n} contains a fixed-point-free element of 2-power order.

Now Isbell’s conjecture is easily generalised to arbitrary primes:

Suppose that the prime p is dominant in n. Then every transitive permutation group on {1,…,n} contains a fixed-point-free element of p-power order.

This is, maybe, the conjecture I would most like to see settled. Since Isbell’s original conjecture is fifty years old, I am prepared to offer a fifty pound prize for a solution.

One of the interesting things about the conjecture is that there is real uncertainty whether it is true or false: what we know points in different directions.

On one hand, Fein, Kantor and Schacher in 1981 (using the Classification of Finite Simple Groups) proved the following theorem:

Let n be greater than 1. Then any transitive permutation group on {1,…,n} contains a fixed-point-free element of prime power order.

It is natural to suspect that, if a prime is dominant in n, then this should be the one.

On the other hand, in trying to see how Isbell’s conjecture could be proved, I made a slightly stronger conjecture:

There is a function g(p,b) such that, if p is prime and P is a p-group of permutations having b orbits each of size at least g(p,b), then P contains a fixed-point-free element.

Now if G is transitive of degree n=pa.b, where p doesn’t divide b, then the Sylow p-subgroup of G has at most b orbits, each of size at least pa. So my conjecture implies Isbell’s. However, this conjecture has been refuted by Eleonora Crestani and Pablo Spiga for all primes greater than 3. (This paper has not yet appeared.)

So Isbell’s conjecture for arbitrary primes might be true or false, or even true for some primes and false for others. I’d like to know!

Incidentally, I would really like to see a proof of the Fein–Kantor–Schacher result without using the Classification of Finite Simple Groups. Camille Jordan proved in 1871 that any finite transitive permutation group of degree greater than 1 contains a fixed-point-free element; why should we have to work so hard to add the rider “of prime power order”?

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition, open problems. Bookmark the permalink.

3 Responses to Isbell’s Conjecture

  1. Haris says:

    Hi,

    This is interesting! Which paper of Isbell do you refer to?

    Thank you.

    Best wishes,

    • Ah, caught! It was 1960, not 1959, sorry (so this year is the 50th anniversary). The paper is J. R. Isbell, Homogeneous games II, Proc Amer. Math. Soc. 11 (1960), 159-161.

      But be warned: he has another paper, Homogeneous games III, in Advances in game theory pp. 255–265 Princeton Univ. Press, Princeton, N.J. 1964, in which he proves the conjecture; but the proof is wrong.

  2. Pingback: A deranging puzzle « Peter Cameron's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s