# doubly-stochastic isomorphisms of graphs

A doubly stochastic matrix that commutes with the adjacency matrix of a graph is a doubly-stochastic automorphism of that graph (definition by Tinhofer 1986). Each (classical) automorphism of a graph is clearly a doubly-stochastic automorphism.

A graph all of whose doubly-stochastic automorphisms are convex combinations of (classical) automorphisms is called compact. (E.g., trees and cycles are known to be compact, complement of compact graphs are compact as long as they are connected, while Petersen's graph to be non-compact)

If a graph is not compact, how do the further extremal points of the polytope of its doubly-stochastic automorphisms look like? Are there any known examples?

• Do you have a reference for the assertion that the Petersen graph is not compact? – Anton Malyshev May 11 '14 at 6:47
• yes, the article "Compact cellular algebras and permutation groups" by Evdokimov-Karpinski-Ponomarenko (Discr. Math. 197/198, 1999) – Delio Mugnolo May 11 '14 at 9:45
• And by the way: In their survey "Symmetry and eigenvectors" Chan and Godsil claim that the n-cube is compact iff $n\ge 4$ (remark before Theorem 11.4). Is this not in contradiction with the fact that the 2-cube is the cycle of length 4? – Delio Mugnolo May 14 '14 at 14:50
• Is Petersen the smallest example? I guess it is small enough to attempt a computer enumeration of vertices of such a polytope. Has anyone tried this? – Dima Pasechnik May 20 '14 at 6:34
• I have tried all graphs on 4 nodes and all of them are compact :) – Delio Mugnolo May 20 '14 at 9:54

A way to compute some extremal points for the Petersen example might be as follows: take the complement $A$ of its adjacency matrix and form the linear function $\ell(X)$ given by $X\mapsto \langle A,X\rangle$ on the space of 10x10 matrices. Maximising $\ell$ on the polytope in question using a simplex method will give you a vertex $Y$, such that $\ell(Y)\geq\ell(\frac{1}{6}A)=5$; you will get the equality in the latter, i.e. $\frac{1}{6}A$ is extremal (see the next paragraph for a proof). Note that Evdokimov et al. showed that $\frac{1}{6}A$ is a point in the polytope which is not a convex combination of classical automorphisms, although they did not seem to care about extremality.
As well, there is the following more theoretical way to produce extreme points, although not vertices in general: observe that the polytope is invariant under the automorphism group $G\cong S_5$ of the graph, and preserves the function $\ell$. Thus the image $g(Y)$ of $Y$ under any automorphism $g\in G$ satisfies $\ell(Y)=\ell(g(Y))$, and $Z:=\frac{1}{|G|}\sum_{g\in G} g(Y)$ is also in the polytope and satisfies $\ell(Z)=\ell(Y)$, i.e. is extremal. On the other hand, $Z=\alpha I +\beta A +\gamma (ee^\top -I-A)$, for some nonnegative $\alpha$, $\beta$, $\gamma$, such that $Z$ is doubly stochastic, i.e. $\alpha+\frac{1}{6}\beta+\frac{1}{3}\gamma=1$. Therefore the set of such matrices $Z$ is the intersection of our polytope with certain 2-dimensional affine subspace. On this 2-dimensional polytope the linear function $\ell$ reaches the maximum at $Z=\frac{1}{6}A$. Therefore $\frac{1}{6}A$ is extremal in the whole polytope.
Finally, note that the latter argument generalises to the other graphs (Johnson graphs $J(n,k)$) in loc.cit, Thm 5.3.
EDIT: note that the Petersen graph (with the adjacency matrix $B:=ee^\top -I-A$) is not compact itself, as its complement (with the adjacency matrix $A$) is not compact. To see this, note that $XA=AX$ if and only if $XB=BX$, i.e. it does not matter which matrix equation we use to define our polytope. (loc.cit. merely says that $A$ generates the corresponding matrix algebra, and the meaning of this remark might be lost on a casual reader).
• sorry, perhaps i am missing something, but since the petersen graph is cubic, how can $\frac{1}{6}A$ be doubly stochastic? shouldn't it be renormalized to $\frac{1}{3}A$? – Delio Mugnolo May 20 '14 at 11:44
• I denote by $A$ the complement of Petersen's adjacency matrix – Dima Pasechnik May 20 '14 at 11:52
• Actually, the same argument can be carried out for $A$ being the adjacency matrix of Petersen, with the obvious changes. – Dima Pasechnik May 20 '14 at 11:53