Representing graphs and preorders as set systems

In the fundamentals of combinatorics I previously described the fact that preorders and graphs are the most fundamental objects of study in combinatorics. Further, I described how interrelated graph theory and order theory are. Graphs such as the comparability graph can be formed from any preorder, and the adjacency containment preorder can be formed from any graph. For trivially perfect graphs, which are the comparability graphs of trees, these preorders fully determine the graphs. The selection of preorders and graphs as fundamental was not random, but rather it was determined by the fact both structures can be represented by set systems. They are among the simplest set systems that can be formed by rank.

One of the reasons to privilege set systems among all other structures is that set systems can be used to describe the classified substructures of any structure. This means that graphs can be fully determined by certain substructures of a structure like the cliques of a graph, or the chains of a partial order which determines the inclusion comparability graph of the order. Likewise, preorders can be formed by certain classified substructures, such as the numerous cases of sets of substructures determined by a closure operation generated by its singleton elements. As set systems are the basic way of describing substructures, graphs and preorders as special cases of them are fundamental concepts.

Graphs:

Independency families
Independency families are nullfree subsingleton free rank two families. In other words all of their sets are either size one or two and the size one sets are not subsets of the size two sets, which means that all the size one or singleton sets are isolated. This means that they are sperner families, as no set is contained in one another.

#{#{0 1} #{0 2} #{1 2} #{2 3}}
#{#{0 1} #{0 2} #{1 2} #{1 3} #{2 3}}

Dependency families
Dependency families are nullfree subsingleton closed rank two families. In other words, they are subnonnull closed set systems, as all the subsets of any set other then the empty set are included in the set. This makes them the rank two counterpart to the independency families. Dependency families are fully determined by their incidence order, which makes them an ideal means of representing graphs. Dependency families form a strongly unique extrema part width two height two partial order under inclusion. The maximal cliques of a cluster graph form a set partition.

#{#{0} #{1} #{2} #{3} #{0 1} #{0 2} #{1 2} #{2 3}}
#{#{0} #{1} #{2} #{3} #{0 1} #{0 2} #{1 2} #{1 3} #{2 3}}

Maximal cliques families
Maximal clique families are another sperner family representation of graphs, which means that the ordering properties of the set system tell us nothing here as well. The difference from independency families is that the maximal clique families are not necessarily rank two. Instead, they are of conjunctive rank two, in the sense that they are a rank two set system.

#{#{0 1 2} #{2 3}}
#{#{0 1 2} #{1 2 3}}

Clique families
The clique families are another set system that are of conjunctive rank two, which essentially means that the goal clauses of conjunctive form of the set system are not a size greater then two. All representations of graphs are in some sense rank two, because they are fundamentally generated by pairs of elements. Like the clique families, these are ordered set systems, except that they form a meet semilattice rather then a strongly unique extrema order, making them more lattice like. In fact, these are the total join representations of a atomistic meet semilattice.

#{#{} #{0} {1} #{2} #{3} #{0 1} #{0 2} #{1 2} #{0 1 2} #{2 3}}
#{#{} #{0} #{1} #{2} #{3} #{0 1} #{0 2} 
  #{1 2} #{1 3} #{2 3} #{0 1 2} #{1 2 3}}

Preorders

Preorder containment families
Given any preordering relation we can form the principal ideals of the preorder, by the input sets of the elements of the preorder. This fully preserves the specialization order of the preorder through the inclusion order of the set system, which makes this an ideal representation for preorders. A partial order with some property is represented by an order containment family with the same property. As a result, when thinking of preorders I tend to think of preorder containment families as the canonical representation of them.

#{#{0} #{0 1} #{0 2} #{0 1 2 3}}
#{#{0} #{1} #{0 1 2} #{0 1 3}}
#{#{0 1} #{2 3} #{0 1 2 3 4 5}}
#{#{0 1} #{0 1 2 3} #{0 1 2 3 4 5}}

Alexandrov topologies
Alexandrov topologies are topologies that are both union closed and intersection closed. In other words, they are null extrema closed families. It is known that these families are represented entirely by their specialization preorders. In fact, all finite topologies are Alexandrov topologies, which can be represented by their preorders. An Alexandrov topology can be formed from a preorder by taking all lower sets of the preorder, rather then simply the principal ideals. The corresponding preorder containment family can be produced by the join irreducible member sets of the topology or the singleton closures. These families are conjunctive rank two as well except they are logically generated by definite clauses rather then goal clauses.

#{#{} #{0} #{0 1} #{0 2} #{0 1 2} #{0 1 2 3}}
#{#{} #{0} #{1} #{0 1} #{1 2} #{0 1 2}}
#{#{} #{0} #{1} #{0 1} #{0 1 2} #{0 1 3} #{0 1 2 3}}
#{#{} #{0 1} #{0 1 2 3} #{0 1 2 3 4 5}}