Skip to content

Graph Products

February 4, 2021


The power of definitions and notations

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 {G_1} and {G_2} and make a new one {H}.

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 {G \times H} 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 {G_1,\dots,G_m} be undirected graphs. Then

\displaystyle  H = \square(d,G_1,\dots,G_m)

is the graph with vertices {(x_1,\dots,x_m)} so that each {x_k} is a vertex in {G_k}, and the vertices {(x_1,\dots,x_m)} and {(y_1,\dots,y_m)} are connected provided for exactly {d} indices {k}, {x_k} and {y_k} are an edge in {G_k} and for the rest {x_k=y_k}.

  • The Cartesian product requires exactly one edge:

    \displaystyle  \square(1,G_1,\dots,G_m).

    It is usually written as

    \displaystyle  G_1 \square\cdots \square G_m.

  • The strong product requires at least one edge:

    \displaystyle  \bigcup_{d \ge 1}\ \square(d,G_1,\dots,G_m).

    It is usually written as

    \displaystyle  G_1 \fbox{x} \cdots \fbox{x} G_m.

  • The tensor product requires all edges:

    \displaystyle  \square(m,G_1,\dots,G_m).

    It is usually written as

    \displaystyle  G_1 \times \cdots \times G_m.

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 {d}. 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

\displaystyle  \chi (G \times H) = min( \chi (G), \chi (H)).

Here {\chi(G)} is the number of colors needed to color {G}. 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 {G} can be edge 3-colored with {o(n)} errors. Then the Four Color Theorem is true.

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

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]

4 Comments leave one →
  1. PandaItchpress permalink
    February 5, 2021 3:56 pm

    Perhaps p not np is false?

  2. javaid aslam permalink
    February 6, 2021 6:48 pm

    The graph isomorphism and the P vs. NP both have remained open problems, with graph isomorphism for an even longer time (whether in P)?
    So how do we interpret the hardness of proving a “conjecture”?

  3. Peter Gerdes permalink
    February 10, 2021 12:14 pm

    If would be really helpful if you could include the pictures of K_2 and P_2 on their own. But interesting post. I can’t help but be reminded by that theorem of the use of ultrapowers in model theory/set theory.

Trackbacks

  1. 55 Best Computer Science Blogs (+ Example Articles)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s