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 (illustrated
here) can be shown to be the only induced subgraph with 48 vertices and maximum degree 3, up to graph isomorphism.

Here is a list of known 2-regular connected induced subgraphs with 36 vertices, with their knot types.

(On a related note, knot types of cycles in the graph of the regular 24-cell are discussed here, and of 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.


My Petersen graph tattoo