Are there number-theoretic graphs that are far from being isomorphic

Question

I say that two graphs $G_1=(V_1,E_1)$, $G_2 = (V_2,E_2)$ with the same number of vertices, edges, are $\epsilon$-far from being isomorphic, if for any bijection between $V_1$ and $V_2$, the fraction of pairs $(x,y)$ for which $(x,y)\in E_2$ conditioned on $(x,y)\in E_1$ is at most $1-\epsilon$.

I am looking of for an infinite family of $\epsilon$-nonisomorphic graph pairs, for which $\epsilon$ is lower-bounded by a positive constant such that these graph pairs are not distinguishable by first-order criteria, like degree distribution, spectra, etc. I am wandering whether it is reasonable to look for such graph pairs from number-theoretic constructions: For example, it is known that there are Paley graphs (say, $P(p^2)$ for prime $p$) for which there exist Peisert graphs (on $GF(p)\times GF(p)$) that are non-isomorphic to them, but with the same parameters, and even co-spectral. Is it possible to show that they are in fact "highly" non-isomorphic as well?

Answer 1

Combinatorics might be a good place to look. I give below a huge family of pairwise non-isomorphic $57$ point graphs all regular of degree $24.$ I suspect that some of them are fairly far from being isomorphic in your sense but have no idea how easy it would be to find the distance given two specific graphs.

There are $11,084,874,829$ isomorphism classes of STS(19) - a steiner triple system with 19 points (and 57 blocks). Each leads to a unique strongly regular graph with parameters SRG(57,24,11,9) (There might be other SRG(57,24,11,9), I'm not sure. ) One forms such a graph with a vertex for each block and an edge joining blocks with a common point.These graphs certainly have much in common. They all have the same spectrum and are regular. Every edge is in $11$ triangles and any pair of non-adjacent vertices is connected by $9$ paths of length $2$. All these graphs have exactly 19 $K_9$ subgraphs which correspond to the points. There are also ways in which they can be quite different. One of them has an automorphism group of order $432$. The vast majority, $11,084,710,071$, have no automorphisms at all. Three of them have $84$ Pasch configurations (the maximum number) and $2,591$ of them have none at all.

As I said, I do not actually know how far a pair of these can be from being isomorphic (in your sense), nor how one would prove that the distance is large. But the Pasch configuration information leads me to speculate that some might be far apart.

A Pasch configuration in a STS is a set of four blocks and six points of the form $uvw,wxy,uxz,vyz$ These are exactly the cases of four pairwise intersecting blocks with no point in common to any three. In the graphs this corresponds to a $K_4$ which overlaps no $K_9$ in a $K_3.$

Whatever is true here is no doubt reflected more extremely in the case of STS(v) for $v \gt 19$ points. I just don't know if these have been exhaustively enumerated for $v \gt 19.$

There are also great numbers of strongly regular graphs which have equal parameters but are pairwise non-isomorphic arising from sets of $j$ pairwise orthogonal $k \times k$ latin squares.

LATER I do like the example above and it seems in the spirit that you want. But here is another case where it might be easier to prove distance. In a precise sense, most trees are not determined by their spectrum. There are many constructions. Here is a small pair which share the spectrum and degree sequence.

It is not so hard to see that they are not fully isomorphic and there is a vertex bijection which preserves 3/4 of the edges (So they are $1/4$ far from being isokmorphic?) The condition

there is a vertex of degree $2$ whose neighbors have degrees $3$ and $4$ .

does distinguish them.

I imagine that there are more intricate trees which are harder to immediately tell apart and which are almost $1/2$ far from being isomorphic. Perhaps even $1-\varepsilon$.