memoirs on a rainy day

Awesome photos from Chile’s recently reactivated Chaitén volcano merging with a lightning-infested thunderstorm. (via kottke)

Dr. Irwin Braverman, a Yale University physician who analyzed images of Akhenaten, has a new theory on why Akhenaten wasn’t the most manly pharaoh, even though he fathered at least a half-dozen children. (via cf)

The new Franco-Swiss supercollider could fill gaps in scientific knowledge or create a black hole!

Well I managed to squeeze in three full proposals for Google Summer of Code. I don’t know if I will be successful. It was pretty stressful trying to finish the last one on time. Next year, I’ll prepare my proposals well in advance.

I just finished a term paper for Teaching College Mathematics. I should get a good grade. I’ve been writing it for about a month. All that’s left is to create a power point and practice my oral presentation.

I’ve got two last assignments left to finish for the end of the semester. One is due next week and the other is due at the end of the term. On top of that, I’ve got four exams in two days during the last week of class.

I took some photos yesterday. I hadn’t notice that my camera was set-up for night shots. I took ISO 400 shots in sunny weather. They didn’t turn out too well.

Spring is finally here! We’ve lost a few feet of snow already and I’ve ditched my thermal pro insulation layer.

A big solar furnace in Uzbekistan. Temperatures reach up to 3000 degrees.

Sunday was consumed by research on spectral sequences, category theory, homological algebra, sheaf theory, topos theory, chain complexes, homotopy theory, cohomology, and functors (tor, ext, hom). These are all concepts of advanced algebra, graduate and doctoral level math in my opinion. I didn’t understand everything, but I’m thirsting for more knowledge on these concepts. When I’m at the library on Wednesday, I’ll pop by to get a few books on these subjects. Maybe I’ll just get and introduction to homological algebra.

I’ve already sent an email to the Analysis III professor asking for class notes so that I can read them and practice for the next semester.

The American Revolution was also on my mind. Since I was watching the John Adams mini-series on HBO, I was curious about certain facts. The Boston Massacre, the Boston Tea Party, the Battle of Bunker Hill, and the Join or Die articles were read.

I’m a bit annoyed at the mini-series. Why?

Well none of the great historical battles or events are portrayed in this series, at least until now. The characters witness them, but the viewers don’t see them. It’s annoying. I find that it cuts the narrative.

Last week, evolutionary biologist Dr. PZ Myers was expelled from the screening of the creationist movie Expelled. They didn’t notice Dr. Richard Dawkins as his guest, who managed to see the movie and to post his review. (via kottke)

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).

Israeli mathematician Avraham Trahtman solves the Road Coloring Problem. Mathematicians have been working on it since 1970. My rudimentary explanation of the problem and its proof. (Here is a link to the proof in PDF version)

Bubble Chamber is a generative painting system of imaginary colliding particles built with Processing. A single super-massive collision produces a discrete universe of four particle types. Particles draw their positions over time resulting in the construction of oddly familiar patterns. (via cpluv)