MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.