{\huge Guessing Conjectures}

How well can we guess the right side of conjectures? \vspace{.5in}

Takaaki Kajita and Arthur McDonald won the 2015 Nobel Prize in Physics for their discovery that neutrinos have mass. Although some physicists had shown as early as the 1950s that standard particle models could accommodate neutrinos with mass, there was no compelling reason for it. Moreover, the terms for neutrino mass lack the desirable mathematical property of renormalizability. So most physicists of the last century guessed that neutrinos would be massless like photons are.

Today Ken and I want to talk about guessing the answers to problems and conjectures in mathematics.

That photons have mass came from experiments but in a way that remains in some sense ``nonconstructive''---the experiments do not tell you how to measure the mass. Instead, Kajita and his team at Japan's Super-Kamiokande neutrino detector discovered in 1998 that one of the three major types of neutrinos had different statistical frequency depending on whether they came through the earth or from overhead. McDonald's team at the Sudbury Neutrino Observatory showed convincingly in 2001 that neutrinos were permuting themselves among the three types in transit from the sun to the earth. Together their results explained a long-mysterious huge dropoff observed by experiments that detected only the type chiefly produced in the sun. The type changes were known to be possible only if the terms for neutrino mass are present.

Of course mathematicians cannot do experiments to test conjectures---or maybe in some cases we can? But they do have a feel for how ``models'' of potential mathematical reality that haven't been proved hang together. Some sides of conjectures confer more desirable mathematical properties on larger structures.

As a game for you---our readers---we will describe some problems that were solved, and invite you to guess the answers without looking up the solutions. We will give the solutions in our next post, which will have a Halloween theme. The answers won't scare off interest in the conjectures because many matters related to them are still open. Likewise the matter of neutrinos: all we know are differences in the squares of their masses, and the experiments so far have not even distinguished which of two plausible mechanisms may cause the mass to arise.

The Angel Problem

The first problem is the Angel Problem, created by John Conway. Two players called the angel and the devil play on an infinite chessboard---always chess, hmmm. The angel can fly to any square that is within $latex {k}&fg=000000$ king moves---that is, any place in the $latex {(2k+1)\times(2k+1)}&fg=000000$ quadrant centered on her current location. The devil at each turn can put a block on any one empty square. The game is won by the devil provided the angel cannot move. Since the angel can fly over blocks but never onto them, this happens if and only when the devil takes the last unoccupied square in the angel's current quadrant. The angel wins by surviving indefinitely.

Here is an illustration from the applet on Oddvar Kloster's page on the problem---we've painted on the blue boundary for $latex {k = 2}&fg=000000$. The angel may move to any square within the blue quadrant except three that the devil has blocked. The picture also shows the devil blocking three squares further away in case the angel flies in that direction. The shading has to do with one side's strategy---don't look on his page yet for the answer.

\includegraphics[width=3in]{AngelDevils.png}

The problem asks, Who wins the game?---and more particularly:

Is there a finite $latex {k > 1}&fg=000000$ such that the angel wins?

For $latex {k = 1}&fg=000000$ the angel is just a chess king loses to a devil who plays entirely within a $latex {32 \times 33}&fg=000000$ grid---note this is asymmetrical since the devil without loss of generality plays first. So $latex {k}&fg=000000$ must be at least 2. A funny feature is that higher $latex {k}&fg=000000$ effectively gives the devil more blocks per turn. The reason is that if the angel has a winning strategy, then she has one that never visits a square that was within a previous quadrant. If visiting that square is now optimal then so would have been visiting it earlier when the devil had blocked fewer squares. Thus she might as well be a Destroying Angel who bombs out every square of her quadrant other than the one she chooses at each turn. Larger $latex {k}&fg=000000$ means more bombing of the same $latex {\sim k^2}&fg=000000$ order as her greater mobility. Conway's writeup shows that several natural simple strategies for the angel lose for every $latex {k}&fg=000000$.

The question is: Can the devil win for any $latex {k}&fg=000000$? Is he able to build a clever wall starting far away that eventually encircles the angel? Or is there some $latex {k > 1}&fg=000000$ that gives the angel eternal freedom? Which do you believe is true?

Four Others

$latex {\bullet}&fg=000000$ Equitable Coloring.

A $latex {k}&fg=000000$-coloring of an $latex {n}&fg=000000$-vertex graph is a mapping $latex {f: [n] \rightarrow [k]}&fg=000000$ such that for each ``color'' $latex {j}&fg=000000$, no two vertices $latex {u,v}&fg=000000$ such that $latex {f(u) = f(v) = j}&fg=000000$ are adjacent. The coloring is equitable provided for each $latex {j \in [k]}&fg=000000$ the number of vertices $latex {u}&fg=000000$ given color $latex {j}&fg=000000$ is either $latex {\lfloor n/k \rfloor}&fg=000000$ or $latex {\lceil n/k \rceil}&fg=000000$. That is, no two color classes differ in number by more than one vertex. If $latex {k}&fg=000000$ divides $latex {n}&fg=000000$, so $latex {n = rk}&fg=000000$, then every color must be used exactly $latex {r}&fg=000000$ times.

Rowland Brooks proved that every graph of degree $latex {d}&fg=000000$ other than complete graphs and odd cycles has a $latex {d}&fg=000000$-coloring. The complete bipartite graph $latex {K_{3,3}}&fg=000000$ has no equitable 3-coloring, though it has an equitable 2-coloring. The question is: Does every graph of degree $latex {d}&fg=000000$ have an equitable coloring using exactly $latex {(d+1)}&fg=000000$ colors?

$latex {\bullet}&fg=000000$ Star Height The star-height problem in formal language theory is the question of whether there is $latex {k > 1}&fg=000000$ such that all regular languages have regular expressions that have at most $latex {k}&fg=000000$-fold nesting of Kleene stars. It was easy to show a no answer over alphabets of arbitrary size. The question is: Is there a bound on $latex {k}&fg=000000$ if the alphabet is binary?

$latex {\bullet}&fg=000000$ Scheinerman's Conjecture Edward Scheinerman conjectured in his 1984 PhD thesis that every planar graph can be represented as the intersection graph of a set of line segments in the plane. This is easy to see if you are allowed arbitrary curves in the plane, since you can replace a vertex of degree $latex {d}&fg=000000$ by a curve that winds itself around in a $latex {d}&fg=000000$-pointed star. But doing it with straight line segments seems quite a challenge. We reproduce Wikipedia's example for an 8-vertex planar graph:

\includegraphics[width=3.5in]{ScheinermanWiki.png}

The question is: Is it always possible? Note that the above example uses only lines with 4 orientations with no two segments of the same orientation touching. Such a graph can be 4-colored by making each orientation a separate color, so a yes answer using only 4 orientations implies the four-color theorem. But we are getting ahead of ourselves---is it possible at all?

$latex {\bullet}&fg=000000$ Road Coloring Problem Suppose we have a directed graph $latex {G}&fg=000000$ in which every vertex has the same out-degree $latex {d}&fg=000000$. Let us use the same alphabet of $latex {d}&fg=000000$ characters to label the $latex {d}&fg=000000$ out-edges from every node. Then for every vertex $latex {u}&fg=000000$ and string $latex {x}&fg=000000$ of these characters, using successive characters of $latex {x}&fg=000000$ as directions on which out-going ``road'' to take determines a unique path $latex {P}&fg=000000$ of length $latex {|x|}&fg=000000$ in the graph. If the path ends at a vertex $latex {v}&fg=000000$ we write $latex {P(u,x) = v}&fg=000000$. If we get the same $latex {v}&fg=000000$ for all $latex {u}&fg=000000$---even $latex {u=v}&fg=000000$ itself---then $latex {x = x_v}&fg=000000$ is a universal sequence of road directions to reach vertex $latex {v}&fg=000000$. For a particular $latex {G}&fg=000000$ we can ask:

Can we assign $latex {d}&fg=000000$ labels so that every $latex {v}&fg=000000$ has a universal string $latex {x_v}&fg=000000$?

If $latex {G}&fg=000000$ has no directed cycles then the answer is clearly no---you can never get to a source. If all cycles have even length then a parity argument shows no, and it works if all cycle lengths are divisible by some odd number as well. For all other $latex {G}&fg=000000$, is it possible? That is the question.

Open Problems

Without looking the answers up, can you guess them? We have stated the italicized yes/no questions in such a way that the numbers of 'yes' and 'no' answers are equitable.