32
$\begingroup$

Given $\ell\ge 1$, we say a graph $G$ is $\ell$-good if for each $u,v\in G$ (not necessarily distinct), the number of walks of length $\ell$ from $u$ to $v$ is odd. We say a graph $G$ is good if it is $\ell$-good for some $\ell\ge 1$.

Do good graphs exist? For clarity, I am only talking about simple graphs (which lack loops and multiple edges).

Context: In Stanley’s book on Algebraic combinatorics, Exercise 1.13 is about proving an interesting property held for all good graphs. A friend of mine told me that after solving the exercise, he realized he didn’t know of any example of such graphs. I too am stumped about whether such graphs can exist.

A computer search revealed that none exist with $7$ or fewer vertices. I am unclear about the specifics of the search, they were done by my friend.

$\endgroup$
14
  • 2
    $\begingroup$ For what it's worth, I have checked about 20 million randomly-generated graphs with between 8 and 20 vertices (inclusive) and none of them have been $\ell$-good for any $2 \leq \ell \leq 10$. $\endgroup$ Sep 23, 2022 at 16:34
  • 4
    $\begingroup$ In other words, the question asks for an adjacency matrix such that its $\ell$th power over ${\rm GF}(2)$ is all-1 matrix, doesn't it? $\endgroup$ Sep 23, 2022 at 17:02
  • 4
    $\begingroup$ Considering the eigenvalues of the adjacency matrix over $\mathbb{F}_2$ we get that $n$ is even, all eigenvalues are 0, all degrees are even. There is one Jordan box of order $\ell+1$, other boxes are strictly smaller. $\endgroup$ Sep 23, 2022 at 17:02
  • 3
    $\begingroup$ I've tested all graphs with $\leq 10$ vertices and found no good ones. $\endgroup$ Sep 23, 2022 at 19:43
  • 4
    $\begingroup$ Can't Tim's argument be extended to all graphs whose vertex degrees are even, thus showing that good graphs don't exist? Partition the walks of length $\ell/2$ from $v$ according to their first $\frac{\ell}{2}-1$ steps. Each block of the partition contains an even number of walks, since there are an even number of choices for the last step. Thus there are even number of walks of length $\ell/2$ from $v$. $\endgroup$ Sep 23, 2022 at 22:59

2 Answers 2

37
$\begingroup$

A graph without loops cannot be good.

Assume the contrary, let $G$ have $n$ vertices and be good.

Let $A$ be the adjacency matrix of $G$, let $\lambda_1,\ldots,\lambda_n$ be its eigenvalues over some extension of $\mathbb{F}_2$. We have $\sum_{i=1}^n \lambda_i=\mathrm{tr} A=0$.

That $A$ is good means that $A^\ell$ is an all-1 matrix over $\mathbb{F}_2$. It has rank 1, thus at least $n-1$ eigenvalues of $A^\ell$ are 0. On the other hand, the eigenvalues of $A^\ell$ are $\lambda_1^\ell,\ldots,\lambda_n^\ell$. Therefore, at least $n-1$ $\lambda_i$'s are zero, and, since $\sum \lambda_i =0$, all $\lambda_i$'s are 0. Thus $A$ is nilpotent. Since $A^\ell$ has rank 1, we get $A^{\ell+1}=0$ (indeed, denote $\mathrm{im} A^{\ell}:=X$, then $\dim X=1$. We have $\mathrm{im} A^{\ell+1}\subset \mathrm{im} A^{\ell}=X$, and also $\mathrm{im} A^{\ell+1}=AX$. Since $\dim X=1$, either $\mathrm{im} A^{\ell+1}=\{0\}$, or $AX=\mathrm{im} A^{\ell+1}=X$; in the latter case $A$ is not nilpotent since $A^kX=X\ne \{0\}$ for all $k=0,1,2,\ldots$). So, $A\cdot A^\ell=0$, that means that the sum of entries in every row of $A$ is even, i.e., every vertex in $G$ must have even degree.

Now pick a vertex $v$ and let $W$ be the set of all walks of length $\ell$ from $v$ to $v$. The cardinality of $W$ is odd by hypothesis. The operation $\rho$ of reversing a walk is an involution on $W$, so the number of fixed points of $\rho$ is odd; these fixed points consists of walks of the form "take any walk of length $\ell/2$ starting at $v$ and then retrace your steps back to $v$" (so in particular, $\ell$ must be even). But because every vertex has even degree, in particular there is an even number of choices for the last step of the walk of length $\ell/2$, so the total number of walks of length $\ell/2$ must be even. This is a contradiction.

$\endgroup$
5
  • 1
    $\begingroup$ Answer is community wiki for obvious reasons. Perhaps Fedor Petrov can edit this answer to give some details about the eigenvalue argument, which I don't immediately see how to prove. $\endgroup$ Sep 23, 2022 at 23:04
  • 1
    $\begingroup$ I added some details $\endgroup$ Sep 24, 2022 at 2:33
  • 2
    $\begingroup$ I apologise in advance if one should know this, but why do the eigenvalues exist? I am familiar with the argument that if a matrix is symmetric, then it is diagonalisable, but doesn't this rely on inner products? Vector spaces over finite fields don't admit inner products, so why is this still true? $\endgroup$
    – LionCoder
    Sep 26, 2022 at 15:47
  • 2
    $\begingroup$ The eigenvalues are the roots of the characteristic polynomial, so must exist in some extension $K$ of $\mathbb{F}_2$. Diagonalizability isn't even needed here; we just need to triangularize the matrix, which can be done over $K$. You are correct that a symmetric matrix need not be diagonalizable in characteristic 2 (e.g., the 2x2 matrix of all 1's). $\endgroup$ Sep 26, 2022 at 21:32
  • 4
    $\begingroup$ Yow! So much for that exercise. $\endgroup$ Jan 9, 2023 at 16:37
6
$\begingroup$

Here is a combinatorial argument; surely, it can also be rewritten in an algebraic way using the adjacency matrices.

As usual, $N(v)$ denotes the set of vertices adjacent with $v$. We also denote by $f_n(u,v)$ the number of length $n$ walks from $u$ to $v$. Notice that $$ f_{n+1}(u,v)=\sum_{w\in N(v)} f_n(u,w). \qquad(*) $$

Suppose that $f_\ell(u,v)\equiv 1$ for all $u$ and $v$ (all congruences are modulo $2$). By $(*)$, we have $\deg u\equiv f_{\ell+1}(u,v)\equiv \deg v$. Hence all degrees are of the same parity.

Case 1. Assume that all degrees are odd (so the number of vertices is even). By $(*)$ we then get $f_{\ell+1}(u,v)\equiv 1$. Similarly, $1=f_{\ell+1}(u,v)=f_{\ell+2}(u,v)=\dots=f_{2\ell}(u,v)$.

On the other hand, considering in each length $2\ell$ path the middle vertex $w$, we get $$ f_{2\ell}(u,v)=\sum_w f_\ell(u,w)f_\ell(w,v)\equiv \sum_w1\equiv 0, $$ since the number of vertices is even. A contradiction.

Case 2. Assume that all degrees are even. Then we repeat @TimothyChow's argument from the previous answer. For completeness: We consider an involution on the set of walks from $u$ to $u$ consisting in reverting the path. It provides $f_\ell(v,v)\equiv 0$ if $\ell$ is odd (so this case is ruled out), and $f_\ell(v,v)\equiv \sum_u f_{\ell/2}(v,u)$ otherwise. But all length $\ell/2$ walks from $v$ can be split intpo groups differing only by the last step, and each group comtains an even number pf walks. Hence $f_\ell(v,v)\equiv 0$ in this case as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.