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 (illustrated here -
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 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 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