[r-t] Crambo - mystery solved(?)
Robert Johnson
r.johnson at qmul.ac.uk
Thu Aug 24 14:05:46 UTC 2006
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
More information about the ringing-theory
mailing list