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!



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.