Squares meet four at a time, bricks three

A bathroom floor tiled with square tiles has four tiles meeting at every corner. A brick wall, laid with alternate courses staggered by half a brick, has only three bricks meeting anywhere: every crossing of mortar lines has become a T. Can a surface be covered by small pieces so that no point touches more than two of them? A row of planks does it — each plank touches only its neighbours — but the planks run the whole width of the floor. With pieces that are all small, Henri Lebesgue proved in 1911, it cannot be done. Somewhere, three must meet.

That fact turns out to characterise dimension. A segment covered by short pieces needs only two to meet at a point, a square needs three, a cube four, and in general the least number of small closed pieces that must share a point is one more than the dimension. It is a topological statement — it survives any stretching or bending — and it is one more face of the theorem that has run through this subject in many forms: Brouwer’s fixed point theorem, Sperner’s three colours, and the board of Hex that cannot be drawn.

Counting where pieces meet #

The pieces in this essay are closed: each includes its boundary, so a point on the edge between two tiles belongs to both. That is the natural convention for a cover by tiles, and it matters — open pieces could avoid sharing boundaries altogether only by leaving the boundaries uncovered.

For tiles shaped as rectangles, the points where several tiles meet are the corners of the tiles and the crossings of their edges, and those are finitely many, so the most tiles meeting at a point can be found by testing every such point against every tile. For the 6 by 6 grid the answer is four, reached at all 25 inner corners. For the brick wall of six courses, 21 bricks in all with the half-bricks at the ends of alternate courses, it is three, reached at 25 inner T-junctions, and no point lies in four. The staggering moves every vertical joint so that it meets a horizontal joint from one side only, and a T has three bricks around it where a cross has four.

Nothing about the particular sizes matters. The brick wall can be made finer, and the figure of finer walls below shows the count of three surviving all refinement. The question is whether any arrangement of small closed pieces, of any shapes at all, can get below three.

The two covers in the figure are equally fine — the bricks are twice as wide as the squares but the same height — and they use their pieces equally efficiently in the sense of area, since every point of the square is covered and the pieces overlap only along their boundaries, which have no area. What distinguishes them is purely combinatorial: the pattern in which the pieces’ boundaries meet. A grid’s boundaries form crossings, a wall’s form T-junctions, and a crossing is a coincidence of two lines that a T-junction avoids. Every point where boundaries meet is a point in several pieces, and the theorem is a statement about how simple that pattern of meetings can be made.

That also explains why the grid is the arrangement people choose for floors and the wall the arrangement they choose for structures. A grid is easy to lay out because its seams are straight lines across the whole floor; a wall is strong because its seams are not, and a crack following a seam must turn at every course. The mason’s staggering, done to stop cracks running, is exactly the arrangement that minimises how many bricks meet at a point.

Two at a time needs long pieces #

A cover with only two pieces meeting at any point is easy if the pieces may be long. Five horizontal strips cover the square, and each strip meets only the strips immediately above and below it: no point lies in more than two.

But every strip spans the square from side to side. Try to make the pieces small by cutting each strip in two, at staggered places so that no cut lines up with another. Each cut ends on a seam between two strips, and the end of a cut is a point of three pieces: the two halves of the cut strip, and the strip on the other side of the seam. The overlap is back to three immediately.

That is the whole difficulty in miniature. A cover in which pieces meet only two at a time arranges them like beads on a string — each touches at most its neighbours in a sequence — and a string of small beads is a thin thing, unable to fill a square. Lebesgue’s theorem makes this precise in its sharpest form: if a square is covered by finitely many closed sets, none of which meets two opposite sides, then some point lies in at least three of them. The sets need not be small in any other sense; it is enough that none stretches across.

Random pieces meet three at a time #

A random cover shows what is typical. Scatter sixty points in the square at random and give each the closed cell of points nearer to it than to any other: the Voronoi diagram of the points.

The cells are small and closed, and they meet exactly as the theorem demands: 90 points lie in three cells, at the corners where three cells come together, and none lies in four. Four cells meet only at a point equidistant from four of the centres, which requires four random points to lie on a common circle, an event of probability nought. So a random cover achieves the minimum overlap without being asked to, and a grid, where four meet at every corner, is the special arrangement.

The number 90 is fixed by Euler’s formula, given the 28 boundary points. For a cover of a disc-like region by cells meeting three at a time, vertices, edges and faces satisfy $V - E + F = 1$ inside the region, and counting edge-ends at three-fold and two-fold points ties the number of inner corners to the number of cells and boundary points. Euler’s formula is the bookkeeping; the fact that the corners exist at all is Lebesgue’s theorem.

The proof is a fixed point theorem #

Why three, and why can no cleverness avoid it? Suppose the square were covered by closed sets, none touching two opposite sides, with no point in three of them. Colour each set by whether it touches the left side, the right side, or neither, and look at how the sets of the first kind and the second kind can be separated. The argument that follows is, in its two-dimensional form, exactly the argument that a game of Hex cannot end in a draw: one player’s stones must connect their two sides, or the other player’s must. A board that cannot be drawn showed that the Hex statement is equivalent to Brouwer’s fixed point theorem for the square, and Lebesgue’s covering theorem sits in the same circle of equivalences.

The equivalence runs through Sperner’s lemma, and it is the most direct way to see the theorem. Given a cover by small closed sets with no point in three, one can build a continuous map of the square to its boundary that fixes the boundary — pushing each point towards a side according to which sets contain it — and Brouwer’s theorem says no such map exists. Conversely, a map of a disc to itself without a fixed point would produce a cover violating the covering theorem. The covering theorem, the fixed point theorem, the three-coloured triangle, the Hex theorem and the statement that a sphere cannot be combed without a bald spot are different faces of one topological fact about the disc.

In three dimensions, four #

The same staggering works in space. Build a solid from layers, each layer a brick wall, and turn each layer a quarter turn from the one below, so that the seams of one layer run across the seams of the next. Inside a layer, at most three bricks meet, as in the flat wall. On the plane between two layers, a point belongs to the bricks of both layers that contain it.

The count is made exactly as before, at every corner and every crossing of seams from the two layers. The most bricks at a point is four, reached where a seam of the lower layer crosses a seam of the upper — two bricks below, two above. A point at a T-junction of the lower layer lies inside a single brick of the upper, three plus one, also four; the layers are offset so that T-junctions above and below never coincide. A grid of cubes, for comparison, has eight cubes at every corner.

So the cube can be covered by small closed bricks with no point in five, and Lebesgue’s theorem in three dimensions says it cannot be done with no point in four. The pattern is one more than the dimension: two for a segment, three for a square, four for a cube, and $n + 1$ for the $n$-dimensional cube, where the staggered construction generalises and the theorem — proved by Lebesgue in outline in 1911 and completely by Brouwer in 1913 — forbids anything better.

Refining does not help #

Making the pieces smaller does not reduce the overlap; it only multiplies the places where the forced overlap occurs.

A grid with $k$ rows has $(k - 1)^2$ inner corners, each in four squares. A brick wall with $k$ rows has the same number, $(k - 1)^2$, of inner T-junctions — two on each brick’s upper edge, shared with the bricks around it — which is about two for every brick, each a point in exactly three bricks. As $k$ grows both counts grow without bound, and the maximum stays where it was. The theorem is about the square, not about any cover of it: whatever the cover, if its pieces are smaller than the square, three meet somewhere.

Dimension, defined by overlap #

Lebesgue turned this into a definition. A space has covering dimension $n$ if it can be covered by arbitrarily small closed pieces with no point in more than $n + 1$ of them, and $n$ is the least number for which this is possible. A segment needs overlaps of two, so it has dimension 1; a square needs three, so 2; the theorem above is the statement that the definition gives the $n$-dimensional cube the dimension $n$, as it should.

The definition applies to spaces with no obvious coordinates, and it sometimes surprises. The Cantor set can be covered by disjoint small closed pieces — the intervals of any stage of its construction, eight of them at stage three, separated by gaps — so its covering dimension is 0. Its fractal dimension, which counts how many small pieces are needed rather than how they must overlap, is $\log 2/\log 3 = 0.6309$. The two notions measure different things, and they agree on smooth shapes and disagree on fractals: the Koch snowflake curve has covering dimension 1 and fractal dimension 1.2619, the Sierpiński carpet covering dimension 1 and fractal dimension 1.8928.

Covering dimension is a topological invariant: a homeomorphism, a continuous bijection with continuous inverse, carries a small closed cover to a small closed cover with the same overlaps. So the theorem that the $n$-cube has covering dimension $n$ proves at once that cubes of different dimensions are not homeomorphic — the invariance of dimension that two pieces in every dimension approached through separation, and that Cantor’s correspondence between a line and a square made urgent. A continuous map that is not a homeomorphism can raise dimension, as a path that fills a square shows; covering dimension is preserved exactly by the maps that preserve topology and by nothing weaker.

The surprising connection: bricks and maps on a torus #

The brick wall has another life. Wrap a brick wall round a torus so that its left edge meets its right and its top meets its bottom, with seven bricks arranged in the right offset, and every brick touches every other: seven regions on a doughnut, each adjacent to all six others, which is why seven colours are needed to colour maps on a torus. The staggering that keeps the overlap down to three is exactly what makes each brick touch six neighbours rather than four or eight — every brick in a staggered wall has six neighbours, as every hexagon in a honeycomb does, because a cover in which three pieces meet at each corner is, combinatorially, a honeycomb. Covers of minimum overlap and maps with six neighbours a region are the same objects, which is why the brick wall, the honeycomb, the Hex board and the Voronoi diagram all look alike.

Covers that succeed, never covers that fail #

Every figure counts overlaps for particular covers: grids, walls, random cells. They show that three is achievable in the square and four in the cube, and that these covers cannot do better; they do not show that no cover can, which is the theorem. The impossibility is proved through Brouwer’s theorem, and no finite search over covers could establish it, since the covers that would have to be excluded are infinitely many and arbitrarily shaped.

The three-dimensional figure shows only the plane between two layers, since a solid cannot be drawn on a page without hiding most of it; inside each layer the count is the flat wall’s, three. The random cover is one sample from one seed, and its count of 90 three-fold points is specific to it.

Every corner tested, the impossibility quoted #

Computed here: the overlap at every corner and edge-crossing for grids and brick walls of 2 to 12 rows; the five strips and the same strips cut in two; sixty random Voronoi cells, clipped to the square one half-plane at a time, with every vertex tested against every cell; and two layers of brick walls in three dimensions, with every corner and crossing of either layer tested against every brick of both.

Quoted: Lebesgue’s theorem and its history, including Brouwer’s 1913 proof; the equivalences with Brouwer’s fixed point theorem, Sperner’s lemma and the Hex theorem, which earlier essays prove; the fractal dimensions of the Cantor set, the Koch curve and the Sierpiński carpet; and the seven-region map on a torus.

Still open: dimension for strange spaces #

For the spaces of ordinary geometry, covering dimension agrees with every other sensible notion of dimension, and the theory is complete. For general topological spaces it is not: covering dimension, the inductive dimensions defined by separating points from closed sets, and other variants can disagree, and examples separating them can be wild. For compact metric spaces they agree, a theorem of the 1920s and 1930s; for general spaces, the relations between them are a large classical subject with questions that remain open about which values can be realised together.

Closer to the pictures, there is a quantitative question. How small must the pieces be, relative to the square, before three are forced to meet? The sharp form says it is enough that no piece meets two opposite sides. For other shapes, and in higher dimensions, the corresponding thresholds — Lebesgue’s “covering constants” and their variants for pieces of bounded diameter — are known in some cases and open in others, and they connect to old problems about how small pieces can be when a set is cut into a given number of them, such as Borsuk’s question on cutting a set into pieces of smaller diameter.

One more than the dimension #

A square covered by closed pieces too small to span it must have a point in three of them, and a staggered brick wall shows that three is enough; a cube needs four, and staggered layers of bricks achieve four. Random cells meet three at a time without being arranged to, grids meet four at a time by coincidence, and refining any cover only multiplies the forced meeting points.

The forced number, minus one, is Lebesgue’s covering dimension, a topological invariant that gives every cube its dimension and gives the Cantor set dimension 0. Behind it stands the same fact about the disc as Brouwer’s fixed point theorem and the Hex board: in two dimensions, three regions must meet somewhere, and no cleverness in shaping the pieces can prevent it.