Hunting The Angry Pig: Personal Notes

Matt Brubeck

September 19, 2002

1 Introduction

These are working notes for my research with Professor Levin into fractional analogues of the Four Color Theorem. This research is a continuation of Ari Nieh’s senior thesis.

2 How General is Our Approach?

One question we’ve asked is how broad a statement we can make about fractional analogues to Tait’s Theorem. The central idea in Tait’s Theorem is the creation of a face coloring from an edge coloring, by labeling the edges and letting an edge label determine the relationship between the two faces adjacent to that edge.

If we operate by the basic mechanism of Tait’s Theorem—label one face, then label the other faces by crossing edges and letting the edge labels act on the face labels–then the edge labels must lie in a group. They act associatively, because we can cross three edges in sequence and the result is well-defined. The edges around a vertex act as the identity. Finally, each label’s action must be its own inverse, which means that the group must be isomorphic to ℤ_{2}^{k} for some k.

3 Non-Injective g

In Ari’s hypothesized analogue to Tait’s Theorem, a function f maps edge color sets to binary strings, and a second function g maps binary strings to face color sets. Ari proves that f’s range always includes least 11 distinct edge strings. He then proves that a consistent g is combinatorially impossible.

The proof of this used a hypergraph argument, and implicitly assumed that g was one-to-one. However, if g is not one-to-one we can use a multi-hypergraph and still complete the proof.

Proof: We can model g as a hypergraph problem. If g exists in this case, then there must exist a hypergraph with 4t vertices (representing the colors) and 16 t-hyperedges. If g is not one-to-one, the hypergraph will have multiple edges. It must be the case that none of these 16 hyperedges intersects more than four others. Such a hypergraph is a combinatorial impossibility.

Ari’s Theorem 4.2.1 is valid for hypergraphs with multiple edges, and its proof needs no modification.

4 Length-5 Strings

choose4.m finds

• 700 with 7 distinct rows • 12600 with 11 distinct rows

• 840 with 15 distinct rows

choose5.m finds

• 420 with 7 distinct rows

• 4032 with 11 distinct rows

• 86016 with 15 distinct rows

Furthermore, some of these matrices have rank 5. Here is an example, found and verified with Matlab:

12 0 0 1 1 0
13 0 1 0 1 0
14 0 1 1 0 1
15 0 1 1 1 0
16 0 1 1 1 1
23 1 0 0 1 1
24 1 0 1 0 0
25 1 0 1 1 1
26 1 0 1 1 0
34 1 1 0 0 0
35 1 1 0 1 1
36 1 1 0 1 0
45 1 1 1 0 0
46 1 1 1 0 1
56 1 1 1 1 0

The next step is to find if it is possible to construct a consistent g based on any of these rank-5 matrices. At first glance it appears that such a g may be possible. For example with t = 2 we are mapping 32 strings to 28 color pairs, requiring that each be disjoint from the images of 15 potentially adjacent strings. This problem is equivalent to placing 32 edges onto a size-8 multigraph (or in general, 32 t-hyperedges on a size 4t multi-hypergraph).

Unlike when l = 4, this does not run into immediate packing problems.

One possible approach: For each of these possible sets of edge labels, consider the 32-vertex graph H whose edges are the pairs of labels that may legally appear on adjacent faces (i.e. their sum is not one of our edge labels). Vertices of this graph correspond to edges of the 8-vertex graph considered above, which we will call G. Edges in G can be incident only if the corresponding vertices are adjacent in H.

If the clique number of H is 7, then each vertex in G must have degree at most 7. This allows for at most 7 × 8 = 56 edge–vertex incidences in G, but we need 32 × 2 = 64 edge–vertex incidences. This approach works for the general case of t-fold face colorings, where we have 7 × 4t > 32 × t.

The difficulty in applying this result is that it requires testing the clique number of a large number of 32-vertex graphs (one for each possible set of edge labels), which may be computationally infeasible. The graphs are vertex-transitive, and this structure may make the task easier. There may also be a large degree of similarity between the graphs, which could reduce the number of cases.

5 AX decomposition of G

Let A be the 15 × 6 bit-matrix whose rows are all six-element vectors with exactly two zeros. That is, A represents all the pairs from a 6-element set, but in the converse of the normal representation.

Let X be the 6×64 matrix whose columns are all possible 6-element bit-vectors. Then AX = G, with one caveat. Because A maps a vector and its binary complement to the same value, only half the columns in G are distinct. So although G has 64 columns, it has only 32 distinct columns.

This formalizes the notion of labelling columns in G with subsets of {1 … 6}. Every such subset, represented by a 6-element column vector of X, is mapped to a column of G by the linear transformation A.

This new method of generating G is easily generalized to higher values of b, but we have yet to show in general that it is equivalent to Ari’s definition of G in terms of constraints on its columns.

It is easy to show one direction of the equivalence: Rows a_{i}, a_{j}, a_{k} of A sum to zero if and only if they represent disjoint pairs of colors; if some color appeared in none of the three pairs there would be a 1 in the corresponding bit of a_{i} + a_{j} + a_{k}. The corresponding sum g_{i} + g_{j} + g_{k} of rows in G is equal to (a_{i} + a_{j} + a_{k}) · X, which equals zero if and only if a_{i} + a_{j} + a_{k} = 0.

6 Miscellany

1. The coloring of the dodecahedron on page 12 of Ari’s thesis has two edge labels interchanged (16 and 24, on the rightmost “petal”).