Tom and Jerry

Tom (the cat) and Jerry (the mouse) are playing on a simple graph $G$.

Every vertex of $G$ is a mousehole, and every edge of $G$ is a tunnel connecting two mouseholes.

Originally, Jerry is hiding in one of the mouseholes.
Every morning, Tom can check one (and only one) of the mouseholes. If Jerry happens to be hiding there then Tom catches Jerry and the game is over.
Every evening, if the game continues, Jerry moves to a mousehole which is adjacent (i.e. connected by a tunnel, if there is one available) to his current hiding place. The next morning Tom checks again and the game continues like this.

Let us call a graph $G$ a Tom graph, if our super-smart Tom, who knows the configuration of the graph but does not know the location of Jerry, can guarantee to catch Jerry in finitely many days.
For example consider all graphs on 3 nodes:

For graphs 1 and 2, Tom will catch Jerry in at most three days. For graph 3 Tom can check the middle connection on two consecutive days and hence guarantee to catch Jerry in at most two days. These three graphs are therefore Tom Graphs. However, graph 4 is not a Tom Graph because the game could potentially continue forever.

Let $T(n)$ be the number of different Tom graphs with $n$ vertices. Two graphs are considered the same if there is a bijection $f$ between their vertices, such that $(v,w)$ is an edge if and only if $(f(v),f(w))$ is an edge.

We have $T(3) = 3$, $T(7) = 37$, $T(10) = 328$ and $T(20) = 1416269$.

Find $T(2019)$ giving your answer modulo $1\,000\,000\,007$.

This problem can’t be solved directly via calculation due to its enormous size. It involves a fair amount of combinatorics and graph theory. Instead, we should find a recurrence relation for $T(n)$.

First let’s define $U(n)$ to be the number of undirected graphs on $n$ vertices without constraints. It is well-known that $U(n) = 2^{\binom{n}{2}}$ because each pair of vertices may either have an edge or not.

Next we need to determine how many graphs are not Tom graphs: those where Jerry can evade Tom infinitely. These are graphs with cycles. To get the number of these, we must count all the graphs, then subtract the cycle-free ones.

The cycle-free graphs are trees and “forests,” multiple disconnected trees. It is known from Cayley’s formula that there are $n^{n-2}$ trees on $n$ vertices.

For forests, we could disconnect the $n$-vertex tree into several trees. To count these possibilities, we can use a generating function. We can write the generating function for the number of forests on $n$ vertices as
$$F(x) = \exp\left({\sum_{n=1}^{\infty}\frac{x^nT(n)}{n}}\right)$$
where $T(n)$ is number of trees on $n$ vertices. From this, we can derive that the number of forests on $n$ vertices is the coefficient of $x^n$ in the power series expansion of $F(x)$.

Once we have the number of cycle-free graphs, we can figure out how many graphs are not Tom graphs: those with cycles. Then we just subtract this from the total number of graphs to get $T(n)$.

However, calculating all these directly for $n=2019$ would be impossible due to the size of numbers. You need to reduce everything modulo $1\,000\,000\,007$ at every step of your calculations. In addition, you will take advantage of efficient computational techniques such as fast power algorithm when calculating large powers, polynomial multiplication and division when calculating coefficients of the generating function.

Finally, this computational task would most likely require a computer programming language with support for large numbers and efficient algorithms as available in languages like Python or C++. Thus solving this problem directly using pen and paper would be practically impossible.

More Answers: