3
$\begingroup$

Say that a digraph $(V,E)$ is reducible if there exist $x,y\in V$ with $x\ne y$ and such that for all $z\in V$, $(x,z)\in E\leftrightarrow(y,z)\in E$ and $(z,x)\in E\leftrightarrow(z,y)\in E$. It is clear that a reducible digraph has a non-trivial automorphism (swapping $x$ and $y$ and fixing the rest), but the inverse is not necessarily true.

For some applications elsewhere, I'm interested in "irreducible" digraphs and especially "irreducible" posets. Now, (insert usual disclaimer about not being an expert), do these already have a (potentially better) name? and if yes, where have they been treated?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Twin-free might be the term you're after. $\endgroup$
    – Peter Taylor
    Commented Mar 26, 2022 at 9:37
  • $\begingroup$ By "where could I find them" do you mean finding actual (small?) examples, or finding in some other sense? $\endgroup$
    – Jukka Kohonen
    Commented Mar 26, 2022 at 14:28
  • $\begingroup$ Very small examples exist. The smallest poset with a nontrivial automorphism but no twin elements has 4 elements: the disjoint union of two 2-element chains. If you require connected, the smallest such poset has 5 elements (the previous and an adjoined bottom element). So what kind of examples do you desire? $\endgroup$
    – Jukka Kohonen
    Commented Mar 26, 2022 at 15:25
  • $\begingroup$ Graphs (undirected) with the property that no two distinct vertices have the same neighborhood have several names: point-determining, R-thin, mating type, and M-graphs. See, e.g., doi.org/10.1016/j.jcta.2010.03.009. I don't know that the analogous digraphs have been studied. $\endgroup$
    – Ira Gessel
    Commented Mar 26, 2022 at 16:17
  • $\begingroup$ Thank you, "twin-free" seems indeed to be good terminology, as do the suggestions by Ira. By "where could I find them?" I meant finding references to the terminology, not finding the graphs themselves, sorry for the ambiguity which I have now removed. $\endgroup$
    – Uli Fahrenberg
    Commented Mar 27, 2022 at 9:29

1 Answer 1

Reset to default
0
$\begingroup$

Just to provide a conclusion here (summing up the comments): twin-free seems to be the best and, dare I say, standard terminology; two points as in my question would then be called twins. Otherwise, point-determining, R-thin, or mating-type have been used to denote the same property.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .