0
$\begingroup$

Let $G=(V,E)$ be a simple digraph that is semi-complete (ie. there's at least one arc between each unordered pair of vertices) and quasi-transitive (ie. its complement is transitive).

Is it true that we can decompose $G$ into semi-complete, transitive spanning subgraphs? In other words, is there a collection of graphs $G_n=(V,E_n)$ where $G_n$ is semi-complete and transitive and $E=\bigcup_n E_n$?

Note that the union of the edges needn't be disjoint. In case it makes a difference, I'm particularly curious about the case where $V$ is infinite.

Thanks!

Improve this question
$\endgroup$
9
  • $\begingroup$ your terminology is strange; typically, "simple" means that there are no multiple arcs. If we assume that, then the digraphs in question are called tournaments, and are well-studied. $\endgroup$
    – Dima Pasechnik
    Commented Apr 5, 2015 at 6:42
  • $\begingroup$ I'm sorry for the confusing terminology, I meant that there can be at most one edge from $x$ to $y$, but unlike a tournament, perhaps one from $y$ to $x$ as well. $\endgroup$
    – Funktorality
    Commented Apr 5, 2015 at 7:02
  • $\begingroup$ the union of edges of $G_n$'s certainly cannot always be disjoint (take a tournament and add one more arc somewhere). $\endgroup$
    – Dima Pasechnik
    Commented Apr 5, 2015 at 7:28
  • $\begingroup$ It's also not clear what you mean by quasi-transitive: "complement" usually means that edges and non-edges replace each other. $\endgroup$
    – Dima Pasechnik
    Commented Apr 5, 2015 at 7:32
  • 1
    $\begingroup$ If I read the conditions correctly, the complement of $G$ is required to be a partial order, and the complements of the $G_n$ are linear orders, hence you are asking whether every partial order is an intersection of linear orders. This is indeed true. $\endgroup$
    – Emil Jeřábek
    Commented Apr 5, 2015 at 13:54

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .