- Input: Graphs \(H_1,\dots,H_k\) and integers \(a_1,\dots,a_k\text{.}\)
- Question: Is it true that \(\sum_{i=1}^ka_i\hom(H_i,G)\geq0\) for every graph \(G\text{?}\)
Section 9.1 Undecidability of Homomorphism Counting Inequalities
In Chapter 8, we focused on the problem of maximizing or minimizing \(\hom(G,(a,W))\) for a fixed choice of target \((a,W)\) over all input graphs \(G\) satisfying certain conditions (e.g. all \(d\)-regular graphs). We will now turn our focus to the problem of fixing the input graph and maximizing or minimizing over all targets satisfying a certain condition. We will usually refer to the (fixed) input graph by \(H\text{.}\) The target will be denoted by \(G\) whenever it happens to be a graph; for matrices, we will still write \(W\) or \((a,W)\) for the target.
If one is trying to determine the maximum or minimum of \(\hom(H,G)\) for fixed \(H\) over all targets \(G\text{,}\) a natural approach is to try to bound \(\hom(H,G)\) in terms of \(\hom(H_1,G),\dots,\hom(H_k,G)\) for some other graphs \(H_1,\dots,H_k\) and try to use known properties of the graphs \(H_1,\dots,H_k\) to get the bound that you want. For example, way back in Section 4.2 in these notes, we obtained an upper bound on \(\hom(C_4,G)\) by proving
\begin{equation*}
\hom(C_4,G)\leq \frac{\hom(P_3,G)^2}{\hom(K_1,G)^2}\leq \frac{\hom(K_2,G)^4}{\hom(K_1,G)^4}
\end{equation*}
which is asymptotically tight by taking \(G\) to be a large random graph. In other words, every \(G\) satisfies
\begin{equation*}
0\leq \hom(K_2\sqcup K_2\sqcup K_2\sqcup K_2,G) -\hom(C_4\sqcup K_1\sqcup K_1\sqcup K_1\sqcup K_1,G)
\end{equation*}
It would be very useful to have an algorithm to determine whether a given linear inequality involving homomorphism counts is satisfied by every graph \(G\text{.}\) Let us formalize this.
Problem 9.1.1.
You are probably familiar with the idea that some combinatorial problems are “harder” than others. This is often discussed in the context of the P vs. NP problem. That is, problems that are in P are deemed to be tractable while problems that are NP-hard or NP-complete are deemed to be intractable. For example, the problem of deciding whether a graph is 3-colourable is deemed intractable because it is NP-complete. However, NP-complete problems are still solvable eventually if you are patient enough; e.g. by brute force, you can answer the 3-colouring problem in time \(3^{|V(G)|}\text{.}\) In this section, we will be talking about the more hopeless situation of undecidable problems in which there does not exist any algorithm (even a brute force algorithm) that can reliably solve a problem in a finite amount of time. We will be working with the intuitive and non-rigorous definition of undecidable problems that I have just given mainly because I don’t actually know how to formally define it correctly! Note that Problem 9.1.1 is a pretty good candidate for being undecidable, since there does not seem to be a natural brute force algorithm that can answer it in a finite amount of time. Before we get to this, let’s look at the most famous undecidable problems, the Halting Problem.
Problem 9.1.2. The Halting Problem.
- Input: A list of instructions (think of an algorithm, or even a computer program written in any programming language).
- Question: Does it eventually terminate?
An example of a “no” instance of the Halting Problem is an infinite loop. E.g. the following list of instructions never terminates:
- \(\displaystyle i\leftarrow 0;\)
-
while \(i\geq 0\)
- \(\displaystyle i\leftarrow i+1;\)
In case you’re not familiar with this notation, this means that we initialize the variable \(i\) to be zero and then, as long as \(i\geq0\text{,}\) we increase \(i\) by one. Clearly, this will never terminate.
Its not too hard to come up with a “yes” instance of the Halting Problem. Just come up with any algorithm that eventually terminates. An empty algorithm would do the trick. Let us now see why the Halting Problem is undecidable.
Theorem 9.1.3.
The Halting Problem is undecidable.Proof.
Suppose that there exists an algorithm \(A\) which can accept any list of instructions as an input and, in a finite amount of time, can output TRUE or FALSE depending on whether the list of instructions terminates or not. Now, let \(P\) denote the following computer program:
-
if \(A(P)\)
- Loop forever.
-
else
- Terminate.
Note that \(P\) is “self-referential”. That is, the program depends on itself. That’s not against the rules! Anyway, now we ask: Does \(P\) terminate? Well, if it does, then \(A(P)\) is true... which triggers \(P\) to loop forever. But, if it does not terminate, then \(A(P)\) is false which causes it to terminate. Either way, we run into a contradiction. So, the only reasonable thing to conclude is that the algorithm \(A\) cannot exist. This issue of self-reference is analogous to those that appear in other paradoxical constructions that you may be familiar with, such as Russel’s Paradox. Anyway, this completes the proof.
In the year 1900, Hilbert famously proposed 23 problems which motivated a large part of 20th century mathematics. His 10th problem was on devising a general algorithm for determining whether a Diophantine equation with integer coefficients has an integer solution. This was solved by Matiyasevich who showed that no such algorithm exist; in fact, he proved the following.
Theorem 9.1.4. Matiyasevich’s Theorem.
Given an integer \(k\) and a polynomial \(p(x_1,\dots,x_k)\) as an input, the problem of determining whether or not \(p(x_1,\dots,x_k)\geq0\) for all \(x_1,\dots,x_k\in\mathbb{Z}\) is undecidable.
Let us now apply this theorem and some fundamental ideas from graph homomorphism theory to show that Problem 9.1.1 is undecidable. By the way, this was proved by Ioannidis and Ramakrishnan, but I first heard about it here https://arxiv.org/abs/2207.12378.
Theorem 9.1.5.
Problem 9.1.1 is undecidable.
Proof.
First, let us show that the decision problem in Theorem 9.1.4 remains undecidable even if we restrict all of the variables to be non-negative. Suppose, to the contrary, that we have an algorithm which is able to decide this problem when the variables are non-negative. Let \(p\) be an instance of the problem in Theorem 9.1.4. Run our hypothetical algorithm on \(2^k\) different variants of the polynomial \(p\) obtained by replacing a subset of the variables \(x_i\) by \(-x_i\text{.}\) If all of them return NO, then \(p\) is a NO instance of the problem in Theorem 9.1.4 and if one of them returns YES then \(p\) is a YES instance of the problem in Theorem 9.1.4. So, this algorithm can’t exist by Theorem 9.1.4.
Okay, so now suppose, to get a contradiction, that there is an algorithm to solve Problem 9.1.1. Let \(p(x_1,\dots,x_k)\) be a polynomial with integer coefficients. Let us show that the algorithm for solving Problem 9.1.1 can be used to determine whether or not \(p(x_1,\dots,x_k)\geq 0\) for all non-negative integers \(x_1,\dots,x_k\text{.}\) To do this, we let \(H_1,\dots,H_k\) be rigid graphs such that there is no homomorphism from \(H_i\) to \(H_j\) for any \(i\neq j\text{.}\) Consider the function
\begin{equation*}
p\left(\hom(H_1,\cdot),\hom(H_2,\cdot),\dots,\hom(H_k,\cdot)\right).
\end{equation*}
Note that \(\hom(F\sqcup H,\cdot)=\hom(F,\cdot)\hom(H,\cdot)\) for any graphs \(F,H\) and so the above function can be written as a linear combination of functions of the form \(\hom(H,\cdot)\) where \(H\) consists of an appropriate number of disjoint copies of the graphs \(H_1,\dots,H_k\text{.}\) So, we can apply the purported algorithm to \(p\left(\hom(H_1,\cdot),\hom(H_2,\cdot),\cdots,\hom(H_k,\cdot)\right)\text{.}\) If the algorithm determines that there exists a graph \(G\) for which this function is negative, then setting \(x_i=\hom(H_i,G)\) gives us non-negative integers at which \(p\) is negative. On the other hand, if there exists a choice of integers \(x_1,\dots,x_k\) such that \(p(x_1,\dots,x_k)<0\text{,}\) then we take \(G\) to be a disjoint union of \(x_i\) copies of \(H_i\) for each \(1\leq i\leq k\text{.}\) Then, by the fact that the graphs \(H_1,\dots,H_k\) are rigid and form an antichain in the homomorphism order, we have \(\hom(H_i,G)=x_i\) for all \(1\leq i\leq k\text{.}\) So, this gives us that \(p\left(\hom(H_1,G),\hom(H_2,G),\dots,\hom(H_k,G)\right)<0\) and we are done.
In a 2011 paper, Hatami and Norine prove an analogous result for homomorphism densities. In this setting, one needs to do more work because, unlike with homomorphism counting functions, homomorphism densities are not integer-valued.
