Expanders except for commutativity?

Question

What would you call a graph that is an expander except for commutativity, in the following sense?

Say that, from every vertex, you have $d$ edges ($d$ large) labelled $x_1,\dotsc, x_d$. Say that your graph is of "large girth except for commutativity" meaning that, for all $k$ less than a certain $k_0\gg \frac{\log |V|}{\log d}$, any two paths of length between $1$ and $k$ from the same vertex end in different vertices, unless the labels of the edges in the two paths are permutations of each other (say that the edges in one path are labelled $x_{i_1},\dotsc,x_{i_k}$ and the edges in the other path are labelled $x_{j_1},\dotsc,x_{j_k}$, and that those two tuples of labels are permutations of each other).

If $\frac{\log |V|}{\log d}$ is $o(d)$, then I don't see why this graph couldn't be an expander according to the usual definition. If, however, $\frac{\log |V|}{\log d}$ is larger than a large constant times $d$, then growth stops being exponential after $d$ steps, and I cannot see how the graph could be an expander in the traditional sense. However, it should still be possible for a random walk to equidistribute *as much as it can given commutativity' (in the sense above) and if that property is strong enough, we should be able to speak of "expansion except for commutativity".

I imagine this sort of situation has been studied before? Does it ring a bell?

Answer 1

With the commutativity assumption your graph admits an action of $\mathbb Z^d$ where the $i$'th generator of $\mathbb Z^d$ sends a vertex to the vertex it's connected to under the edge $x_i$. (I assume the edges are directed since otherwise the condition is impossible to fulfill).

We can assume this action is transitive, so the vertices are $\mathbb Z^d / H$ for some subgroup $H$ of $\mathbb Z^d$, and the condition is roughly that $H$ does not contain any vector in $\mathbb Z^d$ of $L^1$ norm at most $k$. (Technically, it's the condition that $H$ does not contain any vector whose sum of positiv entries is at most $k$ and whose sum of negative entries is at least $-k$, which is implied by $H$ not containing any vector of norm at most $2k$ and implies $H$ not containing any vector of norm at most $k$.)

The kernel of a random homomorphism $\mathbb Z^d \to \mathbb F_p$ has this property if $p$ is larger than the number of vectors which can't be sent to $0$, which means $k_0$ is of size something like $|V|^{1/2d}$ which for $d$ small is much larger that $\log |V|/\log d$.