Graph Products

Leopold Kronecker was one of the great mathematicians of the 19th century. He thought about foundational issues deeply. We highlighted him before—well not deeply.

Today I thought we would talk about some core math ideas arising out of Kronecker’s work.

Kronecker’s angle as an early leader in the modern foundations of mathematics was on which aspects are helpful in concrete analysis. He no doubt would be comfortable with complexity theory, with our interest in not just existence proofs, but in concrete algorithms for the construction of objects. He famously said:

God made the integers, all else is the work of man.

His was a philosophy that would agree with our view of complexity theory. Maybe he would say now:

God made the binary strings, all else is the work of people.

Operations

In any part of mathematics we are often interested in operations that take objects and make new objects. These operations are important as they allow us to build new interesting objects.

• In strings we can take two and concatenate them to make a new one.

• In matrices we can add or multiply them.

• More relevant to today’s topic we can take two matrices and make the Kronecker product:

  

• In graph theory we can take two graphs and and make a new one .

There are a wealth of such operations on graphs. One is called Cartesian product, one the strong product, one the direct product. A trouble, in my opinion, is that the names and the notation for these operations is not uniform. There are alternative names for almost all the major operations: For example,

The Cartesian product of graphs is sometimes called the box product of graphs—see here. The notation that has often been used for Cartesian products of graphs, but is now more commonly used for another construction known as the tensor product of graphs.

Confusing, no?

Ken notes that it gets even more confusing when one teaches the Cartesian product construction of finite automata. Each automaton has a state graph. In general the state graph is directed and the edges are labeled by characters, but one can make cases where the graph is undirected and there is only one character. The state graph of the product machine is in general not the Cartesian product of the graphs of the individual machines. What product is it? Let’s look at graph operations.

Towards a Uniform Definition

Let us give a uniform definition of three basic graph products. Let be undirected graphs. Then

is the graph with vertices so that each is a vertex in , and the vertices and are connected provided for exactly indices , and are an edge in and for the rest .

• The Cartesian product requires exactly one edge:

  

  It is usually written as

  

• The strong product requires at least one edge:

  

  It is usually written as

  

• The tensor product requires all edges:

  

  It is usually written as

  

Here is a comparison of four graph products.

The answer to Ken’s question is that you get the tensor product, which is Kronecker’s product on the adjacency matrices of the graphs. This is because each step of the product requires an action by each constituent machine.

Of course then we get other types of products for other values of . Are any of these interesting? We get intermediate notions up to Kronecker’s product. Can the be put to any natural use?

Coloring Products—Conjecture

An application of graph products is that they yield some quite compelling conjectures. The conjecture due to Stephen Hedetniemi in 1966 is one example. This states that

Here is the number of colors needed to color . The conjecture is false–see Counterexamples to Hedetniemi’s conjecture by Yaroslav Shitov. Also see Gil Kalai’s post about this news.

Coloring Products—Proofs

A potential application of graph products is to the famous Four Color Theorem (4CT)—see here. In a paper of mine with Atish Das Sarma, Amita Gajewar, and Danupon Nanongkai we show:

Theorem 1 (An Approximate Restatement of the Four-Color Theorem) Suppose every two-edge connected, cubic, planar graph can be edge 3-colored with errors. Then the Four Color Theorem is true.

The proof is simple. We assume that some graph is a counterexample to the 4CT. Then form a kind of product of . To be honest we did not see the proof exactly as this, but is essentially what we did. The is a huge product of many of the copies of , with some small modifications. Then we show if we could almost four color then we would be able to exactly color .

Open Problems

Meanwhile, the paper showing that Hedetniemi’s conjecture is false contains an important lesson for mathematicians, Noga Alon says,

Sometimes, the reason that a conjecture is very hard to prove is simply that it is false.

[restored missing line in second sentence, other fixes]