A graph $G$ is called {\em 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 {\em 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,
on {\em pairs} of vertices of the original graph, is expanding. In this case the original graph is
(not only robustly self-ordered but) also expanding.
The second construction proceeds in three steps: It boosts the mere existence of robustly self-ordered graphs,
which provides explicit graphs of sublogarithmic size, to an efficient construction of polynomial-size graphs,
and then, repeating it again, to exponential-size(robustly self-ordered) graphs that are locally constructible. This construction can yield robustly self-ordered graphs that are either expanders or highly disconnected,
having logarithmic size 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 actually show two reductions, one simpler than the other but yielding a less efficient construction when combined with the known constructions of extractors.

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.

We retract the claims made in our initial posting 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). The source of trouble is a fundamental flaw in the proof of Lemma 9.7 (in the original version), which may as well be wrong.
Hence, the original Section 9 was omitted, except that the original Section 9.3 was retained as a new Section 8.3.
The original Section 8 appears as Section 8.0 and 8.1, and Section 8.2 is new.

A graph $G$ is called {\em 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 {\em 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$.

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, on {\em pairs|}\/ of vertices of the original graph, is expanding.
In this case the original graph is (not only robustly self-ordered but) also expanding.
The second construction proceeds in three steps: It boosts the mere existence of robustly self-ordered graphs,
which provides explicit graphs of sublogarithmic size, to an efficient construction of polynomial-size graphs,
and then, repeating it again, to exponential-size(robustly self-ordered) graphs that are locally constructible.
This construction can yield robustly self-ordered graphs that are either expanders or highly disconnected, having logarithmic size 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 give an explicit construction.
This turns out to require very different tools, and the definition and constructions of new pseudo-random objects.
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 an additional natural feature.
Next, we reduce the construction of such non-malleable two-source extractors to the construction of ``relocation-detecting'' codes. Loosely speaking, in such code permuting arbitrarily the coordinates of a random codeword yields a string that is far any other codeword. We conclude by showing how to construct relocation-detecting codes (of various types, including ones with constant rate).

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 complexity of testing and tolerant testing of graph properties in the bounded-degree graph model.

Correcting a couple of minor things and adding a brief discussion of our follow-up work (TR20-160).

A graph $G$ is called {\em 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 {\em 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$.

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, on {\em pairs|}\/ of vertices of the original graph, is expanding.
In this case the original graph is (not only robustly self-ordered but) also expanding.
The second construction proceeds in three steps: It boosts the mere existence of robustly self-ordered graphs,
which provides explicit graphs of sublogarithmic size, to an efficient construction of polynomial-size graphs,
and then, repeating it again, to exponential-size(robustly self-ordered) graphs that are locally constructible.
This construction can yield robustly self-ordered graphs that are either expanders or highly disconnected, having logarithmic size 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 give an explicit construction.
This turns out to require very different tools, and the definition and constructions of new pseudo-random objects.
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 an additional natural feature.
Next, we reduce the construction of such non-malleable two-source extractors to the construction of ``relocation-detecting'' codes. Loosely speaking, in such code permuting arbitrarily the coordinates of a random codeword yields a string that is far any other codeword. We conclude by showing how to construct relocation-detecting codes (of various types, including ones with constant rate).

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 complexity of testing and tolerant testing of graph properties in the bounded-degree graph model.