4
$\begingroup$

To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by removing $(x,z)$ from the arc-set and adding both $(x,y)$ and $(y,z)$. This is the definition in [BJG2009; page 10]; intuitively, we add a vertex $y$ different from all existing vertices in the "middle" of our arrow, and then give it an arrow-"head" that is pointed in the same direction as the other "head". While given any directed graph $G=(V,E)$ when I say an automorphism of $G$ what I am referring to is those permutations in a subgroup $\text{Aut}(G)\subseteq \text{Sym}(V)$ that is given as follows:

           $\text{Aut}(G)=\left\{\sigma\in \text{Sym}(V):\forall x,y\in V\left[(x,y)\in E\iff (\sigma(x),\sigma(y))\in E\right]\right\}$

With that said, after observing different ways in which automorphisms of digraphs permute certain subgraphs I've noticed a number of relationships between homeomorphisms and automorphisms, for instance if $G$ is a finite(*) directed acyclic graph, then all of the orbits of the action $\text{Aut}(R)$ on the vertex-set $V$ must be anti-chains of the poset $(V,E^{*})$ where the kleene star $*$ in the exponent of $E$ denotes its transitive/reflexive closure. Further from here if we call a vertex $v\in V$ "thin" iff we have $\text{deg}^{+}(v)=\text{deg}^{-}(v)=1$ while also referring to any path $P\subseteq G$ as a "thin path" iff every non source/sink vertex of $P$ is a thin vertex in $G$, then every automorphism of $G$ can be described exactly by which maximal thin paths of like length it permutes in $G$. I.e., for each $\ell\in\omega$, there is a permutation action of $\mathrm{Aut}(G)$ on the set $\mathsf{Thin}_\ell(G)$ of all thin directed length-$\ell$-paths in $G$. Where from here if we subdivide a single arrow in each of the maximal thin paths of some fixed length in $G$ it seems the order of the newly formed automorphism group is the same order as $\text{Aut}(G)$, in fact I'm pretty sure not only is this true but so are a number of other identities similar to this, for example here are two other propositions I'm confident to state (though I haven't formally proved):

  1. Any finite(**) digraph is homeomorphic to a digraph which has a trivial automorphism group.
  2. Two directed acyclic graphs are isomorphic to each other iff their barycentric subdivisions are isomorphic. Or more generally iff $\forall n\in \mathbb{N}$ their $n^{\text{th}}$ barycentric subdivisions are isomorphic.

With that in mind, are there other propositions of this kind that relate the automorphism groups of homeomorphic digraphs with one another, or equivalently, relate their isomorphism classes? Also if anyone could point me to some writings that make such connections, that would be helpful as well.

${}$_______________________________________________________________________________

(*)The following statement is obviously false for infinite digraphs.

(**)Without assuming finiteness, this is false: the two-way infinite directed path (i.e., the digraph $(\mathbb{Z},<)$) has the property that any subdivision still has the same, and hence nontrivial, automorphism group.

[BJG2009] Jørgen Bang-Jensen, Gregory Gutin, Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics, Second Edition, 2009, ISBN-13: 978-0857290410

${}$_______________________________________________________________________________

Update: Identities $1$ and $2$ as well as the comments about the order of $\text{Aut}(R)$ that I previously alluded to are in fact true for any finite directed graph. Irregardless though, I am still looking for reading material and or similar identities/formula that may shed additional light on the connections between homeomorphy and isomorphy for directed graphs.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ @Peter Heinig Sorry, I should have clarified the digraphs are finite. Clearly for $1$ you could take a double-ray digraph $D$ and then every subdivision of $D$ is isomorphic to $D$. However I'm quite sure $1$ and $2$ hold for finite digraphs. Basically the intuition for $1$ is any automorphism of a finite DAG can be characterized by which maximal thin paths it interchanges. So now if you take subdivisions of the maximal thin paths, such that no two are of the same length, then this means every automorphism is incapable of swapping any two maximal paths, leaving only the identity. $\endgroup$
    – Ethan Splaver
    Commented Mar 16, 2018 at 11:23
  • $\begingroup$ While the intuition for $2$ is that by taking Barycentric subdivisions we don't alter which maximal thin paths are being interchanged so there is a bijection between the automorphism group of a finite DAG and any Barycentric subdivision. In any case I imagine someone has written about this, as it would allow a reduction of the automorphism group of a DAG to the automorphism group of a smaller DAG which could simplify for example the graph automorphism problem for DAGs. Also I can think of applying a variant of this to any digraph possibly using some notion of path decompositions. $\endgroup$
    – Ethan Splaver
    Commented Mar 16, 2018 at 11:34
  • $\begingroup$ 1. is indeed obviously true, for the reason you have already given at 2018-03-16 11:23:46Z. 2. is true for the following reason: necessity is trivial; for sufficiency, it's enough to prove that any isomorphism between the barycentric subdivisions must map every non-subdivision-vert. (n.-s.-v.) to a non-subdivision-vertex. This is trivial for n.-s.-v.s with deg. $\geq3$ or deg. $\leq 1$; for any n.-s.-v. with deg. $=2$, mapping it to a subdivision-vert. leads, while locally possible, to the contradiction that some other deg.-$2$-vert. at a finite dist. from $v$ must be mapped to a $\geq3$-vert. $\endgroup$
    – Peter Heinig
    Commented Mar 16, 2018 at 12:25
  • $\begingroup$ @PeterHeinig Thanks, I didn't realize what I wrote already constituted a proof. Often when writing proofs in graph theory I sometimes make things too formal, as I've found many geometric/hand-wavy proofs from the time I've been studying related areas. Also with their often being different notation for the same objects used by different authors I don't want to make any false deduction based on a resulting ambiguity etc. In any case I appreciate the book you cited, as though it didn't have any information on the relationship(s) I was interested in, I did find several helpful theorems in it. $\endgroup$
    – Ethan Splaver
    Commented Mar 16, 2018 at 12:37
  • $\begingroup$ Re "I didn't realize what I wrote already constituted a proof". Well, that depends on what you mean by 'proof'. For it to be a formal proof, you'd of course have to formalize it in a specified proof-system, e.g. Hilbert- or natural-deduction-style. But what you wrote is the gist of it, I believe. Incidentally, I made a tiny mistake in what I wrote at 2018-03-16 12:25:42Z: instead of "must be mapped to a $\geq 3$-vert." it should have been 'must be mapped to a vert. of degree unequal to $2$'. In the counterfactual situation in question, one has to account for the possibility of degree$=1$, too. $\endgroup$
    – Peter Heinig
    Commented Mar 16, 2018 at 14:09

0

Reset to default

You must log in to answer this question.