Miscellaneous mathematical musings
by Jan Kristian Haugland

 Contents The regular 600-cell: Colourings and induced subgraphs Induced components of the hexagonal grid with n out of 2n+1 colours Largest polyomino with no four cells equally spaced on a straight line Dissection puzzles My Petersen graph tattoo

The regular 600-cell: Colourings and induced subgraphs

The graph of
the regular 600-cell contains 120 vertices and is 5-colourable. Up to graph isomorphism,
there are 23 different induced subgraphs with 28 vertices and maximum degree 1, listed here,
and 4 different induced subgraphs with 37 vertices and maximum degree 2, listed here.

 The subgraph induced by 2 colours of a 5-colouring (a graphwhich is isomorphic to the cubic symmetric graph F48A, illustrated here on the right side - 3D printed model for sale at Shapeways) can be shown to be the only induced subgraph with48 vertices and maximum degree 3, up to graph isomorphism. Here is a list of known 2-regular connected induced subgraphswith 36 vertices, with their knot types. (On a related note, knot types of cycles in the graph of the regular 24-cell arediscussed here, and in the graph of the BCC lattice here.) If we give each vertex one out of k available colours, and consider all the k subgraphs
induced by the colours, what is the minimal size of the largest connected component?
These examples give upper bounds 40, 15 and 3 in the cases k = 2, 3 and 4 respectively. The latter bound
is tight; this follows from the already mentioned result on induced subgraphs with maximum degree 1.

Induced components of the hexagonal grid with n out of 2n+1 colours

Given a positive integer n, suppose each cell of the regular hexagonal grid is given one out of 2n+1 available colours.
Let h(n) denote the smallest possible value (if any) of the maximal number of cells in any
connected component induced by
any n of the colours. We have h(2) = 4, and this is attained by essentially only two distinct colourings, shown here and here.

In the case n = 3, there is a colouring that yields a maximum of 9 cells, shown here.
Is it optimal? Is it unique? I have verified that h(3) ≥ 8; i.e., h(3) {8, 9}.

An example that yields h(4) ≤ 24 is shown here.

If we instead consider the square grid, and assume that two cells must have a common edge in
order to be considered adjacent, then it is relatively easy to attain 2n2 cells for n out of n+1 colours.
The case n = 3 is shown here, and the reader should be able to spot the pattern for the general case.

Largest polyomino with no four cells equally spaced on a straight line

The number of cells in a
polyomino with no four cells equally spaced on a straight line, is bounded.
This can be verified, for example, by generating all such polyominoes having Hamiltonian paths.
The highest feasible number of cells that I have found is 142, as attained by the following example. Variant 1   Variant 2   Variant 3   Variant 4   Variant 5

Dissection puzzles

The following puzzle dates back to
Sam Loyd (1908): Dissect a 7×7 square into five pieces, and reassemble the pieces into a 6×6, a 3×3
and a 2×2 square. The pieces can be rotated but not flipped over (mirrored).

With computer aid I have found that there are 246 solutions, assuming that the cuts must be along the grid lines.

List of solutions

Solutions sorted by cut length

Here is a similar puzzle. Dissect a 6×6 square into three pieces, and reassemble the pieces into a triangle with base 8 as seen in the figure: There are only two solutions (same assumption as above). The corresponding puzzle with hexagonal cells has 41 solutions.