Miscellaneous meta-mathematics

Miscellaneous meta-mathematics
by Jan Kristian Haugland

"Colouring" the 600-cell

The graph of the regular 600-cell contains 120 vertices. Suppose we give each vertex one out
of k possible colours, and let r denote the cardinality of the largest connected monochromatic
subset of vertices. Given k, what is f(k), the minimal value of r? Here are my results so far.

f(1) = 120: Completely trivial.

f(2) ≤ 40: Confer example a. I suspect that this is optimal, but currently I do not have a proof.

f(3) ≤ 15: Confer example b.

f(4) = 3: Confer example c. Colours 3 and 4 induce subgraphs with 36 vertices and three vertices in each
connected component, and this is essentially the only way to achieve this. Colours 1 and 2 induce
subgraphs with only two vertices in each connected component, and with colours 3 and 4 in place,
this can also be achieved by switching colours of all vertices marked 'A', and/or all vertices marked 'B'.

It is possible to verify directly with a computer search that f(4) > 2, but I have also verified
a stronger result: The maximal number of vertices of an induced subgraph of the graph of
the regular 600-cell such that no connected component contains more than two vertices is 28.
The optimal solutions (one representative for each symmetry class) are listed here.

f(5) = 1: I.e., the graph is 5-colourable in the conventional sense. Left as an exercise. Any two colours
will induce a cubic subgraph with girth = 8 - and this inspired my work on grid subgraphs.

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

I believe the maximal number of cells is 142, but I do not have a proof. It is
easy to verify that the maximum exists - by generating all possible "paths".

Each red line in the figure joins two grey cells. Delete one of them and paint the other
one black for each line, and you have a feasible 142omino (provided it is connected).

Alternative illustration

Carpet cutting puzzles

The following puzzle dates back to Sam Loyd (1908):

Cut a 7×7 carpet into five pieces in such a way that the pieces can be put together to form
a 6×6, a 3×3 and a 2×2 carpet. 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. Cut a 6×6 carpet into three pieces in such a way that
the pieces can be put together to form 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.

How about this triangle-hexagon transformation?

I found some solutions with four pieces.

My Petersen graph tattoo

f(1) = 120:		Completely trivial.
f(2) ≤ 40:		Confer example a. I suspect that this is optimal, but currently I do not have a proof.
f(3) ≤ 15:		Confer example b.
f(4) = 3:		Confer example c. Colours 3 and 4 induce subgraphs with 36 vertices and three vertices in each connected component, and this is essentially the only way to achieve this. Colours 1 and 2 induce subgraphs with only two vertices in each connected component, and with colours 3 and 4 in place, this can also be achieved by switching colours of all vertices marked 'A', and/or all vertices marked 'B'. It is possible to verify directly with a computer search that f(4) > 2, but I have also verified a stronger result: The maximal number of vertices of an induced subgraph of the graph of the regular 600-cell such that no connected component contains more than two vertices is 28. The optimal solutions (one representative for each symmetry class) are listed here.
f(5) = 1:		I.e., the graph is 5-colourable in the conventional sense. Left as an exercise. Any two colours will induce a cubic subgraph with girth = 8 - and this inspired my work on grid subgraphs.