DefinitionsLet $\epsilon > 0$ and let $d$, $r$, and $g$ be positive integers (with $g > 2r+1$).Let $G = (V,E)$ be a simple, $d$-regular, undirected, finite graph with girth at least $g$.Let $\le$ be a total order on $V$.For each $v \in V$, let $V_v \subseteq V$ consist of the nodes that are within distance $r$ from $v$ in $G$ (the shortest path from $v$ to any $u \in V_v$ has at most $r$ edges), and let $G_v$ be the subgraph of $G$ induced by $V_v$. Recall that we assumed that $G$ has a high girth; hence $G_v$ is a tree. Let $\le_v$ be the restriction of $\le$ to $V_v$.We say that an edge $\{u,v\} \in E$ is good if $(G_u,\le_u)$ and $(G_v,\le_v)$ are isomorphic. That is, there is a bijection $f\colon V_u \to V_v$ that preserves adjacencies ( $\{x,y\} \in E$ iff $\{f(x),f(y)\} \in E$ ) and order ($x \le y$ iff $f(x) \le f(y)$). Otherwise an edge is bad.We say that $(G,\le)$ is $\epsilon$-good if there are at least $(1-\epsilon)|E|$ good edges.QuestionLet $d = 4$. Does there exist an $\epsilon$-good pair $(G,\le)$ for any $\epsilon > 0$ and any $r$ and $g$ (with $r \ll g$)?Remarks:I would like to know the answer for a general $d$, but $d = 4$ is the first non-trivial case.The size of $G$ does not matter, as long as it is finite. I do not need a construction of $G$; mere existence or non-existence is sufficient.ExamplesIf $d = 2$, the answer is yes. We can simply take a sufficiently long cycle, and order the nodes along the cycle. There are some bad edges near the edge that joins the largest and the smallest node, but all other edges are good: for almost all nodes $v$, the pair $(G_v,\le_v)$ is just a path with $2r+1$ nodes in an increasing order.If $r = 0$, the answer is yes. Just take a regular high-girth graph.If $g$ is sufficiently small, the answer is yes for any even $d$. Just take a $(d/2)$-dimensional grid graph (with the boundaries wrapped around to make it $d$-regular), and order the nodes lexicographically by their coordinates. Again we have some bad edges near the boundaries of the grid, but we can make the number of bad edges arbitrarily small.If $G$ does not need to be finite, the answer is yes for any even $d$. A regular infinite tree has a total order such that all edges are good.If $d$ is odd and $r$ is sufficiently large, the answer is no. In essence, Naor & Stockmeyer (1995) show that every node is incident to at least one non-good edge.Background(This section can be safely skipped.)The question is related to the foundations of distributed computing, and in particular to local algorithms.What we would like to understand is the following: in which situations the existence of a total order helps with local symmetry breaking in a distributed system. Intuitively, each node $v$ of $G$ has to produce an output that is a function of $(G_v,\le_v)$, i.e., a function of the local neighbourhood of $v$. If an edge $e = \{u,v\}$ is bad, there is some local symmetry-breaking information available near $e$, and nodes $u$ and $v$ may produce different outputs; if the edge is good, then nodes $u$ and $v$ are locally indistinguishable and they have to produce the same output.For many classical graph problems it is known that a total order does not help (much weaker relations provide essentially the same amount of symmetry-breaking information), but some cases are still open  and a general result that covers the case of all high-girth graphs could be a breakthrough.This might be a win-win question: regardless of the answer, we learn something new. If the answer is yes, we might be able to derive new, stronger lower-bound results; if the answer is no, we might be able to design faster algorithms that exploit the local symmetry-breaking information that is available in any $(G,\le)$.Of course in the real world we do not have a total order on $V$; we have something more: each node $v \in V$ has a unique label $\ell(v) \in \mathbb{N}$. But bridging the gap between a total order and unique labels is usually more straightforward; often a Ramsey-like argument shows that (in the worst case) the labels do not provide any information that is not available in a total order.
Regular high-girth graph with a locally uniform total order on nodes
graph theory;co.combinatorics;dc.distributed comp
Yes, such $(G,\le)$ pairs exist for any $\epsilon > 0$, any $r$, any $g$, and any even $d$.For details, see arXiv:1201.6675.