[next] [prev] [up] Date: Thu, 19 Aug 93 15:04:18 -0400 (EDT)
~~~ [prev] [up] From: Allan C. Wechsler <acw@bronze.lcs.mit.edu >
[next] [prev] [up] Subject: Diameter of cube group?
Date: Thu, 05 Aug 1993 16:55:36 -0700
From: "Ronnie B. Kon" <ronnie@cisco.com>

Disclaimer: this sounds more authoritative than is intended--I really
don't know what I'm talking about.
Don't worry. Mathematical reasoning stands on its own merits.
It couldn't be very pointy. From the most distant configuration,
there are 6 positions immediately before it. There are 6^2 two steps
away, 6^3 three steps, etc. (well, 6^2 - 1 and 6^3 - ?) actually.
Very good. This is a necessary insight, regardless of the exact
numerical details. (For example, you mean 12, not 6.) But the
possible flaw is that there might be more than one maximally distant
state; if their sets of neighbors overlap viciously enough, this
effect could make the tail pointier. You can make valence-12 graphs
(not of groups, just arbitrary graphs) that have fairly bumpy
distance-vs-population functions. Any argument that rigorously
constrains N(d) must somehow appeal to the fact that the cube graph is
a Cayley graph, that is, the graph of a group.


This gives me the feeling that Monte Carlo is fairly valid. (How's
that for rigor?)

It's a start. But we have to use groupness somehow.

[next] [prev] [up] [top] [help]