[r-t] Crambo - mystery solved(?)

[Robert Johnson]

As requested by the Ander here is a short proof of the Crambo Theorem (every 
in-course  half extent of doubles admits a crambo).

Given an in-course half extent on 5 make a bipartite graph G by listing the 
"slots" (ie pairs of adjacent rows) on the left and the out-of-course rows on 
the right and joining a slot to a row if inserting that row in that slot 
gives a legal touch. We'd like to find a perfect mathcing in this (that is a 
set of edges which pairs up everything on the left with everything on the 
right).  Obviously every slot has degree 2 (it sees 2 rows) and the averagre 
degree of an ooc row is 2. If all the ooc rows have degree 2 then we are 
happy as the graph is just a disjoint union of even cycles so certainly has a 
perfect matching.  If not then some rows have degree 1. If abcde has degree 1 
then the touch must contain the block

baecd
abced
bacde
bcaed

(This is because we must have a slot which is adjacent to abcde next to both 
abced and bacde so these must be consecutive in the touch, and we are now not 
allowed a 1 pn next to abced or a 5 pn next to bacde.)
Now if we pair up every degree 1 vertex (the prof calls these danglers) with 
the unique slot it is adjacent to and remove these slots and rows  from the 
graph we get a bipartite graph in which every degree is 2. 
This is because the row baced (ie the other neiighbour of the slot which is 
deleted) has degree 3 in the graph. Also, baced is adjacent to a slot with a 
1 pn and a slot with a  5 pn and these slots are never removed (only slots 
with 3 pn are adjacent to danglers).  
A matching in this graph finishes the job. 


This also gives an algorithm for finding all the cramboes. Locate the danglers 
(this is easy just look for the 1.3.5 or 5.3.1 pns in the touch). Make an 
arbitrary choice of one edge in each compnent of the rest and everything else 
is forced. The number of cramboes will be 2^{number of components of G}

I have no idea how to do any of this, or even what a sensible crambo 
conjecture would be, on more than 5.

Robert


On Wednesday 23 Aug 2006 23:42, Alexander Holroyd wrote:
> Last week Robert Johnson discovered a marvellous proof that every
> in-course extent of doubles can be cramboed up in at least one way.  (And
> he duly related it to a few of us in the pub).  Hopefully he will post it
> to the list soon....
>
> _______________________________________________
> ringing-theory mailing list
> ringing-theory at bellringers.net
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net