The transposition diameter of 3-permutations

This document proves that every 3-permutation has an 11/8-sequence unless the permutation contains less than 8 cycles. To understand the details of the proof the reader is referred to the paper by Elias and Hartman. The syntax of the proof is described here.

DOWNLOAD

The whole web interface is contained in sbt1375_proof.tar.gz. This file also includes the verification programs. Altogether there are slightly more than 80.000 files an in uncompressed format it takes 560MB on your hard drive.

Case Analysis 1

With the first case analysis the following two lemmas are shown:

LEMMA 1: Every unoriented sufficient configuration of 9 cycles has an 11/8-sequence.

LEMMA 2: The components of size <= 8 (bad small components) that do not have an 11/8 sequence are:

  1. the unoriented interleaving pair,
  2. the unoriented necklace of size 4,
  3. the twisted necklace of size 4,
  4. the unoriented necklace of size 5,
  5. the unoriented necklace of size 6.

The BFS search

As described in the paper by Elias and Hartman the case analysis works similarly to a BFS search. The two start positions are:
  1. Unoriented interleaving pair
  2. Unoriented intersecting pair

The configurations of each size that do not have a (4,3), (8,6), or (11,8) sequence are listed here. Note that there are no such files of size 9.

Size 2, Size 3, Size 4, Size 5, Size 6, Size 7, Size 8, Size 9

Of all these configurations there are only six full configurations. The 5 bad small components listed above and one additional full configuration of size 4, [3](0_9_7)[3](1_6_3)[3](2_11_4)[3](5_10_8). This sixth configuration is full but it is not a component! That is this configuration can not occur by itself. This is due to one of the lemmas in Elias and Hartman. Intuitively this can be understood by noting that there is no permutation that has this configuration as a breakpoint graph.

Verification of BFS

The program that verifies the correctness of the proof is the class verifier.VerifyBFSProof. To run the verification download the proof and run "java verifier.VerifyBFSProof". The class verifier.Configuration is used by the verification program.

Case Analysis 2: Combinations of bad small components

Here we give the case analysis showing:

LEMMA 3. Let $\pi$ be a permutation that contains several bad small components, such that the sum of the sizes of these components is at least 8. Then, there is an $(11,8)$ sequence on $\pi$.

To show this lemma we need to show that all possible combinations of bad small components such that there are at least 8 cycles have an (11,8) sequence. In the analysis below it is possible to follow links to every combination by starting from one of the bad components and then adding new components in different positions of the breakpoint graph.

  1. the unoriented interleaving pair,
  2. the unoriented necklaces of size 4,
  3. the twisted necklace of size 4,
  4. the unoriented necklaces of size 5,
  5. the unoriented necklaces of size 6.

Verification of Combination proof

The program that verifies the correctness of the combination proof is the class verifier.VerifyCOMBINATIONProof. To run the verification download the proof and run "java verifier.VerifyCOMBINATIONProof". The class verifier.Configuration is used by the verification program.