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
    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
    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
    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
    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
    Apr 5, 2015 at 13:54

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.