We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph.

A *local self-ordering* procedure for a graph $G$
is given oracle access to an arbitrary isomorphic copy of $G$,
denoted $G'$, and a vertex $v$ in $G'$,
and is required to identify the name (or location) of $v$ in $G$,
while making few (i.e., polylogarithmically many) queries to $G'$.
A graph $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$ and to the maximal degree of $G$;
that is, any permutation of the vertices that displaces $t$
vertices must ``displace'' $\Omega(t\cdot d)$ edges,
where $d$ is the maximal degree of the graph.

We consider the relation between these two notions in two regimes: The bounded-degree graph regime, where oracle access to a graph means oracle access to its incidence function, and the dense graph regime, where oracle access to the graph means access to its adjacency predicate.

We show that, *in the bounded-degree regime*,
robustly self-ordering and local self-ordering are almost orthogonal;
that is, even extremely strong versions of one notion
do not imply very weak versions of the other notion.
Specifically, we present very efficient local self-ordering procedures
for graphs that possess derangements that are almost automorphisms
(i.e., a single incidence is violated).
One the other hand, we show robustly self-ordered graphs having
no local self-ordering procedures even when allowing a number
of queries that is a square root of the graph's size.

*In the dense graph regime*, local self-ordering procedures
are shown to yield a quantitatively weaker version of
the robust self-ordering condition, in which the said
proportion is off by a factor that is related to the query
complexity of the local self-ordering procedure.
Furthermore, we show that this quantitatively loss is inherent.
On the other hand,
we show how to transform any robustly self-ordered graph
into one having a local self-ordering procedure,
while preserving the robustness condition.
Combined with prior work, this yields explicit constructions
of graphs that are both robustly and locally self-ordered,
and an application to property testing.

- First version posted: March 2021.
- Revisions: June 2022 (major), December 2022 (removing Prop 3.4).

Back to either Oded Goldreich's homepage or general list of papers.