https://rjlipton.wordpress.com/2021/02/04/graph-products/ Skip to content Godel's Lost Letter and P=NP a personal view of the theory of computation * Home * About P=NP and SAT * About Us * Conventional Wisdom and P=NP * Thanks to An Explainer * The Godel Letter * Cook's Paper * Thank You Page Graph Products February 4, 2021 tags: direct, Four color theorem, planar, products, strong product, tensor by rjlipton The power of definitions and notations [kro] 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: [prod] * 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. [prod2] 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] Share this: * Reddit * Facebook * Like this: Like Loading... Related from - Ideas, Oldies, Open Problems, People, Proofs - Alan Selman, 1941-2021 Pigenhole Principle - 4 Comments leave one - 1. [b5818f1] PandaItchpress permalink February 5, 2021 3:56 pm Perhaps p not np is false? Reply 2. [f7d54f7] 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"? Reply 3. [6b94914] 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. Reply Trackbacks 1. 55 Best Computer Science Blogs (+ Example Articles) Leave a Reply Cancel reply Enter your comment here... [ ] Fill in your details below or click an icon to log in: * * * * * Gravatar Email (required) (Address never made public) [ ] Name (required) [ ] Website [ ] 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 ) Cancel Connecting to %s [ ] Notify me of new comments via email. [ ] Notify me of new posts via email. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] * Subscribe to Godel's Lost Letter [a28] * [type and press enter] * Our Book [lrqmitbookcover] Click image for our page, with errata and links. * Recent Posts + A Quiz of Quotes + Riemann Hypothesis--Why So Hard? + Computing's Role In The Pandemic + Alan Selman + Pigenhole Principle + Graph Products + Alan Selman, 1941-2021 + Happy Un-Birthday Rich + Science Advisor + Edmund Clarke, 1945-2020 + Priming Random Restrictions + Predictions For 2021 + Peter M. Neumann, 1940-2020 + P < NP In Our Stockings? + Database and Theory * Top Posts + Graph Products + A Quiz of Quotes + Riemann Hypothesis---Why So Hard? + The Amazing Zeta Code + Integer Multiplication in NlogN Time + The Godel Letter + Computing's Role In The Pandemic + Is P=NP an Ill Posed Problem? + Pigenhole Principle + The Cantor-Bernstein-Schroder Theorem * Recent Comments [64ede] javaid aslam on A Quiz of Quotes [9e0cd] LongtimeLurker on A Quiz of Quotes [53463] Jon Awbrey on A Quiz of Quotes A Quiz of Quotes | G... on Thinking Out of the Notation... A Quiz of Quotes | G... on Cantor's Non-Diagonal Pr... A Quiz of Quotes | G... on The Cantor-Bernstein-Schroder... [image] Voronin's insi... on Riemann Hypothesis--Why S... 55 Best Computer Sci... on Graph Products [0a840] WP on Riemann Hypothesis--Why S... [f8940] miklosi on Pigenhole Principle [7f5bf] KWRegan on Riemann Hypothesis--Why S... [b127c] Ivan Gusev on Riemann Hypothesis--Why S... [93328] Anonymous on Riemann Hypothesis--Why S... [pictu] Frank Vega on Riemann Hypothesis--Why S... Riemann Hypothesis... on Hunting Complexity in Zet... * Blogroll + Alex Walker + Algorithmic Game Theory + Algorithms, Nature, and Society + AMS + Annoying Precision + Azimuth Project + Banach's Algorithmic Corner + Bits and Pieces + Blame It On The Analyst + Computational Complexity + Division by Zero + Ernie's 3D Pancakes + gentzen + Gil Kalai + Gowers's Weblog + Jon Awbrey + Kamathematics Home + Luca Trevisan + M-Phi + Martin Schwarz + math less traveled + mathbabe + Matt Baker + Michael Mitzenmacher + Michael Nielsen + Minimizing Regret + My Biased Coin + Not Even Wrong + Oddly Shaped Pegs + Peter Cameron's Blog + Pink Iguana + prior probability + Random bits + Rich DeMillo + Rigorous Trivialities + Scott Aaronson + Sebastian Pokutta + Secret Blogging Seminar + Suresh Venkatasubramanian + Tanya Khovanova + tcs math + Terence Tao + the Higher Geometer + The Mathematical Tourist + The nth Root + the polylogblog + The Unapologetic Mathematician + Todd and Vishal's blog + Turing Machine + windows on theory * Archives Archives [Select Month ] * Sitemeter Site Meter * wordpress stat Blog at WordPress.com. Add your thoughts here... (optional) [ ] Post to [] Cancel [Reblog Post] [ ] Email (Required) [ ] Name (Required) [ ] Website [ ] [Post Comment] Loading Comments... Comment x %d bloggers like this: [b]