[r-t] Extents of minor

[Martin Bright]

--On 18 August 2004 12:09 +0100 Robin Hall <halls at twiddlepin.org.uk> wrote:

> A (very very) crude upper limit (I'm no graph theorist - in fact I've
> never even heard of one before) would be 7200. Simply on the basis that I
> think there are only 11 place notations, and you can't have the one
> you've just had.

You mean 10^720 then, which is rather large.

There must really be loads - as well as all the extents using sensible 
methods, there will be vastly many more which have no structure, but are 
just seemingly random sequences of changes.

I'd be surprised if there were a good way of working this out.  Given that 
it's very hard to determine whether a general graph _has_ a Hamiltonian 
cycle (i.e. a cycle that visits every vertex precisely once), it must also 
be difficult to count them.  (Otherwise, to tell whether one existed, you 
could just count them and see whether there were more than 0.)  Of course 
this isn't a random graph, it's a rather special one, but even so...

There may be some known heuristics, but I'm also no graph theorist so I 
wouldn't know.

Isn't the number of extents of minimus known?

Martin

-- 
Martin Bright
Department of Mathematical Sciences, University of Liverpool