Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.