User andy juell - MathOverflow

Matula-Goebel ordering of rooted trees intrinsic?

2013-04-10T04:58:39Z

I was somewhat recently introduced to the Matula-Goebel bijection between rooted trees and natural numbers. (nicely illustrated here http://keithbriggs.info/matula.html) Looking through them, I noticed that smaller integers were repeated as 'terminal subtrees' more often, which led me to wonder whether the MG numbering actually provided a perfect index of how frequently a given rooted tree would appear as such in the set of ALL rooted trees. I already knew that Schenk's Theorem implied that any (rooted) subtree would eventually occur in almost all (rooted) trees, and thus have asymptotic density of 1, but perhaps some subtrees raced to that density reliably faster than others?

To find the set of trees containing our subtree of interest, we start with a set containing only the integer representing that subtree.

for every n in the set, find the nth prime.
add all multiples of this prime to the set.
goto 1

It seems entirely believable that the asymptotic density of all such sets must be 1 regardless of the starting integer...but larger starting n consistently have larger gaps in the final sequence. For two sets starting from different n, clearly there were at most a finite number of x for which the member counts of each set

Great! ...except there are infinitely many other bijections which construct a contradictory ordering.

Nowhere in the definition of the MG bijection is addition used, only multiplication and ordinal comparison on the set of primes...so taking a page from Beurling's generalized integers, there's no reason we can't use a different list of primes when building the tree bijection, provided they still produce unique factorizations. Let's keep things simple and just remove 2, so we can easily map the resulting odd integers back to (x+1)/2. (unsurprisingly I wasn't the first to think of this, see OEIS A048673)

so instead of 1,p1,p2,p1^2,p3,p1p2,p4,p1^3,p2^2,p1p3,p5...

we now have 1,p1,p2,p3,p1^2,p4,p5,p1p2,p6,p7,p1p3,p8,p2^2,p1^3...

which will clearly put the trees in a different ordering. But even using a different list of primes (and being careful how to interpret 'multiiples'), following the same reasoning would seem to require that this new ordering would also yield strictly decreasing 'densities' in the resulting sets. The pairs reversed by this permutation of the trees cannot both exceed the other's frequency, so I'm guessing I proverbially divided by zero somewhere above.

To further deepen the confusion, or perhaps provide a direction toward resolution, a closer reading of Schenk (or at least people quoting him on this side of the paywall) seems to indicate that the number of trees containing a particular 'limb' depends only on the limb's size, not its internal structure, which would seem to make any such ordering within a given tree size dubious, and orderings placing larger trees before smaller (ie 18<19) doubly so.

So, to bring that all into a proper question or two:

Is there an intrinsic meaning to the MG ordering applicable in the domain of rooted trees without reference to the multiplicative structure of the integers? (or perhaps some other well-ordering of them is more useful/meaningful?)
I understand that bijections between infinite sets can yield rampant paradoxes if not handled with sufficient care...is this just another one, or have I committed a serious logical error in the above?

Thanks in advance...

Reals with integer powers bounded away from integers?

2013-04-10T00:37:26Z

Do there exist real numbers whose integer powers are bounded away from integers? More precisely, for an arbitrary constant 0 < $\epsilon$ < 1/2, does there exist real x such that for all positive integer n,
$ \epsilon < (x^n)$ mod 1 < $1-\epsilon $?

Pisot numbers more or less provide the opposite of this behavior, and at first I briefly thought that applying Hurwitz' Theorem to the logs might help...but ln(3)/ln(2) isn't rational, and $2^n$ and $3^n$ seem to keep a minimum unit distance apart. ^_^

Answer by Andy Juell for Almost or probably complete graph invariants?

2013-01-11T18:02:45Z

Though painfully slow to compute, I've yet to find a counterexample to the first invariant proposed in this paper by Mehendale: a vector of integers counting, for each n, the number of labeled subgraphs of G which are trees on n vertices.

Update: I've since discovered several counterexamples, perhaps the simplest being

S3 U P2 U P2

and

P4 U P3 U P1

both of which yield the signature (8,5,3,1)

Possible structures for minimal tiling sets

2012-06-25T00:22:33Z

Inspired by Col. Sicherman's results here, my speculations have so far outrun my expertise that I thought I might pass my question along to others who might find it equally intriguing, but perhaps somewhat less intimidating. Though I first approached it as a question regarding polyforms, it may be easier to attack in the more general case.

Consider the infinite (hyper)graph G, whose vertices correspond to distinct polygonal tiles. A (hyper)edge links each minimal set of polygons which tile the plane. Thus, every polygon which tiles the plane on its own is an isolated vertex with a loop, leaving the remainder of the graph simple.

What finite (hyper)graphs exist as induced subgraphs of G?

Equivalently, for which finite (hyper)graphs can a set of tiles be constructed such that minimal tiling sets correspond exactly to the edges of the (hyper)graph?

Hypergraphs consisting of a single maximal hyperedge (hyperclique?) are easily obtained: take a square, say, and slice it into n radial pieces, then give each adjacent pair a unique nick/bump combination. Complete bipartite graphs can be made by increasingly long unit-width rectangles, with one color class bumped on the unit side, and the other color class nicked. This can be extended to complete k-partite k-hypergraphs for arbitrary k by increasing the variety of nicks and bumps.

Anything further I might add would be half-baked speculation, so I'll hope I've lurked here long enough to know what a decent first question is supposed to look like. ^_^ Thanks in advance!

Comment by Andy Juell

2013-04-11T13:53:16Z

I have to wonder whether it's entirely safe to refer to Greg Egan's "Luminous" ^_^

Comment by Andy Juell

2013-04-10T02:35:31Z

Nifty...thanks! Somewhere between 7.3769347535 and 7.3769347577 lurks a number whose powers never stray within 1/3 of an integer...

Comment by Andy Juell

2013-04-10T01:56:37Z

(was previously ICanChangeThisLaterRight)

Comment by Andy Juell

2013-04-10T01:54:38Z

Duly noted. ^_^

Comment by Andy Juell

2013-01-12T00:06:09Z

Yes...after posting I felt the response was if anything more applicable to the other thread [here](mathoverflow.net/questions/22184/…), sorry if this was inappropriate.