# Robustly Self-Ordered Graphs:
Constructions and Applications to Property Testing

Oded Goldreich  Avi Wigderson

(August 22, 2021)

A graph $G$ is called self-ordered (a.k.a asymmetric) if the identity
permutation is its only automorphism. Equivalently, there is a unique
isomorphism from $G$ to any graph that is isomorphic to $G$. We say that
$G=(V,E)$ is robustly self-ordered if the size of the symmetric difference
between $E$ and the edge-set of the graph obtained by permuting $V$ using any
permutation $\pi:V\to V$ is proportional to the number of non-fixed-points of
$\pi$. In this work, we initiate the study of the structure, construction and
utility of robustly self-ordered graphs.

We show that robustly self-ordered bounded-degree graphs exist (in abundance),
and that they can be constructed efficiently, in a strong sense. Specifically,
given the index of a vertex in such a graph, it is possible to find all its
neighbors in polynomial-time (i.e., in time that is poly-logarithmic in the
size of the graph).

We provide two very different constructions, in tools and structure. The
first, a direct construction, is based on proving a sufficient condition for
robust self-ordering, which requires that an auxiliary graph is expanding. The
second construction is iterative, boosting the property of robust self-
ordering from smaller to larger graphs. Structuraly, the first construction
always yields expanding graphs, while the second construction may produce
graphs that have many tiny (sub-logarithmic) connected components.

We also consider graphs of unbounded degree, seeking correspondingly unbounded
robustness parameters. We again demonstrate that such graphs (of linear
degree) exist (in abundance), and that they can be constructed efficiently, in
a strong sense. This turns out to require very different tools. Specifically,
we show that the construction of such graphs reduces to the construction of
non-malleable two-source extractors (with very weak parameters but with some
additional natural features).

We demonstrate that robustly self-ordered bounded-degree graphs are useful
towards obtaining lower bounds on the query complexity of testing graph
properties both in the bounded-degree and the dense graph models. Indeed,
their robustness offers efficient, local and distance preserving reductions
from testing problems on ordered structures (like sequences) to the unordered
(effectively unlabeled) graphs. One of the results that we obtain, via such a
reduction, is a subexponential separation between the query complexities of
testing and tolerant testing of graph properties in the bounded-degree graph
model.

00footnotetext: The authors’ affiliation and grant acknowledgements apear in
the Acknowledgements section.

###### Contents

  1. 1 Introduction
    1. 1.1 Robustly self-ordered bounded-degree graphs
      1. 1.1.1 Our main results and motivation
      2. 1.1.2 Techniques
    2. 1.2 Robustly self-ordered dense graphs
      1. 1.2.1 Our main results
      2. 1.2.2 Techniques
    3. 1.3 Perspective
    4. 1.4 Roadmaps
  2. I The Case of Bounded-Degree Graphs
    1. 2 The Edge-Colored Variant
      1. 2.1 Transformation to standard (uncolored) version
      2. 2.2 Application: Making the graph regular and expanding
      3. 2.3 Local computability of the transformations
    2. 3 The Direct Construction
      1. 3.1 A sufficient condition for robust self-ordering of directed colored graphs
      2. 3.2 From the directed variant to the undirected one
    3. 4 The Three-Step Construction
      1. 4.1 Existence
      2. 4.2 Constructions
      3. 4.3 Strong (i.e., local) constructions
      4. 4.4 Local self-ordering
    4. 5 Application to Testing Bounded-Degree Graph Properties
    5. 6 Random Regular Graphs are Robustly Self-Ordered
  3. II The Case of Dense Graphs
    1. 7 Existence and Transformation to Bounded-Degree Graphs
    2. 8 Relation to Non-Malleable Two-Source Extractors
      1. 8.1 The first construction
      2. 8.2 The second construction
      3. 8.3 Obtaining efficient self-ordering
    3. 9 Application to Testing Dense Graph Properties
    4. 10 The Case of Intermediate Degree Bounds
    5. Acknowledgements
    6. Appendix: On Definitions of Non-Malleable Two-Source Extractor

###  1 Introduction

For a (labeled) graph $G=(V,E)$, and a bijection $\phi:V\to V^{\prime}$, we
denote by $\phi(G)$ the graph $G^{\prime}=(V^{\prime},E^{\prime})$ such that
$E^{\prime}=\\{\\{\phi(u),\phi(v)\\}:\\{u,v\\}\\!\in\\!E\\}$, and say that
$G^{\prime}$ is isomorphic to $G$. The set of automorphisms of the graph
$G=(V,E)$, denoted ${\tt aut}(G)$, is the set of permutations that preserve
the graph $G$; that is, $\pi\in{\tt aut}(G)$ if and only if $\pi(G)=G$. We say
that a graph is asymmetric (equiv., self-ordered) if its set of automorphisms
is a singleton, which consists of the trivial automorphism (i.e., the identity
permutation). We actually prefer the term self-ordered, because we take the
perspective that is offered by the following equivalent definition.

###### Definition 1.1

(self-ordered (a.k.a asymmetric) graphs): The graph $G=([n],E)$ is self-
ordered if for every graph $G^{\prime}=(V^{\prime},E^{\prime})$ that is
isomorphic to $G$ there exists a unique bijection $\phi:V^{\prime}\to[n]$ such
that $\phi(G^{\prime})=G$.

In other words, given an isomorphic copy $G^{\prime}=(V^{\prime},E^{\prime})$
of a fixed graph $G=([n],E)$, there is a unique bijection
$\phi:V^{\prime}\to[n]$ that orders the vertices of $G^{\prime}$ such that the
resulting graph (i.e., $\phi(G^{\prime})$) is identical to $G$. Indeed, if
$G^{\prime}=G$, then this unique bijection is the identity
permutation.111Naturally, we are interested in efficient algorithms that find
this unique ordering, whenever it exists; such algorithms are known when the
degree of the graph is bounded [29].

In this work, we consider a feature, which we call robust self-ordering, that
is a quantitative version self-ordering. Loosely speaking, a graph $G=([n],E)$
is robustly self-ordered if, for every permutation $\pi:[n]\to[n]$, the size
of the symmetric difference between $G$ and $\pi(G)$ is proportional to the
number of non-fixed-points under $\pi$; that is,
$|E\triangle\\{\\{\pi(u),\pi(v)\\}\\!:\\!\\{u,v\\}\\!\in\\!E\\}|$ is
proportional to $|\\{i\\!\in\\![n]\\!:\\!\pi(i)\\!\neq\\!i\\}|$. (In contrast,
self-ordering only means that the size of the symmetric difference is positive
if the number of non-fixed-points is positive.)

###### Definition 1.2

(robustly self-ordered graphs): A graph $G=(V,E)$ is said to be
$\gamma$-robustly self-ordered if for every permutation $\pi:V\to{V}$ it holds
that

$\big{|}E\triangle\left\\{\\{\pi(u),\pi(v)\\}\\!:\\!\\{u,v\\}\\!\in\\!E\right\\}\big{|}\;\geq\;\gamma\cdot|\\{i\in[n]\\!:\\!\pi(i)\neq
i\\}|,$ (1)

where $\triangle$ denotes the symmetric differece operation. An infinite
family of graphs $\\{G_{n}=([n],E_{n})\\}_{n\in\mathbb{N}}$ (such that each
$G_{n}$ has maximum degree $d$) is called robustly self-ordered if there
exists a constant $\gamma>0$, called the robustness parameter, such that for
every $n$ the graph $G_{n}$ is $\gamma$-robustly self-ordered.

Note that
$|E_{n}\triangle\\{\\{\pi(u),\pi(v)\\}\\!:\\!\\{u,v\\}\\!\in\\!E_{n}\\}|\leq
2d\cdot|\\{i\in[n]\\!:\\!\pi(i)\neq i\\}|$ always holds (for families of
maximum degree $d$). The term “robust” is inspired by the property testing
literature (cf. [31]), where it indicates that some “parametrized violation”
is reflected proportionally in some “detection parameter”.

The second part of Definition 1.2 is tailored for bounded-degree graphs, which
will be our focus in Section 2–6. Nevertheless, in Sections 7–10 we consider
graphs of unbounded degree and unbounded robustness parameters. In this case,
for a function $\rho:\mathbb{N}\to\mathbb{R}$, we say that an infinite family
of graphs $\\{G_{n}=([n],E_{n})\\}_{n\in\mathbb{N}}$ is $\rho$-robustly self-
ordered if for every $n$ the graph $G_{n}$ is $\rho(n)$-robustly self-ordered.
Naturally, in this case, the graphs must have $\Omega(\rho(n)\cdot n)$
edges.222Actually, all but at most one vertex must have degree at least
$\rho(n)/2$. In Sections 7–9 we consider the case of $\rho(n)=\Omega(n)$.

####  1.1 Robustly self-ordered bounded-degree graphs

The first part of this paper (i.e., Section 2–6) focuses on the study of
robustly self-ordered bounded-degree graphs.

#####  1.1.1 Our main results and motivation

We show that robustly self-ordered ($n$-vertex) graphs of bounded-degree not
only exist (for all $n\in\mathbb{N}$), but can be efficiently constructed in a
strong (or local) sense. Specifically, we prove the following result.

###### Theorem 1.3

(constructing robustly self-ordered bounded-degree graphs): For all
sufficiently large $d\in\mathbb{N}$, there exist an infinite family of
$d$-regular robustly self-ordered graphs $\\{G_{n}\\}_{n\in\mathbb{N}}$ and a
polynomial-time algorithm that, given $n\in\mathbb{N}$ and a vertex $v\in[n]$
in the $n$-vertex graph $G_{n}$, finds all neighbors of $v$ (in $G_{n}$).

We stress that the algorithm runs in time that is polynomial in the
description of the vertex; that is, the algorithm runs in time that is
polylogarithmic in the size of the graph. Theorem 1.3 holds both for graphs
that consists of connected components of logarithmic size and for “strongly
connected” graphs (i.e., expanders).

Recall that given an isomorphic copy $G^{\prime}$ of such a graph $G_{n}$, the
original graph $G_{n}$ (i.e., along with its unique ordering) can be found in
polynomial-time [29]. Furthermore, we show that the pre-image of each vertex
of $G^{\prime}$ in the graph $G_{n}$ (i.e., its index in the aforementioned
ordering) can be found in time that is polylogarithmic in the size of the
graph (see discussion in Section 4.4, culminating in Theorem 4.7).333The
algorithm asserted above is said to perform local self-ordering of
$G^{\prime}$ according to $G_{n}$. For $\phi(G^{\prime})=G_{n}$, given a
vertex $v$ in $G^{\prime}$, this algorithm returns $\phi(v)$ in ${\rm
poly}(\log n)$-time. In contrast, a local reversed self-ordering algorithm is
given a vertex $i\in[n]$ of $G_{n}$ and returns $\phi^{-1}(i)$. The second
algorithm is also presented in Section 4.4 (see Theorem 4.9).

We present two proofs of Theorem 1.3. Loosely speaking, the first proof
reduces to proving that a $2d$-regular $n$-vertex graph representing the
action of $d$ permutations on $[n]$ is robustly self-ordered if the
$n(n-1)$-vertex graph representing the action of these permutations on vertex-
pairs is an expander. The graphs constructed in this proof are expanders,
whereas the graphs constructed via by the second proof can be either expanders
or consist of connected components of logarithmic size. More importantly, the
graphs constructed in the second proof are couple with local self-ordering and
local reversed self-ordering algorithms (see Section 4.4). The second proof
proceeds in three steps, starting from the mere existence of robustly self-
ordered bounded-degree $\ell$-vertex graphs, which yields a construction that
runs in ${\rm poly}(\ell^{\ell})$-time. Next, a ${\rm poly}(n)$-time
construction of $n$-vertex graphs is obtained by using the former graphs as
small subgraphs (of $o(\log n)$-size). Lastly, strong (a.k.a local)
constructability is obtained in an analogous manner. For more details, see
Section 1.1.2.

We demonstrate that robustly self-ordered bounded-degree graphs are useful
towards obtaining lower bounds on the query complexity of testing graph
properties in the bounded-degree graph model. Specifically, we use these
graphs as a key ingredient in a general methodology of transporting lower
bounds regarding testing binary strings to lower bounds regarding testing
graph properties in the bounded-degree graph model. In particular, using the
methodology, we prove the following two results.

  1. 1.

A subexponential separation between the complexities of testing and tolerant
testing of graph properties in the bounded-degree graph model; that is, for
some constant $c>0$, the query complexity of tolerant testing is at least
$\exp(q^{c})$, where $q$ is the query complexity of standard testing.

This result, which appears as Theorem 5.5, is obtained by transporting an
analogous result that was known for testing binary strings [15].

  2. 2.

A linear query complexity lower bound for testing an efficiently recognizable
graph property in the bounded-degree graph model, where the lower bound holds
even if the tested graph is restricted to consist of connected components of
logarithmic size (see Theorem 5.2).

As discussed in Section 5, an analogous result was known in the general case
(i.e., without the restriction on the size of the connected components), and
we consider it interesting that the result holds also in the special case of
graphs with small connected components.

To get a feeling of why robustly self-ordered graphs are relevant to such
transportation, recall that strings are ordered objects, whereas graphs
properties are effectively sets of unlabeled graphs, which are unordered
objects. Hence, we need to make the graphs (in the property) ordered, and
furthermore make this ordering robust in the very sense that is reflected in
Definition 1.2. Furthermore, local self-ordering algorithms are used for
transporting lower bounds (and local reversed self-ordering algorithms are
used for transporting upper bounds). We comment that the theme of reducing
ordered structures to unordered structures occur often in the theory of
computation and in logic, and is often coupled with analogous of query
complexity.

Lastly, in Section 6, we prove that random $2d$-regular graphs are robustly
self-ordered; see Theorem 6.1. This extends work in probabilistic graph
theory, which proves a similar result for the weaker notion of self-ordering
[4, 5].

#####  1.1.2 Techniques

As stated above, we present two different constructions that establish Theorem
1.3: A direct construction and a three-step construction. Both constructions
utilize a variant of the notion of robust self-ordering that refers to edge-
colored graphs, which we review first.

###### The edge-coloring methodology.

At several different points, we found it useful to start by demonstrating the
robust self-ordering feature in a relaxed model in which edges are assigned a
constant number of colors, and the symmetric difference between graphs
accounts also for edges that have different colors in the two graphs (see
Definition 2.1). This allows us to analyze different sets of edges separately.

For example, we actually analyze the direct construction in the edge-colored
model, since this allows for identifying each of the underlying permutations
with a different color. Another example, which arises in the three-step
construction, occurs when we super-impose a robustly self-ordered graph with
an expander graph in order to make the robustly self-ordered graph expanding
(as needed for the second and third step of the aforementioned three-step
construction). In this case, assigning the edges of each of the two graphs a
different color, allows for easily retaining the robust self-ordering feature
(of the first graph).

We obtain robustly self-ordered graphs (in the original sense) by replacing
all edges that are assigned a specific color with copies of a constant-sized
(asymmetric) gadget, where different (and in fact non-isomorphic) gadgets are
used for different edge colors. The soundness of this transformation is proved
in Theorem 2.4.

###### The direct construction.

For any $d$ permutations, $\pi_{1},...,\pi_{d}:[n]\to[n]$, we consider the
Schreier graph (see [25, Sec. 11.1.2]) defined by the action of these
permutation on $[n]$; that is, the edge-set of this graph is
$\\{\\{v,\pi_{i}(v)\\}\\!:\\!v\\!\in\\![n]\,\&\,i\\!\in\\![d]\\}$. Loosely
speaking, we prove that this $2d$-regular $n$-vertex graph is robustly self-
ordered if another Schreier graph is an expander. The second Schreier graph
represents the action of the same permutations on pairs of vertices (in
$[n]$); that is, this graph consisting of the vertex-set
$\\{(u,v)\\!:\\!u,v\\!\in\\![n]\\}$ and the edge-set
$\\{\\{(u,v),(\pi_{i}(u),\pi_{i}(v))\\}\\!:\\!u,v\\!\in\\![n]\,\&\,i\\!\in\\![d]\\}$.444Equivalently,
we consider only pairs of distinct vertices; that is, the vertex-set
$\\{(u,v)\\!:\\!u,v\\!\in\\![n]\,\&\,u\\!\neq\\!v\\}$.

The argument is actually made with respect to edge-colored directed graphs
(i.e., the edge-set of the first graph is
$\\{(v,\pi_{i}(v))\\!:\\!v\\!\in\\![n]\,\&\,i\\!\in\\![d]\\}$ and the directed
edge $(v,\pi_{i}(v))$ is assigned the color $i$). Hence, we also present a
transformation of robustly self-ordered edge-colored directed graphs to
analogous undirected graphs. Specifically, we replace the directed edge
$(u,v)$ colored $j$ by a 2-path with a designated auxiliary vertex
$a_{u,v,j}$, while coloring the edge $\\{u,a_{u,v,j}\\}$ by $2j-1$ and the
edge $\\{a_{u,v,j},v\\}$ by $2j$.

We comment that permutations satisfying the foregoing condition can be
efficiently constructed; for example, any set of expanding generators for
${\rm SL}_{2}(p)$ (e.g., the one used by [28]) yield such permutations on
$[n]\equiv\\{(1,i):i\in{\rm GF}(p)\\}\cup\\{(0,1)\\}$ (see Proposition
3.3).555In this case, the primary Schreier graph represents the natural action
of the group on the 1-dimensional subspaces of ${\rm GF}(p)^{2}$.

###### The three-step construction.

Our alternative construction of robustly self-ordered (bounded-degree)
$n$-vertex graphs proceeds in three steps.

  1. 1.

First, we prove the existence of bounded-degree $n$-vertex graphs that are
robustly self-ordered (see Theorem 4.1), while observing that this yields a
$\exp(O(n\log n))$-time algorithm for constructing them.

  2. 2.

Next (see Theorem 4.2), we use the latter algorithm to construct robustly
self-ordered $n$-vertex bounded-degree graphs that consist of $2\ell$-sized
connected components, where $\ell=\frac{O(\log n)}{\log\log n}$; these
connected components are far from being isomorphic to one another, and are
constructed using robustly self-ordered $\ell$-vertex graphs as a building
block. This yields an algorithm that constructs the $n$-vertex graph in ${\rm
poly}(n)$-time, since $\exp(O(\ell\log\ell))={\rm poly}(n)$.

  3. 3.

Lastly, we derive Theorem 1.3 (restated as Theorem 4.5) by repeating the same
strategy as in Step 2, but using the construction of Theorem 4.2 for the
construction of the small connected components (and setting $\ell=O(\log n)$).
This yields an algorithm that finds the neighbors of a vertex in the
$n$-vertex graph in ${\rm poly}(\log n)$-time, since ${\rm poly}(\ell)={\rm
poly}(\log n)$.

The foregoing description of Steps 2 and 3 yields graphs that consists of
small connected components. We obtain analogous results for “strongly
connected” graphs (i.e., expanders) by superimposing these graphs with
expander graphs (while distinguishing the two types of edges by using colors
(see the foregoing discussion)). In fact, it is essential to perform this
transformation (on the result of Step 2) before taking Step 3; the
transformation itself appears in the proof of Theorem 2.6.

###### Using large collections of pairwise far apart permutations.

One ingredient in the foregoing three-step construction is the use of a single
$\ell$-vertex robustly self-ordered (bounded-degree) graph towards obtaining a
large collection of $2\ell$-vertex (bounded-degree) graphs such that every two
graphs are far from being isomorphic to one another, where “large” means
$\exp(\Omega(\ell\log\ell))$ in one case (i.e., in the proof of Theorem 4.2)
and $\exp(\Omega(\ell))$ in another case (i.e., in the proof of Theorem 4.5).
Essentially, this is done by constructing a large collection of permutations
of $[\ell]$ that are pairwise far-apart, and letting the $i^{\rm th}$ graph
consists of two copies of the $\ell$-vertex graph that are matched according
to the $i^{\rm th}$ permutation (see the aforementioned proofs). (Actually, we
use two robustly self-ordered $\ell$-vertex graphs that are far from being
isomorphic (e.g., have different degree).)

A collection of $L=\exp(\Omega(\ell\log\ell))$ pairwise far-apart permutations
over $[\ell]$ can be constructed in ${\rm poly}(L)$-time by selecting the
permutations one by one, while relying on the existence of a permutation that
augments the current sequence (while preserving the distance condition, see
the proof of Theorem 4.2). A collection of $L=\exp(\Omega(\ell))$ pairwise
far-apart permutations over $[\ell]$ can be locally constructed such that the
$i^{\rm th}$ permutation is constructed in ${\rm poly}(\ell)$-time by using
sequences of disjoint transpositions determined via a good error correcting
code (see the proof of Theorem 4.5).

The foregoing discussion begs the challenge of obtaining a construction of a
collection of $L=\exp(\Omega(\ell\log\ell))$ permutations over $[\ell]$ that
are pairwise far-apart along with a polynomial-time algorithm that, on input
$i\in[L]$, returns a description of the $i^{\rm th}$ permutation (i.e., the
algorithm should run in ${\rm poly}(\log L)$-time). We meet this challenge in
[22]. Note that such a collection constitutes a an asymptotically good code
over the alphabet $[\ell]$, where the permutations are the codewords (being
far-apart corresponds to constant relative distance and $\log
L=\Omega(\log(\ell!))$ corresponds to constant rate).

###### On the failure of some natural approaches.

We mention that natural candidates for robustly self-ordered bounded-degree
graphs fail. In particular, there exist expander graphs that are not robustly
self-ordered. In fact, any Cayley graph is symmetric (i.e., has non-trivial
automorphisms).666Specifically, multiplying the vertex labels (say, on the
right) by any non-zero group element yields a non-trivial automorphism
(assuming that edges are defined by multiplying with a generator on the left).
Such automorphisms cannot be constructed in general for Schreier graphs, and
some Schreier graphs have no automorphisms (e.g., the ones we construct here).

In light of the above, it is interesting that expansion can serve as a
sufficient condition for robust self-ordering (as explained in the foregoing
review of the direct construction); recall, however, that this works for
Schreier graphs, and expansion needs to hold for the action on vertex-pairs.

###### On optimization:

We made no attempt to minimize the degree bound and maximize the robustness
parameter. Note that we can obtain 3-regular robustly self-ordered graphs by
applying degree reduction; that is, given a $d$-regular graph, we replace each
vertex by a $d$-cycle and use each of these vertices to “hook” one original
edge. To facilitate the analysis, we may use one color for the edges of the
$d$-cycles and another color for the other (i.e., original) edges.777Needless
to say, we later replace all colored edges by copies of adequate constant-
sized gadgets. Hence, the issue at hand is actually one of maximizing the
robustness parameter of the resulting 3-regular graphs.

###### Caveat (tedious):

Whenever we assert a $d$-regular $n$-vertex graph, we assume that the trivial
conditions hold; specifically, we assume that $n>d$ and that $nd$ is even (or,
alternatively, allow for one exceptional vertex of degree $d-1$).

####  1.2 Robustly self-ordered dense graphs

In the second part of this paper (i.e., Sections 7–10) we consider graphs of
unbounded degree, seeking correspondingly unbounded robustness parameters. In
particular, we are interested in $n$-vertex graphs that are
$\Omega(n)$-robustly self-ordered, which means that they must have
$\Omega(n^{2})$ edges.

The construction of $\Omega(n)$-robustly self-ordered graphs offers yet
another alternative approach towards the construction of bounded-degree graphs
that are $\Omega(1)$-robustly self-ordered. Specifically, we show that
$n$-vertex graphs that are $\Omega(n)$-robustly self-ordered can be
efficiently transformed into $O(n^{2})$-vertex bounded-degree graphs that are
$\Omega(1)$-robustly self-ordered; see Proposition 7.2, which is essentially
proved by the “degree reduction via expanders” technique, while using a
different color for the expanders’ edges, and then using gadgets to replace
colored edges (see Theorem 2.4).

#####  1.2.1 Our main results

It is quite easy to show that random $n$-vertex graphs are
$\Omega(n)$-robustly self-ordered (see Proposition 7.1); in fact, the proof is
easier than the proof of the analogous result for bounded-degree graphs
(Theorem 6.1). Unfortunately, constructing $n$-vertex graphs that are
$\Omega(n)$-robustly self-ordered seems to be no easier constructing robustly
self-ordered bounded-degree graphs. In particular, it seems to require
completely different techniques and tools.

###### Theorem 1.4

(constructing $\Omega(n)$-robustly self-ordered graphs): There exist an
infinite family of dense $\Omega(n)$-robustly self-ordered graphs
$\\{G_{n}\\}_{n\in\mathbb{N}}$ and a polynomial-time algorithm that, given
$n\in\mathbb{N}$ and a pair of vertices $u,v\in[n]$ in the $n$-vertex graph
$G_{n}$, determines whether or not $u$ is adjacent to $v$ in $G_{n}$.

Unlike in the case of bounded-degree graphs, in general, we cannot rely on an
efficient isomorphism test for finding the original ordering of $G_{n}$, when
given an isomorphic copy of it. However, we can obtain dense
$\Omega(n)$-robustly self-ordered graphs for which this ordering can be found
efficiently (see Theorem 8.10).

Our proof of Theorem 1.4 is by a reduction to the construction of non-
malleable two-source extractors, where a suitable construction of the latter
was provided by Chattopadhyay, Goyal, and Li [7]. We actually present two
different reductions (Theorems 8.3 and 8.7), one simpler than the other but
yielding a less efficient construction when combined with the known
constructions of extractors. We mention that the first reduction (Theorem 8.3)
is partially reversible (see Proposition 8.5, which reverses a special case
captured in Remark 8.4).

We show that $\Omega(n)$-robustly self-ordered $n$-vertex graphs can be used
to transport lower bounds regarding testing binary strings to lower bounds
regarding testing graph properties in the dense graph model. This general
methodology, presented in Section 9, is analogous to the methodology for the
bounded-degree graph model, which is presented in Section 5.

We mention that in a follow-up work [23], we employed this methodology in
order to resolve several open problems regarding the relation between adaptive
and non-adaptive testers in the dense graph model. In particular, we proved
that there exist graph properties for which any non-adaptive tester must have
query complexity that is almost quadratic in the query complexity of the best
general (i.e., adaptive) tester, whereas it has been known for a couple of
decades that the query complexity of non-adaptive testers is at most quadratic
in the query complexity of adaptive testers.

###### The case of intermediate degree bounds.

Lastly, in Section 10, we consider $n$-vertex graphs of degree bound $d(n)$,
for every $d:\mathbb{N}\to\mathbb{N}$ such that $d(n)\in[\Omega(1),n]$.
Indeed, the bounded-degree case (studied in Section 2–6) and the dense graph
case (studied in Sections 7–9) are special cases (which correspond to
$d(n)=O(1)$ and $d(n)=n$). Using results from these two special cases, we show
how to construct $\Omega(d(n))$-robustly self-ordered $n$-vertex graphs of
maximum degree $d(n)$, for all $d:\mathbb{N}\to\mathbb{N}$.

#####  1.2.2 Techniques

As evident from the foregoing description, we reduce the construction of
$\Omega(n)$-robustly self-ordered $n$-vertex graphs to the construction of
non-malleable two-source extractors.

Non-malleable two-source extractors were introduced in [8], as a variant on
seeded (one-source) non-malleable extractors, which were introduced in [12].
Loosely speaking, we say that ${\tt
nmE}:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\to\\{0,1\\}^{m}$ is a non-
malleable two-source extractor for a class of sources ${\cal C}$ if for every
two independent sources in ${\cal C}$, denoted $X$ ands $Y$, and for every two
functions $f,g:\\{0,1\\}^{\ell}\to\\{0,1\\}^{\ell}$ that have no fixed-point
it holds that $({\tt nmE}(X,Y),{\tt nmE}(f(X),g(Y)))$ is close to $(U_{m},{\tt
nmE}(f(X),g(Y))$, where $U_{m}$ denotes the uniform distribution over
$\\{0,1\\}^{m}$. We show that a non-malleable two-source extractor for the
class of $\ell$-bit sources of min-entropy $\ell-O(1)$, with a single output
bit (i.e., $m=1$) and constant error, suffices for constructing
$\Omega(n)$-robustly self-ordered $n$-vertex graphs. Recall that constructions
with much stronger parameters (e.g., min-entropy $\ell-\ell^{\Omega(1)}$,
negligible error, and $m=\ell^{\Omega(1)}$) were provided by Chattopadhyay,
Goyal, and Li [7, Thm. 1]. (These constructions are quite complex.
Interestingly, we are not aware of a simpler way of obtaining the weaker
parameters that we need.)

Actually, we show two reductions of the construction of $\Omega(n)$-robustly
self-ordered $n$-vertex graphs to the construction of non-malleable two-source
extractors. In both cases we use extractors that operate on pairs of sources
of length $\ell=\log_{2}n-O(1)$ that have min-entropy $k=\ell-O(1)$, hereafter
called $(\ell,k)$-sources. The extractor is used to define a bipartite graph
with $2^{\ell}$ vertices on each side, and a clique is placed on the vertices
of one side so that a permutation that maps vertices from one side to the
other side yields a proportional symmetric difference (between the original
graph and the resulting graph).

The first reduction, presented in Theorem 8.3, requires the extractor to be
quasi-orthogonal, which means that the residual functions obtained by any two
different fixings of one of the extractor’s two arguments are almost unbiased
and uncorrelated. Using the fact that non-malleable two-source extractors for
$(\ell,k)$-sources can we made quasi-orthogonal in $\exp(\ell)$-time, we
obtain an explicit construction of $\Omega(n)$-robustly self-ordered
$n$-vertex graphs (i.e., the $n$-vertex graph is constructed in ${\rm
poly}(n)$-time).

The second reduction, presented in Theorem 8.7, yields a strongly explicit
construction as asserted in Theorem 1.4 (i.e., the adjacency predicate of the
$n$-vertex graph is computable in ${\rm poly}(\log n)$-time). This reduction
uses an arbitrary non-malleable two-source extractor, and shifts the quasi-
orthogonality condition to two auxiliary bipartite graphs.

Both reductions are based on the observation that if the number of non-fixed-
points (of the permutation) is very large, then the non-malleability condition
implies a large symmetric difference (between the original graph and the
resulting graph). This holds as long as there are at least $\Omega(2^{\ell})$
non-fixed-points on each of the two sides of the corresponding bipartite graph
(which corresponds to the extractor). The complementary case is handled by the
quasi-orthogonality condition, and this is where the two reductions differ.

The simpler case, presented in the first construction (i.e., Theorem 8.3), is
that the extractor itself is quasi-orthogonal. In this case we consider the
non-fixed-points on the side that has more of them. The quasi-orthogonality
condition gives us a contribution of approximately $0.5\cdot 2^{\ell}$ units
per each non-fixed-point, whereas the upper-bound on the number of non-fixed-
points on the other side implies that most of these contributions actually
count in the symmetric difference (between the original graph and the
resulting graph).

In the second construction (i.e., Theorem 8.7), we augment the foregoing
$2^{\ell}$-by-$2^{\ell}$ bipartite graph, which is now determined by any non-
malleable extractor, with an additional $4\cdot 2^{\ell}$-vertex clique that
is connected to the two original $2^{\ell}$-vertex sets by a bipartite graph
that is merely quasi-orthogonal. The analysis is analogous to the one used in
the proof of Theorem 8.3, but is slightly more complex because we are dealing
with a slightly more complex graph.

###### Errata regarding the original posting.

We retract the claims made in our initial posting [21] regarding the
construction of non-malleable two-source extractors (which are quasi-
orthogonal) as well as the claims about the construction of relocation-
detecting codes (see Theorems 1.5 and 1.6 in the original version).888In [21]
quasi-orthogonality is called niceness; we prefer the current term, which is
less generic. The source of trouble is a fundamental flaw in the proof of [21,
Lem. 9.7], which may as well be wrong.

####  1.3 Perspective

Asymmetric graphs were famously studied by Erdos and Renyi [14], who
considered the (absolute) distance of asymmetric graphs from being symmetric
(i.e., the number of edges that should be removed or added to a graph to make
it symmetric), calling this quantity the degree of asymmetry. They studied the
extremal question of determining the largest possible degree of asymmetry of
$n$-vertex graphs (as a function of $n$). We avoided the term “robust
asymmetry” because it could be confused with the degree of asymmetry, which is
a very different notion. In particular, the degree of asymmetry cannot exceed
twice the degree of the graph (e.g., by disconnecting two vertices), whereas
our focus is on robustly self-ordered graphs of bounded-degree.

We mention that Bollobas proved that, for every constant $d\geq 3$, almost all
$d$-regular graphs are asymmetric [4, 5]. This result was extended to varying
$d\in[3,n-4]$ by Kim, Sudakov, and Vu [26]. We also mention that their proof
of [26, Thm. 3.1] implies that a random $n$-vertex Erdos–Renyi graph with edge
probability $p$ is $2p(1-p)n$-robustly self-ordered.

####  1.4 Roadmaps

This work consists of two parts. The first part (Sections 2–6) refers to
bounded-degree graphs, and the second part (Sections 7–10) refers to dense
graphs. These parts are practically independent of one another, except that
Theorem 10.3 builds upon Section 6. Even when focusing on one of these two
parts, its contents may attract attention from diverse perspectives. Each such
perspective may benefit from a different roadmap.

###### Efficient combinatorial constructions.

As mentioned above, in the regime of bounded-degree graphs we present two
different constructions that establish Theorem 1.3. Both constructions make
use of the edge-colored model and the transformations presented in Section 2.
The direct construction is presented in Section 3, and the three-step
construction appears in Section 4. The three-step construction is augmented by
local self-ordering and local reversed self-ordering algorithms (see Section
4.4).999For a locally constructable $G_{n}$ and $G^{\prime}=\phi^{-1}(G_{n})$,
a local self-ordering algorithm is given a vertex $v$ in $G^{\prime}$, and
returns $\phi(v)$. In contrast, a local reversed self-ordering algorithm is
given a vertex $i\in[n]$ of $G_{n}$ and returns $\phi^{-1}(i)$. Both
algorithms run in ${\rm poly}(\log n)$-time. In the regime of dense graphs,
Sections 7 and 8 refer to the constructability of a couple of combinatorial
objects; see roadmap “for the dense case” below.

###### Potential applications to property testing.

In Section 5 we demonstrate applications of Theorem 1.3 to proving lower
bounds (on the query complexity) for the bounded-degree graph testing model.
Specifically, we present a methodology of transporting bounds regarding
testing properties of strings to bounds regarding testing properties of
bounded-degree graphs. The specific applications presented in Section 5 rely
on Section 4. For the first application (Theorem 5.2) the construction
presented in Section 4.2 suffices; for the second application (i.e., Theorem
5.5, which establishes a separation between testing and tolerant testing in
the bounded-degree graph model), the local computation tasks studied in
Section 4.4 are needed. An analogous methodology for the dense graph testing
model is presented in Section 9.

###### Properties of random graphs.

As stated above, it turns out that random $O(1)$-regular graphs are robustly
self-ordered. This result is presented in Section 6, and this section can be
read independently of any other section. (In addition, Section 7 presents a
proof that random (dense) $n$-vertex graphs are $O(n)$-robustly self-ordered.)

###### The dense case and non-malleable two-source extractors.

The regime of dense graphs is studied in Sections 7–9, where the construction
of such graphs is undertaken in Section 8. In Section 7, we show that
$\Omega(n)$-robustly self-ordered $n$-vertex graphs provide yet another way of
obtaining $\Omega(1)$-robustly self-ordered bounded-degree graphs. In Section
8, we reduce the construction of $O(n)$-robustly self-ordered $n$-vertex
graphs to the construction of non-malleable two-source extractors. As outlined
in Section 1.2.2, we actually present two different reductions, where a key
issue is the quasi-orthogonality condition.

Lastly, in Section 10, for every $d:\mathbb{N}\to\mathbb{N}$ such that
$d(n)\in[\Omega(1),n]$, we show how to construct $n$-vertex graphs of maximum
degree $d(n)$ that are $\Omega(d(n))$-robustly self-ordered. Some of the
results and techniques presented in this section are also relevant to the
setting of bounded-degree graphs.

##  Part I The Case of Bounded-Degree Graphs

As stated in Section 1.1.2, a notion of robust self-ordering of edge-colored
graphs plays a pivotal role in our study of robustly self-ordered bounded-
degree graphs. This notion as well as a transformation from it to the
uncolored version (of Definition 1.2) is presented in Section 2.

In Section 3, we present a direct construction of $O(1)$-regular robustly
self-ordered edge-colored graphs; applying the foregoing transformation, this
provides our first proof of Theorem 1.3. Our second proof of Theorem 1.3 is
presented in Section 4, and consists of a three-step process (as outlined in
Section 1.1.2). Sections 3 and 4 can be read independently of one another, but
both rely on Section 2.

In Section 5 we demonstrate the applicability of robustly self-ordered
bounded-degree graphs to property testing; specifically, to proving lower
bounds (on the query complexity) for the bounded-degree graph testing model.
For these applications, the global notion of constructability, established in
Section 4.2, suffices. This construction should be preferred over the direct
construction presented in Section 3, because it yields graphs with small
connected components. More importantly, the subexponential separation between
the complexities of testing and tolerant testing of graph properties (i.e.,
Theorem 5.5) relies on the construction of Section 4 and specifically on the
local computation tasks studied in Section 4.4.

Lastly, in Section 6, we prove that random $O(1)$-regular graphs are robustly
self-ordered. This section may be read independently of any other section.

###  2 The Edge-Colored Variant

Many of our arguments are easier to make in a model of (bounded-degree) graphs
in which edges are colored (by a bounded number of colors), and where one
counts the number of mismatches between colored edges. Namely, an edge that
appears in one (edge-colored) graph contributes to the count if it either does
not appear in the other (edge-colored) graph or appears in it under a
different color. Hence, we define a notion of robust self-ordering for edge-
colored graphs. We shall then transform robustly self-ordered edge-colored
graphs to robustly self-ordered ordinary (uncolored) graphs, while preserving
the degree, the asymptotic number of vertices, and other features such as
expansion and degree-regularity. Specifically, the transformation consists of
replacing the colored edges by copies of different connected, asymmetric
(constant-sized) gadgets such that different colors are reflected by different
gadgets.

We start by providing the definition of the edge-colored model. Actually, for
greater flexibility, we will consider multi-graphs; that is, graphs with
possible parallel edges and self-loops. Hence, we shall consider multi-graphs
$G=(V,E)$ coupled with an edge-coloring function
$\chi\\!:\\!E\\!\to\\!\mathbb{N}$, where $E$ is a multi-set containing both
pairs of vertices and singletons (representing self-loops). Actually, it will
be more convenient to represent self-loops as 2-element multi-sets containing
two copies of the same vertex.

###### Definition 2.1

(robust self-ordering of edge-colored multi-graphs): Let $G=(V,E)$ be a multi-
graph with colored edges, where $\chi\\!:\\!E\\!\to\\!\mathbb{N}$ denotes this
coloring, and let $E_{i}$ denote the multi-set of edges colored $i$ (i.e.,
$E_{i}=\\{e\\!\in\\!E\\!:\\!\chi(e)\\!=\\!i\\}$). We say that $(G,\chi)$ is
$\gamma$-robustly self-ordered if for every permutation $\mu:V\to{V}$ it holds
that

$\sum_{i\in\mathbb{N}}\Big{|}E_{i}\;\triangle\left\\{\\{\mu(u),\mu(v)\\}\\!:\\!\\{u,v\\}\\!\in\\!E_{i}\right\\}\Big{|}\;\geq\;\gamma\cdot|\\{i\\!\in\\!V\\!:\\!\mu(i)\neq
i\\}|,$ (2)

where $A\triangle B$ denotes the symmetric difference between the multi-sets
$A$ and $B$; that is $A\triangle B$ contains $t$ occurrences of $e$ if the
absolute difference between the number of occurrences of $e$ in $A$ and $B$
equals $t$.

(Definition 1.2 is obtained as a special case when the multi-graph is actually
a graph and all edges are assigned the same color.)

We stress that whenever we consider “edge-colored graphs” we actually refer to
edge-colored multi-graphs (i.e., we explicitly allow parallel edges and self-
loops).101010We comment that a seemingly more appealing definition can be used
for edge-colored (simple) graphs. Specifically, in that case (i.e.,
$E\subseteq{V\choose 2}$), we can extend $\chi\\!:\\!E\\!\to\\!\mathbb{N}$ to
non-edges by defining $\chi(\\{u,v\\})=0$ if $\\{u,v\\}\not\in E$, and say
that $(G,\chi)$ is $\gamma$-robustly self-ordered if for every permutation
$\mu:V\to{V}$ it holds that  $\left|\left\\{\\{u,v\\}\in{V\choose
2}:\chi(\\{\mu(u),\mu(v)\\})\\!\neq\\!\chi(\\{u,v\\})\right\\}\right|\;\geq\;\gamma\cdot|\\{i\\!\in\\!V:\mu(i)\neq
i\\}|.$ In contrast, whenever we consider (uncolored) graph, we refer to
simple graphs (with no parallel edges and no self-loops).

Our transformation of robustly self-ordered edge-colored multi-graphs to
robustly self-ordered ordinary graphs depends on the number of colors used by
the multi-graph. In particular, $\gamma$-robustness of edge-colored multi-
graph that uses $c$ colors gets translated to $(\gamma/f(c))$-robustness of
the resulting graph, where $f:\mathbb{N}\to\mathbb{N}$ is an unbounded
function. Hence, we focus on coloring functions that use a constant number of
colors, denoted $c$. That is, fixing a constant $c\in\mathbb{N}$, we shall
consider multi-graphs $G=(V,E)$ coupled with an edge-coloring function
$\chi\\!:\\!E\\!\to\\![c]$.

####  2.1 Transformation to standard (uncolored) version

As a preliminary step for the transformation, we add self-loops to all
vertices and make sure that parallel edges are assigned different colors. The
self-loops make it easy to distinguish the original vertices from auxiliary
vertices that are parts of gadgets introduced in the main transformation.
Different colors assigned to parallel edges are essential to the mere
asymmetry of the resulting graph, since we are going to replace edges of the
same color by copies of the same gadget.

###### Construction 2.2

(preliminary step towards Construction 2.3): For a fixed $d\geq 3$, given a
multi-graph $G=(V,E)$ of maximum degree $d$ and an edge-coloring function
$\chi\\!:\\!E\\!\to\\![c]$, we define a multi-graph $G=(V,E^{\prime})$ and an
edge-coloring function $\chi^{\prime}\\!:\\!E^{\prime}\\!\to\\![d\cdot c+1]$
as follows.

  1. 1.

For every pair of vertices $u$ and $v$ that are connected by few parallel
edges, denoted $e^{(1)}_{u,v},...,e^{(d^{\prime})}_{u,v}$, we change the color
of $e^{(i)}_{u,v}$ to $\chi^{\prime}(e^{(i)}_{u,v})\leftarrow(i-1)\cdot
d+\chi(e^{(i)}_{u,v})$. This includes also the case $u=v$.

  2. 2.

We augment the multi-graph with self-loops colored $d\cdot c+1$; that is,
$E^{\prime}$ is the multi-set $E\cup\\{e_{v}:v\\!\in\\!V\\}$, where $e_{v}$ is
a self-loop added to $v$, and $\chi^{\prime}(e_{v})=dc+1$.

(Other edges $e\\!\in\\!E$ maintain their color; that is, them
$\chi^{\prime}(e)=\chi(e)$ holds).

(For simplicity, we re-color all parallel edges, save the first one, rather
than re-coloring only parallel edges of the same color.) Note that refining
the coloring may only increase the robustness parameter of a multi-graph.
Clearly, $G^{\prime}$ preserves many features of $G$. In particular, it
preserves $\gamma$-robust self-ordering, expansion, degree-regularity, and the
number of vertices.

As stated above, our transformation of edge-colored multi-graphs to ordinary
graphs uses gadgets, which are constant-size graphs. Specifically, when
handling a multi-graph of maximum degree $d$ with edges that are colored by
$c$ colors, we shall use $c$ different connected and asymmetric graphs.
Furthermore, in order to maintain $d$-regularity, we shall use $d$-regular
graphs as gadgets; and in order to have better control on the number of
vertices in the resulting graph, each of these gadgets will contain $k=k(d,c)$
vertices. The existence of such ($d$-regular) asymmetric (and connected)
graphs is well-known, let alone that it is known that a random $d$-regular
$k$-vertex graph is asymmetric (for any constant $d\geq 3$) [4, 5].

We stress that the different gadgets are each connected and asymmetric, and it
follows that they are not isomorphic to one another. We designate in each
gadget an edge $\\{p,q\\}$, called the designated edge, such that omitting
this edge does not disconnect the gadget. The endpoint of this edge will be
used to connect two vertices of the original multi-graph. Specifically, we
replace each edge $\\{u,v\\}$ (of the original multi-graph) that is colored
$i$ by a copy of the $i^{\rm th}$ gadget, while omitting one its designated
edge $\\{p,q\\}$ and connecting $u$ to $p$ and $v$ to $q$. The construction is
spelled out below.

We say that a (non-simple) multi-graph $G=(V,E)$ coupled with an edge-coloring
$\chi$ is eligible if each of its vertices contains a self-loop, and parallel
edges are assigned different colors. Recall that eligible comes almost for
free (by applying Construction 2.2). We shall apply the following construction
only to eligible edge-colored multi-graphs.

###### Construction 2.3

(the main transformation): For a fixed $d\geq 3$ and $c$, let $k=k(d,c)$ and
$G_{1},...,G_{k}$ be different asymmetric and connected $d$-regular graphs
over the vertex-set $[k]$. Given a multi-graph $G=(V,E)$ of maximum degree $d$
and an edge-coloring function $\chi\\!:\\!E\\!\to\\![c]$, we construct a graph
$G^{\prime}=(V^{\prime},E^{\prime})$ as follows.

> Suppose that the multi-set $E$ has size $m$. Then, for each $j\in[m]$, if
> the $j^{\rm th}$ edge of $E$ connects vertices $u$ and $v$, and is colored
> $i$, then we replace it by a copy of $G_{i}$, while omitting its designated
> edge and connecting one of its endpoints to $u$ and the other to $v$.
>
> Specifically, assuming that $V=[n]$ and recalling that $j$ is the index of
> the edge (colored $i$) that connects $u$ and $v$, let $G_{i}^{u,v}$ be an
> isomorphic copy of $G_{i}$ that uses the vertex set $\\{n+(j-1)\cdot
> k+i:i\\!\in\\![k]\\}$. Let $\\{p,q\\}$ be the designated edge in
> $G_{i}^{u,v}$, and ${\hat{G}}_{i}^{u,v}$ be the graph that results from
> $G_{i}^{u,v}$ by omitting $\\{p,q\\}$. Then, we replace the edge $\\{u,v\\}$
> by ${\hat{G}}_{i}^{u,v}$, and add the edges $\\{u,p\\}$ and $\\{v,q\\}$.

Hence, $V^{\prime}=[n+m\cdot k]$ and $E^{\prime}$ consists of the edges of all
${\hat{G}}_{i}^{u,v}$’s as well as the edges connecting the endpoint of the
corresponding designated edges to the corresponding vertices $u$ and $v$.

We stress that, although $G$ may have parallel edges and self-loops, the graph
$G^{\prime}$ has neither parallel edges nor self-loops. Also note that
$G^{\prime}$ preserve various properties of $G$ such as degree-regularity,
number of connected components, and expansion (up to a constant factor).

Showing that the resulting graph $G^{\prime}=(V^{\prime},E^{\prime})$ is
robustly self-ordered relies on a correspondence between the colored edges of
$G=(V,E)$ and the gadgets in $G^{\prime}$. For starters, suppose that the
permutation $\mu^{\prime}:V^{\prime}\to V^{\prime}$ maps $V$ to $V$ (i.e.,
$\mu^{\prime}(V)=V$), and gadgets to the corresponding gadgets; that is, if
$\mu^{\prime}$ maps the vertex-pair $(u,v)\in V^{2}$ to
$(\mu^{\prime}(u),\mu^{\prime}(v))\in V^{2}$, then $\mu^{\prime}$ maps the
vertices in the possible gadget that connects $u$ and $v$ to the vertices in
the gadget that connects $\mu^{\prime}(u)$ and $\mu^{\prime}(v)$. In such a
case, letting $\mu$ be the restriction of $\mu^{\prime}$ to $V$, a difference
of $D$ colored edges between $G$ and $\mu(G)$ translates to a difference of at
least $D$ edges between $G^{\prime}$ and $\mu^{\prime}(G^{\prime})$, due to
the difference between the gadgets that replace the corresponding edges of
$G^{\prime}$, whereas the number of non-fixed-point vertices in $\mu^{\prime}$
is $k$ times larger than the number of non-fixed-point vertices in $\mu$,
which is at most $D/\gamma$ (by the $\gamma$-robust self-ordering of $G$).
Hence, in this case we have

$\frac{|G^{\prime}\triangle\,\mu^{\prime}(G^{\prime})|}{|\\{v\in
V^{\prime}:\mu^{\prime}(v)\\!\neq\\!v\\}|}=\frac{D}{k\cdot|\\{v\in
V:\mu(v)\\!\neq\\!v\\}|}\geq\frac{D}{k\cdot D/\gamma}$

which equals $\gamma/k$. However, in general, $\mu^{\prime}$ needs not satisfy
the foregoing condition. Nevertheless, if $\mu^{\prime}$ splits some gadget or
maps some gadget in a manner that is inconsistent with the vertices of $V$
connected by it, then this gadget contributes at least one unit to the
difference between $G^{\prime}$ and $\mu^{\prime}(G^{\prime})$, whereas the
number of non-fixed-point vertices in this gadget is at most $k$. Lastly, if
$\mu^{\prime}$ maps vertices of a gadget to other vertices in the same gadget,
then we get a contribution of at least one unit due to the asymmetry of the
gadget. The foregoing is made rigorous in the proof of the following theorem.

###### Theorem 2.4

(from edge-colored robustness to standard robustness): For constant $d\geq 3$
and $c$, suppose that the multi-graph $G=(V,E)$ coupled with
$\chi\\!:\\!E\\!\to\\![c]$ is eligible and $\gamma$-robustly self-ordered.
Then, the graph $G^{\prime}=(V^{\prime},E^{\prime})$ resulting from
Construction 2.3 is $(\gamma/3k)$-robustly self-ordered, where $k=k(d,c)$ is
the number of vertices in a gadget (as determined above).

Proof: As a warm-up, let us verify that $G^{\prime}$ is asymmetric. We first
observe that the vertices of $G$ are uniquely identified (in $G^{\prime}$),
since they are the only vertices that are incident at copies of the gadget
that replaces the self-loops.111111Note that this gadget cannot appear as part
of any other gadget, since all gadgets have the same number of vertices.
Hence, any automorphism of $G^{\prime}$ must map $V$ to $V$. Consequently, for
any $i$, such an automorphism $\mu^{\prime}$ must map each copy of $G_{i}$ to
a copy of $G_{i}$, which induces a unique coloring of the edges of $G$. By the
“colored asymmetry” of $G$, this implies that $\mu^{\prime}$ maps each $v\in
V$ to itself, and consequently each copy of $G_{i}$ must be mapped (by
$\mu^{\prime}$) to itself. Finally, using the asymmetry of the $G_{i}$’s, it
follows that each vertex of each copy of $G_{i}$ is mapped to itself.

We now turn to proving that $G^{\prime}$ is actually robustly self-ordered.
Considering an arbitrary permutation $\mu^{\prime}:V^{\prime}\to V^{\prime}$,
we lower-bound the distance between $G^{\prime}$ and
$\mu^{\prime}(G^{\prime})$ as a function of the number of non-fixed-points
under $\mu^{\prime}$ (i.e., of $v\in V^{\prime}$ such that
$\mu^{\prime}(v^{\prime})\neq v^{\prime}$). We do so by considering the
contribution of each non-fixed-point to the distance between $G^{\prime}$ and
$\mu^{\prime}(G^{\prime})$. We first recall the fact that the vertices of $V$
(resp., of gadgets) are uniquely identified in $\mu^{\prime}(G^{\prime})$ by
virtue of the gadgets that replace self-loops (see the foregoing warm-up).

Case 1:

Vertices of some copy of $G_{i}$ that are not mapped by $\mu^{\prime}$ to a
single copy of $G_{i}$; that is, vertices in some $G_{i}^{u,v}$ that are not
mapped by $\mu^{\prime}$ to some $G_{i}^{u^{\prime},v^{\prime}}$.

(This includes the case of vertices $w^{\prime}$ and $w^{\prime\prime}$ of
some $G_{i}^{u,v}$ such that $\mu^{\prime}(w^{\prime})$ is in
$G_{i^{\prime}}^{u^{\prime},v^{\prime}}$ and $\mu^{\prime}(w^{\prime\prime})$
is in $G_{i^{\prime\prime}}^{u^{\prime\prime},v^{\prime\prime}}$, but
$(i^{\prime},u^{\prime},v^{\prime})\neq(i^{\prime\prime},u^{\prime\prime},v^{\prime\prime})$.
It also includes the case of a copy of $G_{i}$ that is mapped by
$\mu^{\prime}$ to a copy of $G_{j}$ for $j\neq i$, and the case that a vertex
$w$ in some $G_{i}^{u,v}$ that is mapped by $\mu^{\prime}$ to a vertex in
$V$.)

The set of vertices $S_{i}^{u,v}$ of each such copy (i.e., $G_{i}^{u,v}$)
contribute at least one unit to the difference between $G^{\prime}$ and
$\mu^{\prime}(G^{\prime})$, since $\mu^{\prime}(S_{i}^{u,v})$ induces a copy
of ${\hat{G}}_{i}$ in $\mu(G^{\prime})$ but not in $G^{\prime}$, where here we
also use the fact that the ${\hat{G}}_{i}$’s are connected (and not isomorphic
(for the case of $i^{\prime}=i^{\prime\prime}\neq i$)). Note that the total
contribution of all vertices of the current case equals at least the number of
gadgets in which they reside. Hence, if the current case contains $n_{1}$
vertices, then their contribution to the distance between $G^{\prime}$ and
$\mu^{\prime}(G^{\prime})$ is at least $n_{1}/k$.

Ditto for vertices that do not belong to a single copy of $G_{i}$ and are
mapped by $\mu^{\prime}$ to a single copy of $G_{i}$. (This also includes
$v\in V$ being mapped to some copy of some $G_{i}$.)

Case 2:

Vertices of some copy of $G_{i}$ that are mapped by $\mu^{\prime}$ to a single
copy of $G_{i}$, while not preserving their indices inside $G_{i}$.

(This refers to vertices of some $G_{i}^{u,v}$ that are mapped by $\mu$ to
vertices of $G_{i}^{u^{\prime},v^{\prime}}$, where $(u^{\prime},v^{\prime})$
may but need not equal $(u,v)$, such that for some $j\in[k]$ the $j^{\rm th}$
vertex of $G_{i}^{u,v}$ is not mapped by $\mu$ to the $j^{\rm th}$ vertex of
$G_{i}^{u^{\prime},v^{\prime}}$.)121212Recall that $G_{i}^{u,v}$ and
$G_{i}^{u^{\prime},v^{\prime}}$ are both copies of the $k$-vertex graph
$G_{i}$, which is an asymmetric graph, and so the notion of the $j^{\rm th}$
vertex in them is well-defined. Formally, the $j^{\rm th}$ vertex of
$G_{i}^{u,v}$ is $\phi^{-1}(j)$ such that $\phi$ is the (unique) bijection
satisfying $\phi(G_{i}^{u,v})=G_{i}$.

By the fact that $G_{i}$ is asymmetric, it follows that each such copy
contributes at least one unit to the difference between $G^{\prime}$ and
$\mu^{\prime}(G^{\prime})$, and so (again) the total contribution of all these
vertices is proportional to their number; that is, if the number of vertices
in this case is $n_{2}$, then their contribution is at least $n_{2}/k$.

Case 3:

Vertices $v\in V$ such that $\mu^{\prime}(v)\neq v$ (equiv.,
$\mu^{\prime}(v)\in V\setminus\\{v\\}$).

(This is the main case, where we use the hypothesis that the edge-colored $G$
is robustly self-ordered.

By the hypothesis that the edge-colored $G$ is robustly self-ordered, it
follows that such vertices contribute proportionally to the difference between
the colored versions of the multi-graphs $G$ and $\mu(G)$, where $\mu$ is the
restriction of $\mu^{\prime}$ to $V$. Specifically, the number of tuples
$(\\{u,v\\},i)$ such that $\\{u,v\\}$ is colored $i$ in exactly one of these
multi-graph (i.e., either in $G$ or in $\mu(G)$ but not in both) is at least
$\gamma\cdot|\\{v\\!\in\\!V:\mu(v)\neq v\\}|$. Assume, without loss of
generality that $\chi(\\{u,v\\})=i$ but either
$\\{{\mu^{-1}}(u),{\mu^{-1}}(v)\\}\not\in E$ or
$\chi(\\{{\mu^{-1}}(u),{\mu^{-1}}(v)\\})=j\neq i$. Either way, it follows that
some vertices that do not belong to a copy of $G_{i}$ are mapped by
$\mu^{\prime}$ to $G_{i}^{u,v}$, which means that Case 1 applies for each such
a tuple. Hence, if the number of vertices in the current case is $n_{3}$, then
$n_{1}\geq\gamma\cdot n_{3}$, and we get a contribution of at least
$\gamma\cdot n_{3}/k$ via Case 1.

Case 4:

Vertices of some copy of $G_{i}$ that are mapped by $\mu^{\prime}$ to a
different copy of $G_{i}$.

This refers to the case that $\mu^{\prime}$ maps $G_{i}^{u,v}$ to
$G_{i}^{u^{\prime},v^{\prime}}$ such that $(u^{\prime},v^{\prime})\neq(u,v)$,
which corresponds to mapping the gadget to a gadget connecting a different
pair of vertices (but by an edge of the same color).

For $u,v,u^{\prime},v^{\prime}$ and $i$ as above, if
$\mu^{\prime}(u)=u^{\prime}$ and $\mu^{\prime}(v)=v^{\prime}$, then a gadget
that connects $u$ and $v$ in $G^{\prime}$ is mapped to a gadget that does not
connects them in $\mu^{\prime}(G^{\prime})$ (but rather connects the vertices
$u^{\prime}$ and $v^{\prime}$, whereas either $u^{\prime}\neq u$ or
$v^{\prime}\neq v$). So we get a contribution of at least one unit to the
difference between $G^{\prime}$ and $\mu^{\prime}(G^{\prime})$ (i.e., the
gadget-edge incident at either $u$ or $v$), whereas the number of vertices in
this gadget is $k$. Hence, the contribution is proportional to the number of
non-fixed-points of the current type. Otherwise (i.e.,
$(\mu^{\prime}(u),\mu^{\prime}(v))\neq(u^{\prime},v^{\prime})$), we get a
vertex as in Case 3, and get a proportional contribution again.

Hence, the contribution of each of these cases to the difference between
$G^{\prime}$ and $\mu^{\prime}(G^{\prime})$ is proportional to the number of
vertices involved. Specifically, if there are $n_{i}$ vertices in Case $i$,
then we get a contribution-count of at least
$\gamma\cdot\sum_{i\in[4]}n_{i}/k$, where some of these contributions were
possibly counted thrice. The claim follows.

###### Remark 2.5

(fitting any desired number of vertices): Assuming that the hypothesis of
Theorem 2.4 can be met for any sufficiently large $n\in S\subseteq\mathbb{N}$,
Construction 2.3 yields robustly self-ordered $n^{\prime}$-vertex graphs for
any $n^{\prime}\in\\{k\cdot n:n\\!\in\\!S\\}$. To obtain such graphs also for
$n^{\prime}$ that is not a multiple of $k$, we may use two gadgets with a
different number of vertices for replacing at least one of the sets of colored
edges.

####  2.2 Application: Making the graph regular and expanding

We view the edge-colored model as an intermediate locus in a two-step
methodology for constructing robustly self-ordered graphs of bounded-degree.
First, one constructs edge-colored multi-graphs that are robustly self-ordered
in the sense of Definition 2.1, and then converts them to ordinary robustly
self-ordered graphs (in the sense of Definition 1.2), by using Construction
2.3 (while relying on Theorem 2.4).

We demonstrate the useful of this methodology by showing that it yields a
simple way of making robustly self-ordered graphs be also expanding as well as
regular, while maintaining a bounded degree. We just augment the original
graph by super-imposing an expander (on the same vertex set), while using one
color for the edges of the original graph and another color for the edges of
the expander. Note that we do not have to worry about the possibility of
creating parallel edges (since they are assigned different colors). The same
method applies in order to make the graph regular. We combine both
transformations in the following result, which we shall use in the sequel.

###### Theorem 2.6

(making the graph regular and expanding): For constant $d\geq 3$ and $\gamma$,
there exists an efficient algorithm that given a $\gamma$-robustly self-
ordered graph $G=(V,E)$ of maximum degree $d$, returns a $(d+O(1))$-regular
multi-graph coupled with a 2-coloring of its edges such that the edge-colored
graph is $\gamma$-robustly self-ordered (in the sense of Definition 2.1).

The same idea can be applied to edge-colored multi-graphs; in this case, we
use one color more than given. We could have avoided the creation of parallel
edges with the same color by using more colors, but preferred to relegate this
task to Construction 2.2, while recalling that it preserves both the expansion
and the degree-regularity. Either way, applying Theorem 2.4 to the resulting
edge-colored multi-graph, we obtain robustly self-ordered (uncolored) graphs.

Proof: For any $d^{\prime\prime}\geq d+d^{\prime}$, given a graph $G=(V,E)$ of
maximum degree $d$ that is $\gamma$-robustly self-ordered and a
$d^{\prime}$-regular expander graph $G^{\prime}=(V,E^{\prime})$, we construct
the desired $d^{\prime\prime}$-regular multi-graph $G^{\prime\prime}$ by
super-imposing the two graphs on the same vertex set, while assigning the
edges of each of these graphs a different color. In addition, we add edges to
make the graph regular, and color them using the same color as used for the
expander.131313We assume for simplicity that $|V^{\prime}|$ is even.
Alternatively, assuming that $G$ contains no isolated vertex, we first augment
it with an isolated vertex and apply the transformation on the resulting
graph. Yet another alternative is to consider only even $d^{\prime\prime}$.
Details follow.

  * •

We superimpose $G$ and $G^{\prime}$ (i.e., create a multi-graph $(V,E\cup
E^{\prime})$), while coloring the edges of $G$ (resp., $G^{\prime}$) with
color 1 (resp., color 2).

Note that this may create parallel edges, but with different colors.

  * •

Let $d_{v}\leq d+d^{\prime}$ denote the degree of vertex $v$ in the resulting
multi-graph. Then, we add edges to this multi-graph so that each vertex has
degree $d^{\prime\prime}$. These edges will also be colored 2.

(Here, unless we are a bit careful, we may introduce parallel edges that are
assigned the same color. This can be avoided by using more colors for these
added edges, but in light of Construction 2.2 (which does essentially the
same) there is no reason to worry about this aspect.)

(Recall that the resulting edge-colored multi-graph is denoted
$G^{\prime\prime}$.)

The crucial observation is that, since the edges of $G$ are given a distinct
color in $G^{\prime\prime}$, the added edges do not harm the robust self-
ordering feature of $G$. Hence, for any permutation $\mu:V\to V$, any vertex-
pair that contributes to the symmetric difference between $G$ and $\mu(G)$,
also contributes to an inequality between colored edges of $G^{\prime\prime}$
and $\mu(G^{\prime\prime})$ (by virtue of the edges colored 1).

####  2.3 Local computability of the transformations

In this subsection, we merely point out that the transformation presented in
Constructions 2.2 and 2.3 as well as the one underlying the proof of Theorem
2.6 preserve efficient local computability (e.g., one can determine the
neighborhood of a vertex in the resulting multi-graph by making a
polylogarithmic number of neighbor-queries to the original multi-graph).
Actually, this holds provided that we augment the (local) representation of
graphs, in a natural manner.

Recall that the standard representation of bounded-degree graphs is by their
incidence functions. Specifically, a graph $G=([n],E)$ of maximum degree $d$
is represented by the incident function $g:[n]\times[d]\to[n]\cup\\{0\\}$ such
that $g(v,i)=u\in[n]$ if $u$ is the $i^{\rm th}$ neighbor of $v$, and
$g(v,i)=0$ if $v$ has less than $i$ neighbors. This does not allow us to
determined the identity of the $j^{\rm th}$ edge in $G$, nor even to determine
the number of edges in $G$, by making a polylogarithmic number of queries to
$g$. Nevertheless, efficient local computability is preserved if we use the
following local representation (presented for edge-colored multi-graphs).

###### Definition 2.7

(local representation): For $d,c\in\mathbb{N}$, a local representation of a
multi-graph $G=([n],E)$ of maximum degree $d$ that is coupled with a coloring
$\chi\\!:\\!E\\!\to\\![c]$ is provided by the following three functions:

  1. 1.

An incidence function $g_{1}:[n]\times[d]\to\mathbb{N}\cup\\{0\\}$ such that
$g_{1}(v,i)=j\in\mathbb{N}$ if $j$ is the index of the $i^{\rm th}$ edge that
incident at vertex $v$, and $g_{1}(v,i)=0$ if $v$ has less than $i$ incident
edges.

  2. 2.

An edge enumeration function
$g_{2}:\mathbb{N}\to([n]^{2}\times[c])\cup\\{0\\}$ such that
$g_{2}(j)=(u,v,\chi(e_{j})$ if the $j^{\rm th}$ edge, denoted $e_{j}$,
connects the vertices $u$ and $v$, and $g_{2}(j)=0$ if the multi-graph has
less than $j$ edges.

  3. 3.

An vertex enumeration (by degree) function
$g_{3}:[d]\to([n]\to[n])\cup\\{0\\}$ such that $g_{3}(i,j)=v\in[n]$ if $v$ is
the $i^{\rm th}$ vertex of degree $j$ in the multi-graph, and $g_{3}(i,j)=0$
if the multi-graph has less than $j$ vertices of degree $i$.

Needless to say, the function $g_{3}$ is redundant in the case that we are
guaranteed that the multi-graph is regular. One may augment the above
representation by providing also the total number of edges, but this number
can be determined by binary search.

###### Theorem 2.8

(the foregoing transformations preserve local computability): The local
representation of the multi-graph that result from Construction 2.2 can be
computed by making a polylogarithmic number of queries to the given multi-
graph. The same holds for Construction 2.3 and for the transformation
underlying the proof of Theorem 2.6.

Proof: For Construction 2.2, we mostly need to enumerate all parallel edges
that connect $u$ and $v$. This can be done easily by querying the incidence
function on $(u,1),...,(u,d)$ and querying the edge enumeration function on
the non-zero answers. (In addition, when adding a self-loop on vertex
$v\in[n]$, we need to determine the degree of $v$ as well as the number of
edges in the multi-graph (in order to know how to index the self-loop in the
incidence and edge enumeration functions, respectively). For Construction 2.3,
we merely need to determine the color of the $j^{\rm th}$ edge and its index
in the incidence list of each of its endpoints (in order to replace it by
edges that lead to the gadget).

For the transformation underlying the proof of Theorem 2.6, adding edges to
make the multi-graph regular requires determining the index of a vertex in the
list of all vertices of the same degree (in order to properly index the added
edges). Here is where we use the vertex enumeration (by degree) function. (We
also need to select a fixed procedure for transforming an sorted $n$-long
sequence $(d_{1},...,d_{n})\in[d^{\prime\prime}]$ into an
all-$d^{\prime\prime}$ sequence by making pairs of increments; that is, given
$j\in[D]$ such that $D=(d^{\prime\prime}n-\sum_{i\in[n]}d_{i})/2$, we should
determine a pair $(u_{j},v_{j})$ such that for every $i\in[n]$ it holds that
$d_{i}+|\\{j:u_{j}\\!=\\!i\\}|+|\\{j:v_{j}\\!=\\!i\\}|=d^{\prime\prime}$.)

###  3 The Direct Construction

We shall make use of the edge-colored variant presented in Section 2, while
relying on the fact that robustly self-ordered colored multi-graphs can be
efficiently transformed into robustly self-ordered (uncolored) graphs.
Actually, it will be easier to present the construction as a directed edge-
colored multi-graph. Hence, we first define a variant of robust self-ordering
for directed edge-colored multi-graph (see Definition 3.1), then show how to
construct such multi-graphs (see Section 3.2), and finally show how to
transform the directed variant into an undirected one (see Section 3.1).

The construction is based on $d$ permutations, denoted
$\pi_{1},...,\pi_{d}:[n]\to[n]$, and consists of the directed edge-colored
multi-graph that is naturally defined by them. Specifically, for every
$v\in[n]$ and $i\in[d]$, this multi-graph contains a directed edge, denoted
$(v,\pi_{i}(v)$, that goes from vertex $v$ to vertex $\pi_{i}(v)$, and is
colored $i$.

We prove that a sufficient condition for this edge-colored directed multi-
graph, denoted $G_{1}$, to be robustly self-ordered is that a related multi-
graph is an expander. Specifically, we refer to the multi-graph
$G_{2}=(V_{2},E_{2})$ that represents the actions of the permutation of pairs
of vertices of $G_{1}$; that is,
$V_{2}=\\{(u,v)\\!\in\\![n]^{2}:u\\!\neq\\!v\\}$ and
$E_{2}=\\{\\{(u,v),(\pi_{i}(u),\pi_{i}(v))\\}:(u,v)\\!\in\\!V_{2}\,\&\,i\\!\in\\![d]\\}$.

The foregoing requires extending the notion of robustly self-ordered (edge-
colored) multi-graphs to the directed case. The extension is straightforward
and is spelled-out next, for sake of good order.

###### Definition 3.1

(robust self-ordering of edge-colored directed multi-graphs): Let $G=(V,E)$ be
a directed multi-graph with colored edges, where
$\chi\\!:\\!E\\!\to\\!\mathbb{N}$ denotes this coloring, and let $E_{i}$
denote the multi-set of edges colored $i$. We say that $(G,\chi)$ is
$\gamma$-robustly self-ordered if for every permutation $\mu:V\to{V}$ it holds
that

$\sum_{i\in\mathbb{N}}\Big{|}E_{i}\;\triangle\left\\{(\mu(u),\mu(v))\\!:\\!(u,v)\\!\in\\!E_{i}\right\\}\Big{|}\;\geq\;\gamma\cdot|\\{i\\!\in\\!V\\!:\\!\mu(i)\neq
i\\}|,$ (3)

where $A\triangle B$ denotes the symmetric difference between the multi-sets
$A$ and $B$ (as in Definition 2.1).

(The only difference between Definition 3.1 and Definition 2.1 is that Eq. (3)
refers to the directed edges of the directed multi-graph, whereas Eq. (2)
refers to the undirected edges of the undirected multi-graph.)

In Section 3.1 we present a construction of a directed edge-colored
$O(1)$-regular multi-graph that is $\Omega(1)$-robustly self-ordered. We shall
actually present a sufficient condition and a specific instantiation that
satisfies it. In Section 3.2 we show how to transform any directed edge-
colored multi-graph into an undirected one while preserving all relevant
features; that is, bounded robustness, bounded degree, regularity, expansion,
and local computability.

####  3.1 A sufficient condition for robust self-ordering of directed colored
graphs

For any $d$ permutations, $\pi_{1},...,\pi_{d}:[n]\to[n]$, we consider two
multi-graphs.

  1. 1.

The primary multi-graph (of $\pi_{1},...,\pi_{d}$) is a directed multi-graph,
denoted $G_{1}=([n],E_{1})$, such that
$E_{1}=\\{(v,\pi_{i}(v)):v\\!\in\\![n]\,\&\,i\\!\in\\![d]\\}$. This directed
multi-graph is coupled with an edge-coloring in which the directed edge from
$v$ to $\pi_{i}(v)$ is colored $i$.

  2. 2.

The secondary multi-graph (of $\pi_{1},...,\pi_{d}$) is an undirected multi-
graph, denoted $G_{2}=(V_{2},E_{2})$, such that
$V_{2}=\\{(u,v)\\!\in\\![n]^{2}:u\\!\neq\\!v\\}$ and
$E_{2}=\\{\\{(u,v),(\pi_{i}(u),\pi_{i}(v))\\}:(u,v)\\!\in\\!V_{2}\,\&\,i\\!\in\\![d]\\}$.

We note that each of these multi-graphs is a Schreier graph that correspond to
the action of the permutation $\pi_{1},...,\pi_{d}$ on the corresponding
vertex sets (i.e., $[n]$ and $V_{2}$, respectively). For a wider perspective
see the (paragraph at the) end of this subsection.

We now state the main result of this section, which asserts that the primary
multi-graph $G_{1}$ is robustly self-ordered if the secondary multi-graph
$G_{2}$ is an expander. We use the combinatorial definition of expansion: A
multi-graph $G=(V,E)$ is $\gamma$-expanding if, for every subset $S$ of size
at most $|V|/2$, there are at least $\gamma\cdot|S|$ vertices in $V\setminus
S$ that neighbor some vertex in $S$.

###### Theorem 3.2

(expansion of $G_{2}$ implies robust self-ordering of $G_{1}$): For any $d\geq
2$ permutations, $\pi_{1},...,\pi_{d}:[n]\to[n]$, if the secondary multi-graph
$G_{2}$ of $\pi_{1},...,\pi_{d}$ is $\gamma$-expanding, then the primary
directed multi-graph $G_{1}$ of $\pi_{1},...,\pi_{d}$ coupled with the
foregoing edge-coloring is $\gamma$-robustly self-ordered. Furthermore,
$G_{1}$ (or rather the undirected multi-graph underlying $G_{1}$) is
$\min(0.25,\gamma/3)$-expanding.

Proof: Let $\mu:[n]\to[n]$ be an arbitrary permutation, and let
$T=\\{v\\!\in\\![n]:\mu(v)\\!\neq\\!v\\}$ be its set of non-fixed-points.
Then, the size of the symmetric difference between $G_{1}$ and $\mu(G_{1})$
equals $2\cdot\sum_{i\in[d]}|D_{i}|$ such that $v\in D_{i}$ if
$(\mu(v),\mu(\pi_{i}(v)))$ is either not an edge in $G_{1}$ or is not colored
$i$ in it, whereas $(v,\pi_{i}(v))$ is an edge colored $i$ in $G_{1}$. Note
that if $(\mu(v),\mu(\pi_{i}(v)))$ is not an $i$-colored edge in $G_{1}$, then
$\pi_{i}(\mu(v))\neq\mu(\pi_{i}(v))$. Hence,
$D_{i}=\\{v\\!\in\\![n]:\mu(\pi_{i}(v))\neq\pi_{i}(\mu(v))\\}$.

The key observation (proved next) is that if $v\in T\setminus D_{i}$, then
$(\pi_{i}(v),\pi_{i}(\mu(v))\in T_{2}$, where
$T_{2}=\\{(v,\mu(v)):v\\!\in\\!T\\}$ represents the sets of replacements
performed by $\mu$. This fact implies that if $\sum_{i\in[d]}|D_{i}|$ is small
in comparison to $|T|$, then the set $T_{2}$ (which is a set of vertices in
$G_{2}$) does not expand much, in contradiction to the hypothesis. Details
follow.

###### Observation 3.2.1

(key observation): For $T,~{}D_{i}$ and $T_{2}$ as defined above, if $v\in
T\setminus D_{i}$,
then $(\pi_{i}(v),\pi_{i}(\mu(v))\in T_{2}$.

Recall that $v\in T$ implies $(v,\mu(v))\in T_{2}$. Observation 3.2.1 asserts
that if (in addition to $v\in T$) it holds that $v\not\in D_{i}$, then
$(\pi_{i}(v),\pi_{i}(\mu(v))$ is also in $T_{2}$. This means that the edges
colored $i$ incident at $\\{(\pi_{i}(v),\pi_{i}(\mu(v))):v\\!\in\\!T\setminus
D_{i}\\}$ do not contribute to the expansion of the set $T_{2}$ in $G_{2}$.

Proof: Since $v\not\in D_{i}$ we have $\pi_{i}(\mu(v))=\mu(\pi_{i}(v))$, and
$\mu(\pi_{i}(v))\neq\pi_{i}(v)$ follows, because otherwise
$\pi_{i}(\mu(v))=\pi_{i}(v)$, which implies $\mu(v)=v$ in contradiction to
$v\in T$. However, $\mu(\pi_{i}(v))\neq\pi_{i}(v)$ means that $\pi_{i}(v)\in
T$, and $(\pi_{i}(v),\pi_{i}(\mu(v)))=(\pi_{i}(v),\mu(\pi_{i}(v)))\in T_{2}$
follows.

Conclusion. Recall that Observation 3.2.1 implies that
$\\{(\pi_{i}(v),\pi_{i}(\mu(v))):v\\!\in\\!T\setminus D_{i}\\}\subseteq
T_{2}$, whereas
$\bigcup_{i\in[d]}\\{(\pi_{i}(v),\pi_{i}(\mu(v))):v\\!\in\\!T\\}$ is the
neighborhood of $T_{2}$ in the multi-graph $G_{2}$ (since
$\\{(\pi_{i}(v),\pi_{i}(\mu(v))):i\\!\in\\![d]\\}$ the neighbor-set of
$(v,\mu(v))$ in $G_{2}$). Using the $\gamma$-expansion of $G_{2}$ (and
$|T_{2}|\leq n<|V_{2}|/2$), it follows that
$\sum_{i\in[d]}|D_{i}|\geq\gamma\cdot|T|$. The main claim follows.

The expansion of $G_{1}$ is shown by relating sets of vertices of $G_{1}$ to
the corresponding sets of pairs in $G_{2}$. Specifically, for and
$S\subset[n]$ of size at most $n/2$, we consider the set
$T=\\{(u,v)\\!\in\\!V_{2}:u,v\\!\in\\!S\\}$, which has size
$|S|\cdot(|S|-1)\leq\frac{n}{2}\cdot(\frac{n}{2}-1)<\frac{|V_{2}|}{2}$.
Letting $T^{\prime}$ denote the set of neighbors of $T$ in $G_{2}$, and
$|S^{\prime}|$ denote the set of neighbors of $S$ in $G_{1}$, we have
$|T^{\prime}\setminus T|\geq\gamma\cdot|T|$, on the one hand (by expansion of
$G_{2}$), and $|T^{\prime}\setminus T|\leq 2\cdot|S|\cdot|S^{\prime}\setminus
S|+|S^{\prime}\setminus S|\cdot(|S^{\prime}\setminus S|-1)$ on the other hand.
This implies $|S^{\prime}\setminus S|\geq(\gamma/3)\cdot|S|$ (unless $|S|<5$,
which can be handled by using $|S^{\prime}\setminus S|\geq 1$).

###### Primary and secondary multi-graphs based on ${\rm SL}_{2}(p)$.

Recall that ${\rm SL}_{2}(p)$ is the group of 2-by-2 matrices over ${\rm
GF}(p)$ that have determinant 1. There are several different explicit
constructions of constant-size expanding generating sets for ${\rm
SL}_{2}(p)$, namely making the associated Cayley graph an expander (see, e.g.,
[28], [27, Thm. 4.4.2(i)], and [6]). We use any such generating set to define
a directed (edge-colored) multi-graph $G_{1}$ on $p+1$ vertices, and show that
the associated multi-graph on pairs, $G_{2}$, is an expander.

###### Proposition 3.3

(expanding generators for ${\rm SL}_{2}(p)$ yield an expanding secondary
multi-graph): For any prime $p>2$, let $V=\\{(1,i)^{\top}:i\in{\rm
GF}(p)\\}\cup\\{(0,1)^{\top}\\}$, and $M_{1},...,M_{d}\in{\rm SL}_{2}(p)$. For
every $i\in[d]$, define $\pi_{i}:V\to V$ such that $\pi_{i}(u)=v$ if $v\in V$
is a non-zero multiple of $M_{i}u$. Then:

  1. 1.

Each $\pi_{i}$ is a bijection.

  2. 2.

If the Cayley multi-graph ${\cal C}={\cal C}({\rm
SL}_{2}(p),\\{M_{1},...,M_{d}\\})=({\rm
SL}_{2}(p),\\{\\{M,M_{i}M\\}:M\\!\in{\rm SL}_{2}(p)\,\&\,i\\!\in\\![d]\\})$ is
an expander, then the (Schreier) multi-graph $G_{2}$ with vertex-set
$P=\\{(v,v^{\prime}):v\\!\in\\!V\,\&\,v^{\prime}\\!\in\\!V\setminus\\{v\\}\\}$
and edge-set
$\\{\\{(v,v^{\prime}),(\pi_{i}(v),\pi_{i}(v^{\prime}))\\}:(v,v^{\prime})\\!\in\\!P\\}$
is an expander.

Part 1 implies that these permutations yield a primary directed edge-colored
multi-graph on the vertex-set $V$, whereas Part 2 asserts that the
corresponding secondary graph is an expander (if the corresponding Cayley
graph is expanding). Note that $|V|=p+1$ and $|P|=(p+1)p$, whereas $|{\rm
SL}_{2}(p)|=p^{3}-p=(p-1)\cdot|P|$.

Proof: Part 1 follows by observing that for every $M\in{\rm SL}_{2}(p)$ and
every vector $v\in{\rm GF}(p)^{2}$ and scalar $\alpha\in{\rm GF}(p)$ it holds
that $M\alpha v=\alpha Mv$. Consequently, if for some non-zero
$\alpha,\alpha^{\prime}\in{\rm GF}(p)$ it holds that $\alpha
Mv=\alpha^{\prime}Mv^{\prime}$, then $Mv=M\alpha^{\prime\prime}v^{\prime}$ for
$\alpha^{\prime\prime}=\alpha^{\prime}/\alpha$, which implies
$v=\alpha^{\prime\prime}v^{\prime}$ (since $M$ is invertible). (Hence,
$\pi_{i}(v)=\pi_{i}(v^{\prime})$, for $v,v^{\prime}\in V$, implies
$v=v^{\prime}$.)

Part 2 follows by observing that the vertices of $G_{2}$ correspond to
equivalence classes of the vertices of ${\cal C}$ that are preserved by ${\rm
SL}_{2}(p)$, where $A,B\in{\rm SL}_{2}(p)$ are equivalent if the columns of
$A$ are non-zero multiples of the corresponding columns of $B$. That is, we
consider an equivalence relation, denoted $\equiv$, such that for
$A=[A_{1}|A_{2}]$ and $B=[B_{1}|B_{2}]$ in ${\rm SL}_{2}(p)$ it holds that
$A\equiv B$ if $A_{i}=\alpha_{i}B_{i}$ for both $i\in\\{1,2\\}$, where
$\alpha_{1},\alpha_{2}\in[p-1]$ (and, in fact,
$\alpha_{2}=1/\alpha_{1}$).141414Recall that ${\rm det}(A)=1={\rm det}(B)$,
whereas ${\rm
det}([\alpha_{1}B_{1}|\alpha_{2}B_{2}])=\alpha_{1}\alpha_{2}\cdot{\rm
det}(B)$. Note that each equivalence class contains a single element of $P$.
By saying that these equivalence classes are preserved by ${\rm SL}_{2}(p)$,
we mean that, for every $A,B,M\in{\rm SL}_{2}(p)$, if $A\equiv B$, then
$MA\equiv MB$. Hence, the (combinatorial) expansion of $G_{2}$ follows from
the expansion of ${\cal C}$, because the neighbors of a vertex-set $S\subseteq
P$ in $G_{2}$ are the vertices of $G_{2}$ that are equivalent to $T^{\prime}$
such that $T^{\prime}$ is the set of vertices of ${\tt CC}^{(t)}$ that
neighbor (in ${\tt CC}^{(t)}$) vertices that are equivalent to vertices in
$S$.151515Specifically, let $S$ have density at most half in $P$, and let $T$
be the set of vertices of ${\cal C}$ that are equivalent to $S$. Note that
$|T|=(p-1)\cdot|S|$, since each equivalence class contains a single element of
$P$. By the foregoing, the set of neighbors of $T$ in ${\cal C}$, denoted
$T^{\prime}$, is a collection of equivalence classes of vertices of $G_{2}$,
and $|T^{\prime}\setminus T|=\Omega(|T|)$ by the expansion of ${\cal C}$. It
follows that the set of neighbors of $S$ in $G_{2}$, denoted $S^{\prime}$, is
the set of vertices that are equivalent to $T^{\prime}$, which implies that
$|S^{\prime}\setminus S|=\frac{|T^{\prime}\setminus T|}{p-1}=\Omega(|S|)$.

###### A simple construction.

Combining Theorem 3.2 with Proposition 3.3, while using a simple pair of
expanding generators (which does not yield a Ramanujan graph), we get

###### Corollary 3.4

(a simple robustly self-ordered primary multi-graph): For any prime $p>2$, let
$V=\\{(1,i)^{\top}:i\in{\rm GF}(p)\\}\cup\\{(0,1)^{\top}\\}$, and consider the
matrices

$M_{1}\stackrel{{\scriptstyle\rm def}}{{=}}\left(\begin{array}[]{cc}1&1\\\
0&1\end{array}\right)\;\;\;\;\;\mbox{\rm
and}\;\;\;\;\;M_{2}\stackrel{{\scriptstyle\rm
def}}{{=}}\left(\begin{array}[]{cc}0&1\\\ -1&0\end{array}\right)$ (4)

Then, for $\pi_{1}$ and $\pi_{2}$ defined as in Proposition 3.3, the
corresponding primary (directed edge-colored) multi-graph is robustly self-
ordered.

This follows from the fact that the corresponding Cayley graph ${\cal C}({\rm
SL}_{2}(p),\\{M_{1},M_{2}\\})$ is an expander [27, Thm. 4.4.2(i)].

###### Perspective.

The foregoing construction using the group ${\rm SL}_{2}(p)$ is a special case
of a much more general family of constructions, and the elements of the proof
of Proposition 3.3 follow an established theory (explained, e.g., in [25, Sec.
11.1.2]), which we briefly describe.

Let $H$ be any finite group, and $S$ an expanding generating set of $H$ (i.e.,
the Cayley graph ${\cal C}(H,S)$ is an expander). Assume that $H$ acts on a
finite set $V$ (i.e., each $h\in H$ is associated with a permutation on $V$,
and $h^{\prime}h(v)=h^{\prime}(h(v))$ for every $h,h^{\prime}\in H$ and $v\in
V$). Then, the primary (directed edge-colored) multi-graph $G_{1}$ on vertices
$V$ can be constructed from the permutations defined by members of $S$. The
secondary multi-graph $G_{2}$ is naturally defined by the action of $S$ on
pairs of elements in $V$. Finally, the expansion of ${\cal C}(H,S)$ implies
that every connected component of $G_{2}$ is an expander.161616Indeed, this
was easy to demonstrate directly in the case of Proposition 3.3. Thus,
whenever this (Schreier) graph $G_{2}$ is connected (as it is in Proposition
3.3), one may conclude that $G_{1}$ is a directed edge-colored robustly self-
ordered multi-graph.

####  3.2 From the directed variant to the undirected one

In this section we show how to transform directed (edge-colored) multi-graphs,
of the type constructed in Section 3.1, into undirected ones, while preserving
all relevant features (i.e., bounded robustness, bounded degree, regularity,
expansion, and local computability). The transformation is extremely simple
and natural: We replace the directed edge $(u,v)$ colored $j$ by a 2-path with
a designated auxiliary vertex $a_{u,v,j}$, while coloring the edge
$\\{u,a_{u,v,j}\\}$ by $2j-1$ and the edge $\\{a_{u,v,j},v\\}$ by $2j$.
Evidently, this colored 2-path encodes the direction of the original edge (as
well as the original color).

Note that the foregoing transformation works well provided that there are no
parallel edges that are colored with the same color, a condition which is
satisfied by the construction presented in Section 3.1. Furthermore, since the
latter construction has no vertices of (in+out) degree less that $2d\geq 4$,
there is no need to mark the original vertices by self-loops. Hence, a
preliminary step akin to Construction 2.2 in unnecessary here, although it can
be performed in general.

###### Proposition 3.5

(from directed robust self-ordering to undirected robust self-ordering): For
constants $d\geq 3$ and $c$, let $G=(V,E)$ be a directed multi-graph in which
each vertex has between three and $d$ incident edges (in both directions), and
that $G$ is coupled with an edge-coloring function $\chi\\!:\\!E\\!\to\\![c]$
such that no parallel edges (in same the direction) are assigned the same
color. Letting $E_{i}=\\{e\\!\in\\!E:\chi(e)=i\\}$ denote the set of edges
colored $i$ in $G$, consider the undirected multi-graph
$G^{\prime}=(V^{\prime},E^{\prime})$ such that
$V^{\prime}=V\cup\\{a_{u,v,i}:(u,v)\\!\in\\!E_{i}\\}$ and
$E^{\prime}=\bigcup_{j\in[2c]}E^{\prime}_{j}$ where

$\displaystyle E^{\prime}_{2i-1}$ $\displaystyle=$
$\displaystyle\\{\\{u,a_{u,v,i}\\}:(u,v)\\!\in\\!E_{i}\\},$ $\displaystyle
E^{\prime}_{2i}$ $\displaystyle=$
$\displaystyle\\{\\{a_{u,v,i},v\\}:(u,v)\\!\in\\!E_{i}\\},$

and the edge-coloring function $\chi^{\prime}\\!:\\!E^{\prime}\\!\to\\![2c]$
that assigns the edges of $E^{\prime}_{j}$ the color $j$ (i.e.,
$\chi^{\prime}(e)=j$ for every $e\\!\in\\!E^{\prime}_{j}$). Then, if
$(G,\chi)$ is $\gamma$-robustly self-ordered (in the sense of Definition 3.1),
then $(G^{\prime},\chi^{\prime})$ is $(\gamma/2)$-robustly self-ordered (in
the sense of Definition 2.1).

We comment that the transformation of $(G,\chi)$ to
$(G^{\prime},\chi^{\prime})$ preserves bounded robustness, bounded degree,
regularity, expansion, and local computability (cf. Theorem 2.8).

Proof: The proof is analogous to the proof of Theorem 2.4, but it is much
simpler because the gadgets used in the current transformation (i.e., the
auxiliary vertices $a_{u,v,i}$) are much simpler.

Considering an arbitrary permutation $\mu^{\prime}:V^{\prime}\to V^{\prime}$,
we lower-bound the distance between $G^{\prime}$ and
$\mu^{\prime}(G^{\prime})$ as a function of the number of non-fixed-points
under $\mu^{\prime}$. We do so by considering the contribution of each non-
fixed-point to the distance between $G^{\prime}$ and
$\mu^{\prime}(G^{\prime})$. We first recall the fact that the vertices of $V$
(resp., the auxiliary vertices) are uniquely identified in
$\mu^{\prime}(G^{\prime})$ by virtue of the their degree, since each vertex of
$V$ has degree at least three (in $G^{\prime}$) whereas the auxiliary vertices
have degree 2.

Case 1:

Auxiliary vertices of the form $a_{u,v,i}$ that are not mapped by
$\mu^{\prime}$ to auxiliary vertices of the form
$a_{u^{\prime},v^{\prime},i}$; that is,
$\mu^{\prime}(a_{u,v,i})\in(V\cup\bigcup_{j\neq
i}\\{a_{u^{\prime},v^{\prime},j}:(u^{\prime},v^{\prime})\\!\in\\!E\\})$.

Each such vertex $a_{u,v,i}$ contributes at least one unit to the difference
between $G^{\prime}$ and $\mu^{\prime}(G^{\prime})$, since the two edges
incident at $a_{u,v,i}$ (in $G^{\prime}$) are colored $2i-1$ and $2i$
respectively, whereas $\mu(a_{u,v,i})$ has either more than two edges (in
$G^{\prime}$) or its two edges are colored $2j-1$ and $2j$, respectively,
where for $j\neq i$. Hence, if the current case contains $n_{1}$ vertices,
then their contribution to the distance between $G^{\prime}$ and
$\mu^{\prime}(G^{\prime})$ is at least $n_{1}$.

Ditto for vertices of $V$ that are mapped by $\mu^{\prime}$ to an auxiliary
vertex.

Case 2:

Vertices $v\in V$ such that $\mu^{\prime}(v)\in V\setminus\\{v\\}$.

By the hypothesis that the edge-colored directed $G$ is robustly self-ordered,
it follows that such vertices contribute proportionally to the difference
between the colored versions of the directed multi-graphs $G$ and $\mu(G)$,
where $\mu$ is the restriction of $\mu^{\prime}$ to $V$. Specifically, the
number of tuples $((u,v),i)$ such that $(u,v)$ is colored $i$ in exactly one
of these multi-graph (i.e., either in $G$ or in $\mu(G)$ but not in both) is
at least $\gamma\cdot|\\{v\\!\in\\!V:\mu(v)\neq v\\}|$. Assume, without loss
of generality that $(u,v)\in E_{i}$ but either
$({\mu^{-1}}(u),{\mu^{-1}}(v))\not\in E$ or $({\mu^{-1}}(u),{\mu^{-1}}(v))\in
E_{j}$ for $j\neq i$. Either way, it follows that a vertex not in
$\\{a_{u^{\prime},v^{\prime},i}:(u^{\prime},v^{\prime})\\!\in\\!E_{i}\\}$ is
mapped by $\mu^{\prime}$ to $a_{u,v,i}$, which means that Case 1 applies for
each such a tuple. Hence, if the number of vertices in the current case is
$n_{2}$, then $n_{1}\geq\gamma\cdot n_{2}$, and we get a contribution of at
least $\gamma\cdot n_{2}$ via Case 1.

Case 3:

Auxiliary vertices of the form $a_{u,v,i}$ that are mapped by $\mu^{\prime}$
to auxiliary vertices of the form $a_{u^{\prime},v^{\prime},i}$ for
$(u^{\prime}v^{\prime})\neq(u,v)$; that is,
$\mu^{\prime}(a_{u,v,i})\in\\{a_{u^{\prime},v^{\prime},i}:(u^{\prime},v^{\prime})\\!\in\\!E_{i}\setminus\\{(u,v)\\}\\}$.

For $u,v,u^{\prime},v^{\prime}$ and $i$ as above, if
$\mu^{\prime}(u)=u^{\prime}$ and $\mu^{\prime}(v)=v^{\prime}$, then an
auxiliary vertex that connects $u$ and $v$ in $G^{\prime}$ is mapped to an
auxiliary vertex that does not connects them in $\mu^{\prime}(G^{\prime})$
(but rather connects the vertices $u^{\prime}$ and $v^{\prime}$, whereas
either $u^{\prime}\neq u$ or $v^{\prime}\neq v$). So we get a contribution of
at least one unit to the difference between $G^{\prime}$ and
$\mu^{\prime}(G^{\prime})$ (i.e., the edge incident at either $u$ or $v$).
Hence, the contribution is proportional to the number of non-fixed-points of
the current type. Otherwise (i.e.,
$(\mu^{\prime}(u),\mu^{\prime}(v))\neq(u^{\prime},v^{\prime})$), we get a
vertex as in either Case 1 or Case 2, and get a proportional contribution
again.

Hence, the contribution of each of these cases to the difference between
$G^{\prime}$ and $\mu^{\prime}(G^{\prime})$ is proportional to the number of
vertices involved. Specifically, if there are $n_{i}$ vertices in Case $i$,
then we get a contribution-count of at least $\gamma\cdot\sum_{i\in[3]}n_{1}$,
where some of these contributions were possibly counted twice. The claim
follows.

###  4 The Three-Step Construction

In this section we present a different construction of bounded-degree graphs
that are robustly self-ordered. It uses totally different techniques than the
ones utilized in the construction presented in Section 3. Furthermore, the
current construction offers the flexibility of obtaining either graphs that
have small connected components (i.e., of logarithmic size) or graphs that are
highly connected (i.e., are expanders). Actually, one can obtain anything in-
between (i.e., $n$-vertex graphs that consist of $s(n)$-sized connected
components that are each an expander, for any $s(n)=\Omega((\log n)/\log\log
n)$). We mention that robustly self-ordered bounded-degree graphs with small
connected components are used in the proof of Theorem 5.2.

As stated in Section 1.1.2, the current construction proceeds in three steps.
First, in Section 4.1, we prove the existence of robustly self-ordered
bounded-degree graphs, and observe that such $\ell$-vertex graphs can actually
be found in ${\rm poly}(\ell!)$-time [sic]. Next, setting $\ell=\Omega((\log
n)/\log\log n)$, we use these graphs as part of $2\ell$-vertex connected
components in an $n$-vertex (robustly self-ordered bounded-degree) graph that
is constructed in ${\rm poly}(n)$-time (see Section 4.2). Lastly, in Section
4.3, we repeat this strategy using the graphs constructed in Section 4.2, and
obtain exponentially larger graphs that are locally constructible.

In addition, in Section 4.4, we show that the foregoing graphs can be locally
self-ordered. That is, given a vertex $v$ in any graph
$G^{\prime}=(V^{\prime},E^{\prime})$ that is isomorphic to the foregoing
$n$-vertex graph and oracle access to the incidence function of $G^{\prime}$,
we can find the vertex to which this unique isomorphism maps $v$ in ${\rm
poly}(\log n))$-time.

####  4.1 Existence

As stated above, we start with establishing the mere existence of bounded-
degree graphs that are robustly self-ordered.

###### Theorem 4.1

(robustly self-ordered graphs exist): For any sufficiently large constant $d$,
there exists a family $\\{G_{n}\\}_{n\in\mathbb{N}}$ of robustly self-ordered
$d$-regular graphs. Furthermore, these graphs are expanders.

Actually, it turns out that random $d$-regular graphs are robustly self-
ordered; see Theorem 6.1. Either way, given the existence of such $n$-vertex
graphs, they can actually be found in ${\rm poly}(n!)$-time, by an exhaustive
search. Specifically, for each of the possible $n^{dn/2}$ graphs, we check the
robust self-ordering condition by checking all $n!-1$ relevant permutation.
(The expansion condition can be checked similarly, by trying all
$(0.5+o(1))\cdot 2^{n}$ relevant subsets of $[n]$.)

The proof of Theorem 4.1 utilizes a simpler probabilistic argument than the
one used in the proof of Theorem 6.1. This argument (captured by Claim 4.1.1)
refers to the auxiliary model of edge-colored multi-graphs (see Definition
2.1) and is combined with a transformation of this model to the original model
of uncolored graphs (provided in Construction 2.3 and analyzed in Theorem
2.4). Indeed, the relative simplicity of Claim 4.1.1 is mainly due to using
the edge-colored model (see digest at the end of Section 6).

Proof: To facilitate the proof, we present the construction while referring to
the edge-colored model presented in Section 2. We shall then apply Theorem 2.4
and obtain a result for the original model (of uncolored simple graphs).

For $m=n/O(1)$, we shall consider $2m$-vertex multi-graphs that consists of
two $m$-vertex cycles, using a different color for the edges of each cycle,
that are connected by $d^{\prime}=O(1)$ random perfect matching, which are
also each assigned a different color. (Hence, we use $2+d^{\prime}$ colors in
total.) We shall show that (w.h.p.) a random multi-graph constructed in this
way is robustly self-ordered (in the colored sense). (Note that parallel
edges, if they exist, will be assigned different colors.) Specifically, we
consider a generic $2m$-vertex multi-graph that is determined by $d^{\prime}$
perfect matchings of $[m]$ with $\\{m+1,...,2m\\}$. Denoting this sequence of
perfect matchings by ${\overline{M}}=(M_{1},...,M_{d^{\prime}})$, we consider
the (edge-colored) multi-graph $G_{\overline{M}}([2m],E_{\overline{M}})$ given
by

$\displaystyle E_{\overline{M}}$ $\displaystyle=$ $\displaystyle C_{1}\cup
C_{2}\cup\bigcup_{j\in[d^{\prime}]}M_{j}$ where
$C_{1}=\\{\\{i,i+1\\}:i\in[m-1]\\}\;\cup\;\\{\\{m,1\\}\\}$ and
$C_{2}=\\{\\{m+i,m+i+1\\}:i\in[m-1]\\}\;\cup\;\\{\\{2m,m+1\\}\\}$

and a coloring $\chi$ in which the edges of $C_{j}$ are colored $j$ and the
edges of $M_{j}$ are colored $j+2$. (That is, for $i\in\\{1,2\\}$, the set
$C_{i}$ forms a cycle of the form $((i-1)m+1,(i-1)m+2,...,(i-1)m+m,(i-1)m+1)$
and its edges are colored $i$.) Note that the $d^{\prime}+1$ edges incident at
each vertex are assigned $d^{\prime}+1$ different colors.

###### Claim 4.1.1

(w.h.p., $G_{\overline{M}}$ is robustly self-ordered): For some constant
$\gamma>0$, with high probability over the choice of $\overline{M}$, the edge-
colored multi-graph $G_{\overline{M}}$ is $\gamma$-robustly self-ordered.
Furthermore, it is also an expander.

Proof: Consider an arbitrary permutation $\mu:[2m]\to[2m]$, and let
$t=|\\{i\\!\in\\![2m]\\!:\\!\mu(i)\neq i\\}|$. We shall show that, with
probability $1-\exp(-\Omega(dt\log m))$ over the choice of $\overline{M}$, the
difference between the colored versions of $G_{\overline{M}}$ and
$\mu(G_{\overline{M}})$ is $\Omega(t)$. Towards this end, we consider two
cases.

Case 1:

$|\\{i\in[m]:\mu(i)\not\in[m]\\}|>t/4$. Equivalently,
$|\\{i\in[2m]:{\lceil\mu(i)/m\rceil}\neq{\lceil i/m\rceil}\\}|>t/2$.

The vertices in the set $\\{i\in[m]:\mu(i)\not\in[m]\\}$ are mapped from the
first cycle to the second cycle, and so rather than having two incident edges
that are colored 1 they have two incident edges colored 2. Hence, each such
vertex contributes two units to the difference (between the colored versions
of $G_{\overline{M}}$ and $\mu(G_{\overline{M}})$), and the total contribution
is greater than $2\cdot(t/4)\cdot 2$, where the first factor of 2 accounts
also for vertices that are mapped from $C_{2}$ to $C_{1}$.

Case 2:

$|\\{i\in[m]:\mu(i)\not\in[m]\\}|\leq t/4$. Equivalently,
$|\\{i\in[2m]:{\lceil\mu(i)/m\rceil}\neq{\lceil i/m\rceil}\\}|\leq t/2$.

We focus on the non-fixed-points of $\mu$ that stay on their original cycle
(i.e., those not considered in Case 1). Let $A\stackrel{{\scriptstyle\rm
def}}{{=}}\\{i\\!\in\\![m]:\mu(i)\\!\neq\\!i\wedge\mu(i)\\!\in\\![m]\\}$ and
$B\stackrel{{\scriptstyle\rm
def}}{{=}}\\{i\\!\in\\!\\{m+1,....,2m\\}:\mu(i)\\!\neq\\!i\wedge\mu(i)\\!\in\\!\\{m+1,...,2m\\}\\}$.
By the case hypothesis, $|A|+|B|\geq t/2$, and we may assume (without loss of
generality) that $|A|\geq t/4$. As a warm-up, we first show that each element
of $A$ contributes a non-zero number of units to the difference (between the
colored versions of $G_{\overline{M}}$ and $\mu(G_{\overline{M}})$) with
probability $1-O(1/m)^{d^{\prime}}$, over the choice of $\overline{M}$.

To see this, let $\pi_{j}:[m]\to\\{m+1,...,2m\\}$ be the mapping used in the
$j^{\rm th}$ matching; that is,
$M_{j}=\\{\\{i,\pi_{j}(i)\\}:i\\!\in\\![m]\\}$, which means that $\pi_{j}(i)$
is the $j^{\rm th}$ match of $i$ in $G_{\overline{M}}$ (i.e., the vertex
matched to $i$ by $M_{j}$). Then, we consider the event that for some
$j\in[d^{\prime}]$, the $j^{\rm th}$ match of $i\in[m]$ in
$\mu(G_{\overline{M}})$ is different from the $j^{\rm th}$ match of $i$ in
$G_{\overline{M}}$, and note that when this event occurs $i$ contributes to
the difference (between the colored versions of $G_{\overline{M}}$ and
$\mu(G_{\overline{M}})$). Note that $x$ is the $j^{\rm th}$ match of $i$ in
$\mu(G_{\overline{M}})$ if and only if ${\mu^{-1}}(x)$ is the $j^{\rm th}$
match of ${\mu^{-1}}(i)$ in $G_{\overline{M}}$, which holds if and only if
${\mu^{-1}}(x)=\pi_{j}({\mu^{-1}}(i))$ (equiv.,
$x=\mu(\pi_{j}({\mu^{-1}}(i)))$). Hence, $i\in[m]$ contributes to the
difference if and only if for some $j$ it holds that
$\pi_{j}(i)\neq\mu(\pi_{j}({\mu^{-1}}(i)))$, because
$\pi_{j}(i)\neq\mu(\pi_{j}({\mu^{-1}}(i)))$ means that the edge
$\\{i,\pi_{j}(i)\\}$ is colored $j+2$ in $G_{\overline{M}}$ but is not colored
$j+2$ in $\mu(G_{\overline{M}})$ (since a different edge incident at $i$ in
$\mu(G_{\overline{M}})$ is colored $j+2$). Letting
${\overline{\pi}}=(\pi_{1},...,\pi_{d^{\prime}})$, the probability of the
complementary event (i.e., $i$ does not contribute to the difference) is given
by

$\displaystyle{\rm Pr}_{\overline{\pi}}\left[(\forall
j\\!\in\\![d^{\prime}])\;\;\pi_{j}(i)=\mu(\pi_{j}({\mu^{-1}}(i)))\right]$
$\displaystyle=$ $\displaystyle\prod_{j\in[d^{\prime}]}{\rm
Pr}_{\pi_{j}}\left[\pi_{j}(i)=\mu(\pi_{j}({\mu^{-1}}(i)))\right]$
$\displaystyle\leq$ $\displaystyle(m-1)^{-d^{\prime}},$

where the inequality uses the hypothesis that $\mu(i)\neq i$ and
$i,\mu(i)\\!\in\\![m]$; specifically, fixing the value of
$\pi_{j}({\mu^{-1}}(i))$, leaves $\pi_{j}(i)$ uniformly distributed in
$S\stackrel{{\scriptstyle\rm
def}}{{=}}\\{m+1,...,2m\\}\setminus\\{\pi_{j}({\mu^{-1}}(i))\\}$, which means
that ${\rm Pr}_{\pi_{j}}[\pi_{j}(i)\\!=\\!\mu(v)|v=\pi_{j}({\mu^{-1}}(i))]\leq
1/|S|$ (where equality holds if $\mu(v)\in S$).

The same argument generalises to any set $I\subseteq A$ such that
$I\cap\mu(I)=\emptyset$. In such a case, letting
$I=\\{i_{1},...,i_{t^{\prime}}\\}$, we get

$\displaystyle{\rm Pr}_{\overline{\pi}}\left[(\forall i\\!\in\\!I)(\forall
j\\!\in\\![d^{\prime}])\;\;\pi_{j}(i)=\mu(\pi_{j}({\mu^{-1}}(i)))\right]$
$\displaystyle=$
$\displaystyle\prod_{k\in[t^{\prime}]}\prod_{j\in[d^{\prime}]}{\rm
Pr}_{\pi_{j}}\left[\pi_{j}(i_{k})=\mu(\pi_{j}({\mu^{-1}}(i_{k})))\left|(\forall
k^{\prime}\\!\in\\![k-1])\;\pi_{j}(i_{k^{\prime}})=\mu(\pi_{j}({\mu^{-1}}(i_{k^{\prime}})))\right.\right]$
$\displaystyle\leq$ $\displaystyle(m-2t^{\prime}+1)^{-t^{\prime}d^{\prime}},$

where the inequality uses the hypothesis that $I\cap\mu(I)=\emptyset$;
specifically, for each $k\in[t^{\prime}]$, we use the fact that
$i_{k}\not\in\\{i_{1},...,i_{k-1},{\mu^{-1}}(i_{1}),...,{\mu^{-1}}(i_{k})\\}$.
Hence, fixing the values of $\pi_{j}(i_{k^{\prime}})$ for all
$k^{\prime}\in[k-1]$ and the values of $\pi_{j}({\mu^{-1}}(i_{k^{\prime}}))$
for all $k^{\prime}\in[k]$, and denoting these values by $u_{1},...,u_{k-1}$
and $v_{1},...,v_{k}$ respectively, leaves $\pi_{j}(i_{k})$ uniformly
distributed in $S\stackrel{{\scriptstyle\rm
def}}{{=}}\\{m+1,...,2m\\}\setminus\\{u_{1},...,u_{k-1},v_{1},...,v_{k}\\}$,
which means that ${\rm Pr}_{\pi_{j}}[\pi_{j}(i)\\!=\\!\mu(v_{k})|\mbox{\rm
foreging fixing}]\leq 1/|S|$ (where equality holds if $\mu(v_{k})\in S$).

Recalling that $|A|\geq t/4$ and $t\leq 2m$, we upper-bound the probability
(over the choice of $\overline{M}$) that $A$ contains a $t/8$-subset
$A^{\prime}$ such that $(\forall i\\!\in\\!A^{\prime})(\forall
j\\!\in\\![d^{\prime}])\;\pi_{j}(i)=\mu(\pi_{j}({\mu^{-1}}(i)))$, by taking a
union bound over all possible $A^{\prime}$ and using for each such
$A^{\prime}$ a subset $I\subset A^{\prime}$ such that $I\cap\mu(I)=\emptyset$.
(So we actually take a union bound over the $I$’s and derive a conclusion
regarding the $t/8$-subsets $A^{\prime}$.) Observing that
$|I|\geq|A^{\prime}|/2\geq t/16$, we conclude that, with probability at most
${t\choose{t/16}}\cdot(m/2)^{d^{\prime}\cdot
t/16}=\exp(-\Omega(d^{\prime}t\log m))$ over the choice of $\overline{M}$, the
set $A$ contains no $t/8$-subset $A^{\prime}$ as above. This means that, with
probability at most $\exp(-\Omega(d^{\prime}t\log m))$, less than $t/8$ of the
indices $i\in A$ contribute a non-zero number of units to the difference
(between the colored versions of $G_{\overline{M}}$ and
$\mu(G_{\overline{M}})$).

Hence, we have shown that, for every permutations $\mu:[2m]\to[2m]$, the
probability (over the choice of $\overline{M}$) that the size of the symmetric
difference between the colored versions of $G_{\overline{M}}$ and
$\mu(G_{\overline{M}})$ is smaller than $t/8$ is $\exp(-\Omega(d^{\prime}t\log
m))$, where $t$ is the number of non-fixed-points of $\mu$. Letting
$\gamma=1/8$ and taking a union bound over all (non-trivial) permutations
$\mu:[2m]\to[2m]$, we conclude that the probability, over the choice of
$\overline{M}$, that $G_{\overline{M}}$ is not $\gamma$-robustly self-ordered
is at most

$\displaystyle\sum_{t\in[2m]}{{2m}\choose t}\cdot\exp(-\Omega(d^{\prime}t\log
m))$ $\displaystyle=$
$\displaystyle\sum_{t\in[2m]}\exp(-\Omega((d^{\prime}-O(1))\cdot t\log m))$
$\displaystyle=$ $\displaystyle\exp(-\Omega((d^{\prime}-O(1))\cdot\log m)),$

and the claim follows (for any sufficiently large $d^{\prime}$), while
observing that, with very high probability, these multi-graphs are expanders.

Back to the non-colored version. We now convert the edge-colored multi-graphs
$G=G_{\overline{M}}$ that are $\gamma$-robustly self-ordered into standard
graphs $G^{\prime}$ that are robustly self-ordered in the original sense. This
is done by using Construction 2.3 (while relying on Theorem 2.4). Recall that
this transformation also preserves expansion. Actually, before invoking
Construction 2.3, we augment the multi-graph $G$ by adding a self-loop to each
vertex, and color all these self-loops using a special color. Combining Claim
4.1.1 and Theorem 2.4, the current theorem follows.

####  4.2 Constructions

Having established the existence of bounded-degree graphs that are robustly
self-ordered, we now turn to actually construct them. We shall use the fact
that the proof of existence yields a construction that runs in time that is
polynomial in the number of possible graphs. Specifically, for
$\ell=\frac{O(\log n)}{\log\log n}$, we shall construct $\ell$-vertex graphs
in ${\rm poly}(\ell^{\ell})$-time and use them in our construction of
$n$-vertex graphs, while noting that ${\rm poly}(\ell^{\ell})={\rm poly}(n)$.

###### Theorem 4.2

(constructing robustly self-ordered graphs): For any sufficiently large
constant $d$, there exists an efficiently constructable family
$\\{G_{n}\\}_{n\in\mathbb{N}}$ of robustly self-ordered graphs of maximum
degree $d$. That is, there exists a polynomial-time algorithm that on input
$1^{n}$ outputs the $n$-vertex graph $G_{n}=([n],E_{n})$. Furthermore, $G_{n}$
consists of connected components of size $\frac{O(\log n)}{\log\log n}=o(\log
n)$.

Note that the connected components of $G_{n}$ cannot be any smaller (than
$\frac{O(\log n)}{\log\log n}$). This is the case because an asymmetric
$n$-vertex bounded-degree graph, let alone a robustly self-ordered one, cannot
have connected components of size $\frac{o(\log n)}{\log\log n}$ (because the
number of $t$-vertex graphs of bounded-degree is $t^{O(t)}$).

Proof: The proof proceeds in two steps. We first use the existence of
$\ell$-vertex ($d^{\prime}$-regular) expander graphs that are robustly self-
ordered towards constructing a sequence of $m=\exp(\Omega(\ell\log\ell))$
bounded-degree $2\ell$-vertex graphs that are robustly self-ordered,
expanding, and far from being isomorphic to one another. We construct this
sequence of $2\ell$-vertex graphs in ${\rm poly}(m)$-time, using the fact that
$(\ell!)^{O(1)}={\rm poly}(m)$. In the second step, we show that the $(m\cdot
2\ell)$-vertex graph that consists of these $2\ell$-vertex graphs (as its
connected components) is robustly self-ordered. Note that this graph is
constructed in time that is polynomial in its size, since its size is
$\Omega(m)$, whereas it is constructed in ${\rm poly}(m)$-time.171717We
mention that a slightly different construction can be based on the fact that
random $\ell$-vertex ($d^{\prime}$-regular) graphs are robustly self-ordered
expanders (see Theorem 6.1). In this alternative construction we find a
sequence of $m$ such graphs that are pairwise far from being isomorphic to one
another. As further detailed in Remark 6.2, the analysis of the alternative
construction is somewhat easier than the analysis of the construction
presented below, but we need the current construction for the proof of Theorem
4.5.

Given a generic $n$, let $\ell=\frac{O(\log n)}{\log\log n}$, which implies
that $\ell^{\ell}={\rm poly}(n)$. By Theorem 4.1, for all sufficiently large
$d^{\prime}$, there exist $\ell$-vertex $d^{\prime}$-regular expander graphs
that are robustly self-ordered (with respect to the robustness parameter
$c^{\prime}$). Furthermore, we can find such a graph, denoted
$G^{\prime}_{\ell}$, in time ${\rm poly}(\ell^{\ell})={\rm poly}(n)$, by
scanning all $\ell$-vertex $d^{\prime}$-regular graphs and checking both the
expansion and the robustness (w.r.t parameter $c^{\prime}$) conditions for
each of them. Actually, for $d^{\prime\prime}=d^{\prime}+1$, we shall also
find an $\ell$-vertex $d^{\prime\prime}$-regular expander, denoted
$G^{\prime\prime}_{\ell}$, that is robustly self-ordered.

The construction of $G_{n}$. Using $G^{\prime}_{\ell}$ and
$G^{\prime\prime}_{\ell}$, we construct an $n$-vertex robustly self-ordered
graph, denoted $G_{n}$, that consists of $n/2\ell$ connected components that
are pairwise far from being isomorphic to one another. This is done by picking
$m=n/2\ell$ permutations, denoted $\pi_{1},...,\pi_{m}:[\ell]\to[\ell]$, that
are pairwise far-apart and constructing $2\ell$-vertex graphs such that the
$i^{\rm th}$ such graph consist of a copy of $G^{\prime}_{\ell}$ and a copy of
$G^{\prime\prime}_{\ell}$ that are connected by a matching as determined by
the permutation $\pi_{i}$. Specifically, for
$G^{\prime}_{\ell}=([\ell],E^{\prime}_{\ell})$ and
$G^{\prime\prime}_{\ell}=([\ell],E^{\prime\prime}_{\ell})$, the $i^{\rm th}$
connected component is isomorphic to a graph with the vertex set $[2\ell]$ and
the edge set

$E^{\prime}_{\ell}\;\cup\;\\{\\{\ell+u,\ell+v\\}:\\{u,v\\}\in
E^{\prime\prime}_{\ell}\\}\;\cup\;\\{\\{v,\ell+\pi_{i}(v)\\}:v\\!\in\\![\ell]\\}.$
(5)

(The first two sets correspond to the copies of $G^{\prime}_{\ell}$ and
$G^{\prime\prime}_{\ell}$, and the third set corresponds to the matching
between these copies. Note that the vertices in $[\ell]$ have degree
$d^{\prime}+1$, whereas vertices in $\\{\ell+1,...,2\ell\\}$ have degree
$d^{\prime\prime}+1\neq d^{\prime}+1$.)

To see that this construction can be carried out in ${\rm poly}(n)$-time, we
need to show that the sequence of $m$ pairwise far-apart permutations can be
determined in ${\rm poly}(n)$-time, let alone that such a sequence exists.
This is the case, because we can pick the permutation sequentially (one after
the other) by scanning the symmetric group on $[\ell]$ and relying on the fact
that for ($i<n$ and) any fixed sequence of permutations
$\pi_{1},...,\pi_{i-1}:[\ell]\to[\ell]$ it holds that a random permutation
$\pi_{i}$ is far-apart from each of the fixed $i-1$ permutations; that is,
${\rm
Pr}_{\pi_{i}}[|\\{v\in[\ell]:\pi_{i}(v)\neq\pi_{j}(v)\\}|=\Omega(\ell)]=1-o(1/n)$
for every $j\in[i-1]$.181818Specifically, for some
$\ell^{\prime}=\Omega(\ell)$, we upper-bound ${\rm
Pr}_{\pi}[|\\{v\in[\ell]:\pi(v)=v)\\}|\geq\ell-\ell^{\prime}]$, where
$\pi:[\ell]\to[\ell]$ is a random permutation. We do so by observing that the
number of permutations that have at least $\ell-\ell^{\prime}$ fixed-points is
at most
${\ell\choose{\ell^{\prime}}}\cdot(\ell^{\prime}!)=\frac{\ell!}{(\ell-\ell^{\prime})!}$,
whereas $(\ell-\ell^{\prime})!=\exp(\Omega(\ell\log\ell))=\omega(n)$ for any
$\ell^{\prime}$ such that $\ell-\ell^{\prime}=\Omega(\ell)$.

Towards proving that $G_{n}$ is robustly self-ordered. We now prove that the
resulting graph $G_{n}$, which consists of these $m$ connected components, is
$c$-robustly self-ordered, where $c$ is a universal constant (which is
independent of the generic $n$). For starters, let’s verify that $G_{n}$ is
self-ordered. We first note that any automorphism of $G_{n}$ must map the
verifices of copies of $G^{\prime}_{\ell}$ (resp., $G^{\prime\prime}_{\ell}$)
to vertices of copies of $G^{\prime}_{\ell}$ (resp.,
$G^{\prime\prime}_{\ell}$), since these are the only vertices of degree
$d^{\prime}+1$. The connectivity of these copies implies that the
automorophism must map each connected component to some connected component,
which determines the $m$ connected components. The self-ordered feature of
$G^{\prime}_{\ell}$ and $G^{\prime\prime}_{\ell}$ determines a unique ordering
on each copy, whereas the fact the permutations (i.e., $\pi_{i}$’s) are
different imposes that each connected component is mapped to itself (i.e., the
order of the connected components is preserved). Hence, the automorphism must
be trivial (and it follows that $G_{n}$ is self-ordered).

An analogous argument establishes the robust self-ordering of $G_{n}$, where
we use the hypothesis that $G^{\prime}_{\ell}$ and $G^{\prime\prime}_{\ell}$
are expanders (rather than merely connected), the choice of the $\pi_{i}$’s as
being far-apart (rather than merely different), and the robust self-ordering
of $G^{\prime}_{\ell}$ and $G^{\prime\prime}_{\ell}$ (rather than their mere
self-ordering) in order to establish the robust self-ordering of $G_{n}$.
Considering an arbitrary permutation $\mu:[n]\to[n]$, these stronger features
are used to establish a lower bound on the size of the symmetric difference
between $G_{n}$ and $\mu(G_{n})$ as follows:

  * •

The fact that $G^{\prime}_{\ell}$ is an expander implies that if $\mu$ splits
the vertices of a copy of $G^{\prime}_{\ell}$ such that $\ell^{\prime}$
vertices are mapped to copies that are different than the other
$\ell-\ell^{\prime}\geq\ell^{\prime}$ vertices, then this contributes
$\Omega(\ell^{\prime})$ units to the difference between $G_{n}$ and
$\mu(G_{n})$. Ditto for $G^{\prime\prime}_{\ell}$, whereas mapping a copy of
$G^{\prime}_{\ell}$ to a copy of $G^{\prime\prime}_{\ell}$ contributes
$\Omega(\ell)$ units (per the difference in the degrees).

  * •

The robust self-ordering of $G^{\prime}_{\ell}$ and $G^{\prime\prime}_{\ell}$
implies that if $\mu$ changes the index of vertices inside a component, then
this yields a proportional difference between $G_{n}$ and $\mu(G_{n})$.

  * •

The distance between the $\pi_{i}$’s (along with the aforementioned
robustness) implies that if $\mu$ changes the indices of the connected
components, then each such change contributes $\Omega(\ell)$ units to the
difference between $G_{n}$ and $\mu(G_{n})$.

The actual implementation of this sketch requires a careful accounting of the
various contributions. As a first step in this direction we provide a more
explicit description of $G_{n}$. We denote the set of vertices of the copy of
$G^{\prime}_{\ell}$ (resp., $G^{\prime\prime}_{\ell}$) in the $i^{\rm th}$
connected component of $G_{n}$ by $F_{i}=\\{2(i-1)\ell+j:j\in[\ell]\\}$
(resp., $S_{i}=\\{2(i-1)\ell+\ell+j:j\in[\ell]\\}$). Recall that $F_{i}$ and
$S_{i}$ are connected by the edge-set

$\left\\{\\{2(i-1)\ell+j,2(i-1)\ell+\ell+\pi_{i}(j)\\}:j\\!\in\\![\ell]\right\\}$
(6)

whereas the subgraph of $G_{n}$ induced by $F_{i}$ (resp., $S_{i}$) has the
edge-set
$\\{\\{2(i-1)\ell+u,2(i-1)+v\\}:\\{u,v\\}\\!\in\\!E^{\prime}_{\ell}\\}$
(resp.,
$\\{\\{2(i-1)\ell+\ell+u,2(i-1)+\ell+v\\}:\\{u,v\\}\\!\in\\!E^{\prime\prime}_{\ell}\\}$).
In addition, let $F=\bigcup_{i\in[m]}F_{i}$ (resp.,
$S=\bigcup_{i\in[m]}S_{i}$).

The actual proof (that $G_{n}$ is robustly self-ordered). Considering an
arbitrary permutation $\mu:[n]\to[n]$, we lower-bound the distance (i.e., size
of the symmetric difference) between $G_{n}$ and $\mu(G_{n})$ as a function of
the number of non-fixed-points under $\mu$ (i.e., the number of $v\in[n]$ such
that $\mu(v)\neq v$). We do so by considering the (average) contribution of
every non-fixed-point to the distance between $G_{n}$ and $\mu(G_{n})$ (i.e.,
number of pairs of vertices that form an edge in one graph but not in the
other). We may include the same contribution in few of the following (seven)
cases, but this only means that we are double-counting the contribution by a
constant factor.

Case 1:

Vertices $v\in F$ such that ${\mu^{-1}}(v)\in S$. Ditto for $v\in S$ such that
${\mu^{-1}}(v)\in F$.

Each such vertex contributes at least one unit to the distance (between
$G_{n}$ and $\mu(G)$) by virtue of $v$ having degree $d^{\prime}+1$ in $G_{n}$
and strictly higher degree in $\mu(G_{n})$, since vertices in $F$ have degree
$d^{\prime}+1$ (in $G_{n}$) whereas vertices in $S$ have higher degree (in
$G_{n}$).191919Note that $v$ neighbors $u$ in $\mu(G_{n})$ if and only if
${\mu^{-1}}(v)$ neighbors ${\mu^{-1}}(u)$ in $G_{n}$.

In light of Case 1, we may focus on vertices whose “type” is preserved by
${\mu^{-1}}$. Actually, it will be more convenient to consider the set of
vertices whose “type” is preserved by $\mu$; that is, the set
$\\{v\\!\in\\!F\\!:\\!\mu(v)\\!\in\\!F\\}\cup\\{v\\!\in\\!S\\!:\\!\mu(v)\\!\in\\!S\\}$.
Next, for each $i\in[m]$, we define $\mu^{\prime}(i)$ to be the index of the
connected component that takes the plurality of $\mu(F_{i})$; that is,
$\mu^{\prime}(i)\stackrel{{\scriptstyle\rm def}}{{=}}j$ if $|\\{v\in
F_{i}:\mu(v)\in F_{j}\\}|\geq|\\{v\in F_{i}:\mu(v)\in F_{k}\\}|$ for all
$k\in[m]$ (breaking ties arbitrarily).

Case 2:

Vertices $v\in F_{i}$ such that $\mu(v)\in F\setminus F_{\mu^{\prime}(i)}$.

For starters, suppose that
$|\\{v\\!\in\\!F_{i}\\!:\\!\mu(v)\\!\in\\!F_{\mu^{\prime}(i)}\\}|\geq\ell/2$;
that is, a majority of the vertices of $F_{i}$ are mapped by $\mu$ to
$F_{\mu^{\prime}(i)}$. In this case, by the expansion of $G^{\prime}_{\ell}$,
we get a contribution that is proportional to the size of the set
$F^{\prime}_{i}\stackrel{{\scriptstyle\rm
def}}{{=}}\\{v\\!\in\\!F_{i}\\!:\\!\mu(v)\\!\not\in\\!F_{\mu^{\prime}(i)}\\}$,
because there are $\Omega(|F^{\prime}_{i}|)$ edges betwen $F^{\prime}_{i}$ and
the rest of $F_{i}$ but there are no edges between $F^{\prime}_{i}$ and
$F_{i}\setminus F^{\prime}_{i}$ in $\mu(G_{n})$. In the general case, we have
to be more careful since expansion is guaranteed only for sets that have size
at most $\ell/2$. In such a case we use an adequate subset of
$F^{\prime}_{i}$. Details follow.

Let $J\subseteq[m]\setminus\\{\mu^{\prime}(i)\\}$ be maximal such that
$\sum_{j\in J}|\\{v\\!\in\\!F_{i}\\!:\\!\mu(v)\\!\in\\!F_{j}\\}|\leq\ell/2$,
and note that $F^{\prime}_{i}\stackrel{{\scriptstyle\rm
def}}{{=}}\bigcup_{j\in J}\\{v\\!\in\\!F_{i}\\!:\\!\mu(v)\\!\in\\!F_{j}\\}$
occupies at least one third of
$\\{v\\!\in\\!F_{i}\\!:\\!\mu(v)\\!\in\\!F\setminus F_{\mu^{\prime}(i)}\\}$.
Recall that the subgraph of $G_{n}$ induced by $F_{i}$ is an expander, and
consider the edges in $G_{n}$ that cross the cut between $F^{\prime}_{i}$ and
the rest of $F_{i}$. Then, this cut has $\Omega(|F^{\prime}_{i}|)$ edges in
$G_{n}$, but there are no edges between $F^{\prime}_{i}$ and $F_{i}\setminus
F^{\prime}_{i}$ in $\mu(G_{n})$, because
${\mu^{-1}}(F^{\prime}_{i})\subseteq\bigcup_{j\in J}F_{j}$ and
${\mu^{-1}}(F_{i}\setminus F^{\prime}_{i})\subseteq\bigcup_{j\in[m]\setminus
J}F_{j}$ are not connected in $G_{n}$. Hence, the total contribution of the
vertices in $\\{v\\!\in\\!F_{i}\\!:\\!\mu(v)\\!\in\\!F\setminus
F_{\mu^{\prime}(i)}\\}$ to the distance (between $G_{n}$ and $\mu(G)$) is
$\Omega(|F^{\prime}_{i}|)$, which is proportional to their number (i.e., is
$\Omega(|\\{v\\!\in\\!F_{i}\\!:\\!\mu(v)\\!\in\\!F\setminus
F_{\mu^{\prime}(i)}\\}|)$).

Defining $\mu^{\prime\prime}(i)$ in an analogous manner with respect to
$\mu(S_{i})$, we get an analogous contribution by the expander induced by
$S_{i}$. Specifically, for each $i\in[m]$, we define $\mu^{\prime\prime}(i)$
to be the index of the connected component that takes the plurality of
$\mu(S_{i})$; that is, $\mu^{\prime\prime}(i)\stackrel{{\scriptstyle\rm
def}}{{=}}j$ if
$|\\{v\\!\in\\!S_{i}\\!:\\!\mu(v)\\!\in\\!S_{j}\\}|\geq|\\{v\\!\in\\!S_{i}\\!:\\!\mu(v)\\!\in\\!S_{k}\\}|$
for all $k\in[m]$ (breaking ties arbitrarily).

Case 3:

Vertices $v\in S_{i}$ such that $\mu(v)\in S\setminus
S_{\mu^{\prime\prime}(i)}$.

Here we get a contribution of
$\Omega(|\\{v\\!\in\\!S_{i}\\!:\\!\mu(v)\\!\in\\!S\setminus
S_{\mu^{\prime\prime}(i)}\\}|)$, where the analysis is analogous to Case 2.

Recall that if $v\in F_{i}$ then it holds that $v=2(i-1)\ell+j$ for some
$j\in[\ell]$, and that (in $G_{n}$) vertex $v$ has a unique neighbor in $S$,
which is $2(i-1)\ell+\ell+\pi_{i}(j)\in S_{i}$. It will be convinient to
denote this neighbor by $\phi_{i}(v)$; that is, for $v\in F_{i}$ such that
$v=2(i-1)\ell+j$, we have $\phi_{i}(v)=2(i-1)\ell+\ell+\pi_{i}(j)\in S_{i}$.
The next two cases refer to vertices that are mapped by $\mu$ according to the
plurality vote (e.g., $v\in F_{i}$ is mapped to $\mu(v)\in
F_{\mu^{\prime}(i)}$), but their match is not mapped accordingly (i.e.,
$\phi_{i}(v)\in S_{i}$ is not mapped to $S_{\mu^{\prime}(i)}$).

Case 4:

Vertices $v\in F_{i}$ such that $\mu(v)\in F_{\mu^{\prime}(i)}$ but
$\mu(\phi_{i}(v))\not\in S_{\mu^{\prime}(i)}$.

(Note that the condition $v\in F_{i}$ and $\mu(v)\in F_{\pi^{\prime}(i)}$
means that vertex $v$ is not covered in Case 2. If
$\mu^{\prime\prime}(i)=\mu^{\prime}(i)$, then $\mu(\phi_{i}(v))\not\in
S_{\mu^{\prime}(i)}$ means that $v$ is covered in Case 3, since
$\phi_{i}(v)\in S_{i}$. Hence, the current case is of interest only when
$\mu^{\prime\prime}(i)\neq\mu^{\prime}(i)$. In particular, it is of interest
when referring to vertices in the $i^{\rm th}$ connected component of $G_{n}$
that reside in the copies of $G^{\prime}_{\ell}$ and $G^{\prime\prime}_{\ell}$
and are mapped according to the plurality votes of these copies, whereas these
two plurality votes are inconsistent.)

We focus on the case that a vast majority of the vertices in both $F_{i}$ and
$S_{i}$ are mapped according to the plurality votes (i.e., $\mu^{\prime}(i)$
and $\mu^{\prime\prime}(i)$), since the complementary cases are covered by
Cases 2 and 3, respectively. Specifically, if either
$|\\{v\\!\in\\!F_{i}\\!:\\!\mu(v)\\!\in\\![n]\setminus
F_{\mu^{\prime}(i)}\\}|>\ell/3$ or
$|\\{u\\!\in\\!S_{i}\\!:\\!\mu(u)\\!\in\\![n]\setminus
S_{\mu^{\prime\prime}(i)}\\}|>\ell/3$, then we get a contribution of
$\Omega(\ell)$ either by Cases 1&2 or by Cases 1&3\. Otherwise, it follows
that

${|\\{v\\!\in\\!F_{i}\\!:\\!\mu(v)\\!\in\\!F_{\mu^{\prime}(i)}\;\wedge\;\mu(\phi_{i}(v))\\!\in\\!S_{\mu^{\prime\prime}(i)}\\}|}\geq\ell-2\cdot\ell/3$

which implies that, if $\mu^{\prime}(i)\neq\mu^{\prime\prime}(i)$, then the
$i^{\rm th}$ connected component of $G_{n}$ contributes $\ell/3$ units to the
difference (between $G_{n}$ and $\mu(G_{n})$), since $v$ and $\phi_{i}(v)$ are
connected in $G_{n}$, but $\mu(v)\in F_{\mu^{\prime}(i)}$ and
$\mu(\phi_{i}(v))\in S_{\mu^{\prime\prime}(i)}$ reside in different connected
components of $\mu(G_{n})$. (That is, the contribution is due to vertices $v$
of $F_{i}$ that are mapped by $\mu$ to $F_{\mu^{\prime}(i)}$, while the
corresponding vertices $\phi_{i}(v)$ of $S_{i}$ (which are connected to them
in $G_{n}$) are mapped by $\mu$ to $S_{\mu^{\prime\prime}(i)}\subset
S\setminus S_{\mu^{\prime}(i)}$, whereas $F_{\mu^{\prime}(i)}$ and
$S_{\mu^{\prime\prime}(i)}$ are not connected in $G_{n}$, assuming
$\mu^{\prime}(i)\neq\mu^{\prime\prime}(i)$.)

To conclude: The contribution of the vertices of Case 4 (to the difference
between $G_{n}$ and $\mu(G_{n})$) is proportional to the number of these
vertices (where this contribution might have been counted already in Cases 1,
2 and 3).

Case 5:

Vertices $v\in F_{i}$ such that $\mu(v)\not\in F_{\mu^{\prime\prime}(i)}$ but
$\mu(\phi_{i}(v))\in S_{\mu^{\prime\prime}(i)}$.

(Equiv., vertices $v\in S_{i}$ such that $\mu(v)\in S_{\mu^{\prime\prime}(i)}$
but $\mu(\phi_{i}^{-1}(v))\not\in F_{\mu^{\prime\prime}(i)}$.)

Analogously to Case 4, the contribution of these vertices is proportional to
their number. (Analogously, this augments Case 2 only in case
$\mu^{\prime\prime}(i)\neq\mu^{\prime}(i)$.)

In light of Cases 2–5, we may focus on indices $i\in[m]$ such that
$\mu^{\prime}(i)=\mu^{\prime\prime}(i)$ and on vertices in $i^{\rm th}$
connected component that are mapped by $\mu$ to the $\mu^{\prime}(i)^{\rm th}$
connected component (and the same ”type” per Case 1). The following case
refers to such vertices that do not maintain their position in this connected
component.

Case 6:

Vertices $v\\!=\\!2(i-1)\ell+j\in F_{i}$ such that $\mu(v)\in
F_{\mu^{\prime}(i)}\setminus\\{2(\mu^{\prime}(i)-1)\ell+j\\}$.

Ditto for $v\\!=\\!2(i-1)\ell+\ell+j\in S_{i}$ such that $\mu(v)\in
S_{\mu^{\prime\prime}(i)}\setminus\\{2(\mu^{\prime\prime}(i)-1)\ell+\ell+j\\}$.

(This case refers to vertices in $F_{i}$ that are mapped to
$F_{\mu^{\prime}(i)}$ but do not maintain their index in the relevant copy of
$G^{\prime}_{\ell}$; indeed, $v\\!=\\!2(i-1)\ell+j$ is the $j^{\rm th}$ vertex
of $F_{i}$, but it is mapped by $\mu$ to the $k^{\rm th}$ vertex of
$F_{\mu^{\prime}(i)}$ (i.e., $\mu(v)\\!=\\!2(\mu^{\prime}(i)-1)\ell+k$) such
that $k\neq j$.)

Fixing $i$, let $C\stackrel{{\scriptstyle\rm
def}}{{=}}\\{v\\!=\\!2(i-1)\ell+j\in F_{i}:\mu(v)\in
F_{\mu^{\prime}(i)}\setminus\\{2(\mu^{\prime}(i)-1)\ell+j\\}\\}$ denote the
set of vertices considered in this case, and $D=\\{v\in F_{i}:\mu(v)\not\in
F_{\mu^{\prime}(i)}\\}$ denote the set of vertices that we are going to
discount for. As a warm-up, consider first the case that $D=\emptyset$. In
this case, by the robust self-ordering of $G^{\prime}_{\ell}$, the
contribution of the vertices in $C$ to the difference between $G_{n}$ and
$\mu(G_{n})$ is $\Omega(|C|)$.

In the general case (i.e., where $D$ may not be empty), we get a contribution
of $\Omega(|C|)-d^{\prime}\cdot|D|$, where the second term compensates for the
fact that the vertices of $D$ were moved outside of this copy of
$G^{\prime}_{\ell}$ and replaced by different vertices that may have different
incidences. Letting $c^{\prime}$ be the constant hidden in the
$\Omega$-notation, we get a contribution of at least
$c^{\prime}\cdot|D|-d^{\prime}\cdot|D|$, which is at least
$c^{\prime}\cdot|C|/2$ if $|D|\leq c^{\prime}\cdot|C|/2d^{\prime}$. On the
other hand, if $|D|>c^{\prime}\cdot|C|/2d^{\prime}$, then we get a
contribution of $\Omega(|D|)=\Omega(|C|)$ by Cases 1–2.

Hence, in both sub-cases we have a contribution of $\Omega(|C|)$ to the
difference between $G_{n}$ and $\mu(G_{n})$.

The same analysis applies to $\\{v\\!=\\!2(i-1)\ell+\ell+j\in S_{i}:\mu(v)\in
S_{\mu^{\prime\prime}(i)}\setminus\\{2(\mu^{\prime\prime}(i)-1)\ell+\ell+j\\}\\}$,
where we use the robust self-ordering of $G^{\prime\prime}_{\ell}$ and Cases
1&3\.

Lastly, we consider vertices that do not fall into any of the prior cases.
Such vertices maintain their type, are mapped with the plurality vote of their
connected component, which is consistent among its two parts (i.e.,
$\mu^{\prime}$ and $\mu^{\prime\prime}$), and maintain their position in that
component. Hence, the hypothesis that they are not fixed-points of $\mu$ can
only be attributed to the fact that these vertices are mapped to a connected
component with a different index.

Case 7:

Vertices $v\in F_{i}$ such that both $\mu(v)\in F_{\mu^{\prime}(i)}\setminus
F_{i}$ and $\mu(\phi_{i}(v))\in S_{\mu^{\prime\prime}(i)}\setminus S_{i}$
hold.

(We may assume that $\mu^{\prime}(i)\neq i$ and $\mu^{\prime\prime}(i)\neq i$,
since otherwise this set is empty. We may also assume that
$\mu^{\prime}(i)=\mu^{\prime\prime}(i)$, since the complementary case was
covered by Cases 4 and 5. Hence, we focus on pairs of vertices that are
matched in the $i^{\rm th}$ connected component of $G_{n}$ and are mapped by
$\mu$ to the $k^{\rm th}$ component of $G_{n}$ such that $k\neq i$.)

For every $i\neq k$, let
$\Delta_{i,k}=\\{j\in[\ell]:\pi_{i}(j)\neq\pi_{k}(j)\\}$ be the sets on which
$\pi_{i}$ and $\pi_{k}$ differ. (Note that if for every $v=2(i-1)\ell+j\in
F_{i}$ it holds that $\mu(v)=2(k-1)\ell+j$ and
$\mu(\phi_{i}(v))=2(k-1)\ell+\pi_{i}(j)$ (equiv.,
$\mu(2(i-1)\ell+\ell+\pi_{i}(j))=2(k-1)\ell+\pi_{i}(j)$), then we get a
contribution of $|\Delta_{i,k}|$ to the difference between $G_{n}$ and
$\mu(G_{n})$.)

Fixing $i$, let $D=D_{1}\cup D_{2}$ such that

$\displaystyle D_{1}$ $\displaystyle=$ $\displaystyle\\{v\in
F_{i}:\mu(v)\not\in F_{\mu^{\prime}(i)}\;\vee\;\mu(v+\ell)\not\in
S_{\mu^{\prime\prime}(i)}\\}$ $\displaystyle D_{2}$ $\displaystyle=$
$\displaystyle\left\\{v\\!=\\!2(i-1)\ell+j\in
F_{i}:\begin{array}[]{l}\mu(v)\in
F_{\mu^{\prime}(i)}\setminus\\{2(\mu^{\prime}(i)-1)\ell+j\\}\\\
\vee\;\;\mu(\phi_{i}(v))\in
S_{\mu^{\prime\prime}(i)}\setminus\\{2(\mu^{\prime\prime}(i)-1)\ell+\ell+\pi_{i}(j)\\}\end{array}\right\\}$

(Recall that $\phi_{i}(2(i-1)\ell+j)=2(i-1)\ell+\ell+\pi_{i}(j)$. The set
$D_{1}$ accounts for the vertices covered in Cases 2&3, whereas $D_{2}$
accounts for the vertices covered in (the two sub-cases of) Case 6.)

As a warm-up, consider first the case that $D=\emptyset$. In this case,
assuming $\mu^{\prime}(i)=\mu^{\prime\prime}(i)\neq i$, we get a contribution
of $|\Delta_{i,\mu^{\prime}(i)}|=\Omega(\ell)$ (to the difference between
$G_{n}$ and $\mu(G_{n})$). This contribution is due to the difference in the
edges that match $F_{\mu^{\prime}(i)}$ and $S_{\mu^{\prime}(i)}$ in $G_{n}$
and the edges that match $F_{i}$ and $S_{i}$ in $G_{n}$, where
$|\Delta_{i,\mu^{\prime}(i)}|=\Omega(\ell)$ is due to the fact that the
permutations (i.e., $\pi_{k}$’s) are far-apart. The hypothesis
$D_{1}=\emptyset$ means that all vertices of $F_{i}$ (resp., of $S_{i}$) are
mapped to $F_{\mu^{\prime}(i)}$ (resp., to
$S_{\mu^{\prime\prime}(i)}=S_{\mu^{\prime}(i)}$), whereas $D_{2}=\emptyset$
means that these vertices preserves their order within the two parts of the
connected component.

The general case (i.e., where $D$ may not be empty) requires a bit more care.
Suppose that the $\pi_{k}$’s are $\gamma$-apart; that is,
$|\Delta_{k^{\prime},k}|>\gamma\cdot\ell$ for every $k^{\prime}\neq k$. We
focus on the case that a vast majority of the vertices in both $F_{i}$ and
$S_{i}$ are mapped according to the plurality votes (i.e., $\mu^{\prime}(i)$
and $\mu^{\prime\prime}(i)$), since the complementary cases are covered by
Cases 2 and 3, respectively. Specifically, if $|D_{1}|>\gamma\ell/3$, then we
get a contribution of $\Omega(\ell)$ by either Case 2 or Case 3. Likewise, if