Terra Nova Proof S01E07 (Fox)

Terra Nova billboard via Fox

It took some time, but I’m glad that we managed to see Terra Nova. The pilot had been delayed for a while, ever since last May. I didn’t expect much, since I don’t really keep apprised of the latest TV news, but I was happily surprised with the pilot. The setting is quite interesting. While the future 2149 setting isn’t really that important, it set the mood nicely. It was a sort of Big Brother-like future, where people weren’t allowed to have many children and the Earth was becoming non-sustainable for human life. The time fracture, opening 85 million years into the past, allows different pilgrimages to settle in healthy biosphere, but populated by dinosaurs. I like the fact that this isn’t the same timeline as before. They entered another worldine, which is the only way that this could make sense.

Warning: Spoilers ahead.

Continue reading “Terra Nova Proof S01E07 (Fox)”

Road Coloring Problem

Until recently, the Road Coloring theorem was known as the Road Coloring conjecture. This means that it was a hypothesis that had not yet been proven by anyone. Avraham Trahtman proved it in September 2007. It therefore became a mathematical theorem. The conjecture of this problem was first made in 1970 by Benjamin Weiss and Roy Adler.

The Road Coloring theorem is part of a branch of mathematics called graph theory. Graphs are a bit like networks, maps or grids. They can be used to represent the structure of a website, road networks, and other situations which can be modeled by a graph.

Graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection. A “graph” in this context refers to a collection of vertices or ‘nodes’ and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another.

In layman’s terms, the issue is to find out if by using instructions, you can reach or locate an object or destination from any point within a network. Of course, here when we use network, we mean the non-mathematical definition of a network. A network in graph theory is a digraph with weighted edges, such as the lengths of a road in a road graph representation. With networks, you can analyze traffic networks, transportation networks and other such type of networks.

The solution appears to be completely counterintuitive. For example, it can be expressed as the following analogy. Whether a man who arrives in a city without street names to visit a friend and telephones for help, could be given directions which would work wherever he was at the time.

Consider the above directed graph. Each vertex (node in the graph) has an out-degree of 2. That simply means that two paths go out from each vertex. Each vertex also has an in-degree of 2. Two paths always lead to each vertex. However, for a synchronizing coloring to exist, we need a constant out-degree for all its vertices. In this case, it’s 2. The edges (or paths) have been colored in red and blue to create a synchronizing coloring (a type of graph labeling).

Graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called “colors” to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Consider the vertex marked in yellow. No matter on which vertex you start, if you traverse all nine edges in the walk “blue-red-red—blue-red-red—blue-red-red”, you will end up at the yellow vertex. Similarly, if you will always end up at the green vertex by using this walk “blue-blue-red—blue-blue-red—blue-blue-red”.

The road coloring theorem states that for a certain category of directed graphs, it is always possible to create a synchronizing coloring. The graph needs to be strongly connected and aperiodic.

A directed graph is said to be aperiodic if there is no integer k > 1 that divides the length of every cycle of the graph. Equivalently, a graph is aperiodic if the greatest common divisor of the lengths of its cycles is one; this greatest common divisor for a graph G is called the period of G.

A directed graph is called strongly connected if for every pair of vertices u and v there is a path from u to v and a path from v to u. The strongly connected components (SCC) of a directed graph are its maximal strongly connected subgraphs. These form a partition of the graph. If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph.

Synchronizing coloring corresponds to the synchronizing word in deterministic finite state automaton theory, a field of research stemming from combinatorics.

The road coloring problem is important in automata theory. It makes the behavior of an automaton resistant against input errors. Once an error is detected, a synchronizing word can reset the automaton to its original state, as if no error had occurred.

A coloring of a directed finite graph is synchronizing if the said coloring turns the graph into a deterministic finite state automaton processing a synchronizing word.

In his paper, Trahtman uses 7 lemmas that he proves and three theorems to lead to his final theorem, which proves the road coloring conjecture. In mathematics, theorems can often be deduced and easily proven from lemmas. Lemmy 7 the most significant.

The set of all outgoing edges of a vertex is called a bunch if all these edges are incoming edges of only one vertex.

A spanning subgraph S is a subgraph of an aperiodic finite strongly connected directed graph Γ all of the vertices of Γ belong to S and exactly one outgoing edge of every vertex of Γ.

A synchronizing pair of states p and q of an automaton is called stable if for any word u the pair pu, qu is also synchronizing.

Theorem 2 [J. Kari. Synchronizing finite automata on Eulerian digraphs, Theoretical Computer Science 295 (2003), 223–232]

Let us consider a coloring of aperiodic finite strongly connected directed graph Γ. The stability of states is a binary relation on the set of states of the obtained automaton; we denote this relation by ρ. Then ρ is a congruence relation, Γ/ρ is an aperiodic finite strongly connected directed graph and a synchronizing coloring of Γ/ρ implies synchronizing recoloring of Γ.

Lemma 7
Let any vertex of an aperiodic finite strongly connected directed graph Γ have no two incoming bunches. Then Γ has a spanning subgraph such that all its vertices of maximal positive level belong to one non-trivial tree.

This leads to his third theorem in this paper.

Theorem 3
Any aperiodic finite strongly connected directed graph has a coloring with stable couples.

Which leads him to conclude his final theorem, which is inferred from theorem 3 and 2.

Theorem 4
Every aperiodic finite strongly connected directed graph has synchronizing coloring.

The proof is complex for laymen to understand. Mathematicians specializing in graph theory can fully grasp the implications and the proofs. As a mathematics student, most of it is above my level of understanding of graph theory and combinatorics, but I can partly understand it at times. Here is a link to the proof.

As mentioned before, the result is counterintuitive, but the road coloring problem is for a finite directed graph that is strongly connected and aperiodic, which doesn’t make it any less difficult to prove. Over a hundred mathematicians over the last 37 years have tried to prove this problem. Avraham Trahtman is a 63 year old professor of mathematics at Bar-Ilan University (Israel).

Team Work

Today I was doing a team assignment in Analysis I with four other guys. In our usual team, one guys had abandoned the class. Another guy joined us. He’s annoying because he speaks very loud and he’s about 50 years old. I don’t have anything against older people, but he kept trying to talk over and to push his point across while I was completing a proof [proving that a non-specified function was continuous on an arbitrary interval (-δ,δ)]. In the end, it seemed to me rightfully that the work was only done by two people.

Rémi and I also copied our work to give it to the professor. [these team assignment last one hour and we have to hand in our work at the end of the class]. I wasn’t a happy camper, especially since I stayed the extra five minutes to make sure that my proof was flawless. Everyone else had left. I don’t fault Rémi, he works had and did his part. But the other two idiots didn’t do squat. In fact, one of them asked the professor to explain something that he hadn’t understood during class, the continuity of a function on a point. I was pissed, because he hadn’t done anything.

Can you imagine trying to complete a mathematical proof on paper, while another guy is almost screaming in your ears? I had my hands on my ears in an effort to focus on what I was doing. That guy didn’t contribute anything to the work. He distracted us mostly. I’ll have to talk about this with Rémi.

I’ve included the problem and the answer, written in M$ Word 2007 thanks to M$ Equation, converted into PDF then into an image.

%d bloggers like this: