[seqfan] a challenge: guess the formula
Brendan McKay
bdm at cs.anu.edu.au
Fri Oct 28 13:58:38 CEST 2011
Hi, Here is an unsolved problem some people here might have fun
with. A fullerene is a cubic planar graph with only faces of size 5
and 6. It is also called a buckyball, and a standard soccer ball is
an example.
At http://cs.anu.edu.au/~bdm/rooted_maps_big.maple you can find a
file like this:
------------
# Rooted fullerene counts from Jan
c[12] := 1:
c[13] := 0:
c[14] := 6:
c[15] := 13:
c[16] := 49:
...
c[196] := 232707817491808:
c[197] := 244417114815861:
-----------
The value of c[n] is the number of rooted fullerenes with n faces,
where "rooted" means that a triple (v,e,f) is distinguished, where v
is a vertex, e is an edge on that vertex, and f is a face on that edge.
(Such rooting is a standard device in enumeration of planar graphs
since it removes all symmetries.)
A deep theoretical result is that c[n] is proportional to n^10 for
very large n. Polynomial growth is very rare for graph classes. It
is plausible that in fact c[n] is given by a formula. For example,
it might be a polynomial of degree 10 (but it isn't, I checked). Or
it might be a different polynomial of degree 10 according to n mod 4.
(There is a distinct wriggle of period 4, but this one doesn't seem
to work either; don't trust me.) Or some other possiblity.
My fantasy is that just by playing with the numbers in different
ways it might be possible to guess the formula, if there is one.
Another possibility is that the generating function might be
guessable. For example it might be a rational function
c(x) = p(x)/q(x)
where p,q are polynomials and the smallest zeros of q(x) have
absolute value 1 and one such zero has multiplicity 11.
It would be very interesting if someone can find something.
This sequence is not in OEIS yet.
Cheers, Brendan.
More information about the SeqFan
mailing list