Highly arc-transitive digraphs -- structure and counterexamples (Q1677569): Difference between revisions

Unlike the case of connected finite digraphs, where outside the oriented cycles the \(s\)-arc-transitivity is limited to \( s \leq 8 \), families of infinite digraphs which are \(s\)-arc-transitive for all \( s \geq 0 \) exist in abundance. Nevertheless, constructions of such families are often quite involved; with the proof of the \(s\)-arc-transitivity of the resulting graphs, for every \(s \geq 0 \), `encoded' in the construction from its very beginning. The existence of conjectures assuming various limits on the structure of these infinite digraphs is therefore not surprising, even though some of them are proven false with the introduction of new, more imaginative, constructions. This is what happens in the present article, which introduces a number of constructions leading to counterexamples to conjectures of this type. In their attempts to classify these highly symmetric infinite digraphs, called highly arc-transitive digraphs, mathematicians divide the families according to their number of ends or with regard to their reachability properties. Two arcs in an infinite digraph are said to be mutually reachable if there exists an orientation alternating path starting from one and ending in the other. In case of arc-transitive graphs, all components induced by the classes of the equivalence relation of reachability are isomorphic, and the non-existence of locally finite highly arc-transitive digraphs with a single equivalence class under the relation of reachability has been conjectured; based on a number of negative results for specific parameters. The conjecture is proved wrong via a construction of a single-reachability-class infinite locally finite highly arc-transitive digraph of an in- and out-degree \(d\) for every composite \( d \geq 4 \). Interestingly, these are all the degrees for which the non-existence of such graphs had not been previously proved. The rest of the paper is devoted to two-ended highly arc-transitive digraphs. If we let \(R(D)\) denote the digraph induced by a single reachability component of the digraph \(D\), another conjecture assumed the non-existence of connected highly arc-transitive digraphs admitting a homomorphism onto an infinite path with finite vertex pre-images for which \(R(D)\) does not form a complete bipartite digraph. This again is proved false via a number of constructions, and the situation is shown quite a bit more complicated. A general construction which yields all two-ended highly arc-transitive graphs is introduced; the construction however also produces digraphs which are not highly arc-transitive.