Miscellaneous mathematical musings

by
Jan Kristian Haugland

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 graph which 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 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 in the graph of the BCC lattice here.) |

If we give each vertex one out of

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

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 2*n*+1 colours

Given a positive integer *n*, suppose each cell of the regular hexagonal grid is given one out
of 2*n*+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 2*n*^{2} 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