On the support sets of acyclic and transitive digraphs

Abstract EN

For any “acyclic digraph  there is defined a connected component” G X( )  of the graph G X( ) containing relation  , there are defined non-empty “support sets”: ' S y X x y for all x X S x X x y for all y X ( ) { : ( , ) 0 }, ( ) { : ( , ) 0 },           there are defined the families: ' ' S G S X G X S G S X G X ( ) { ( ) : ( )}, ( ) { ( ) : ( )}             “consisting of all support sets of acyclic digraphs”  included in the component G X( )  .

In this work we proved that the equality ' S G S G ( ) ( )    is valid and we investigated some features of the concepts of “support sets of acyclic and transitive digraphs”.

The family ' S G S G ( ) ( ( ))    is a specific partially ordered set with respect to the natural relation of inclusion of sets.

Specificity is that, together with each element, the family S G( )  contains all non- empty subsets of this element, and, in addition, S G( )  contains all singlton subsets of the set X .

Moreover, if  is a “transitive digraph”, then the family S G( )  contains all two-element subsets of the set X .

The latter circumstance can play an important role in the process of separating transitive digraphs from acyclic digraphs.

In connection with this fact, we consider the central problem of an independent description of families S G( )  (or their maximal elements).-