Monday, August 31, 2015

Threshold graphs and interval orders

Threshold graphs like interval orders have the property that each element is determined by some vertex invariant in all substructures. In threshold graphs all elements are determined by degree. In interval orders all elements are determined entirely by their interval representations. Both of these properties are maintained in forbidden substructures of each of these structures. Weak orders are the special class of interval orders whose elements are determined in terms of degrees. Threshold orders are interval orders with threshold comparability.

Saturday, May 30, 2015

Weakly chordal graphs

The weakly chordal graphs are a subclass of the perfect graphs that exclude all holes and antiholes. The weakly chordal graphs are an important class of graphs in order theory. Well the class of weakly chordal graphs does not include all comparability graphs or all cocomparability graphs it does include all permutation graphs which are the graphs that are both comparability and cocomparability. This means it also includes the cographs which also happen to be permutation graphs.

The chordal graphs as well as their complements the cochordal graphs are weakly chordal. The trivially perfect graphs are precisely those graphs that are both chordal and cographs. The cotrivially perfect graphs are precisely those graphs that are both cochordal and cographs. The trivially perfect graphs and the cotrivially perfect graphs can both be expressed entirely in terms of preorders. Only weakly chordal graphs can be described entirely in terms of preorders in this sense.

Thursday, April 30, 2015

Comparisons between sets

We can produce certain comparisons between sets such as based upon the intersection size. This is what leads to the classes of independent, linear, and antidisjoint families of sets. The independent families have no intersection between elements. Linear families have no intersection larger then one. And the antidisjoint families are complementary to the independent families in the sense that no elements lack intersection. Pairs of sets can only either be comparable or incomparable which is what leads to chain families and sperner families. In chain families each pair of sets is comparable. In sperner families each pair of sets is incomparable. Laminar families are produced by the union of independence and comparability as each element is either comparable or it has empty intersection. In uniform families each element has the same size. Each of these comparisons between sets corresponds to a clique family. The dependence condition of antidisjoint families produces line graphs and the comparability condition produces comparability graphs and cocomparability graphs of subclass containment orders.

Monday, March 30, 2015

Forbidden subfamilies

Given a set theory we can classify families of sets based upon forbidden subfamilies. As with most classes determined by forbidden substructures the classification of families based upon forbidden subfamilies is characterized based upon the size of the largest forbidden subfamily. If the largest forbidden subfamily is of size one then the class is going to be a power set of some family often determined by cardinality. If the largest forbidden subfamily is of size two then the class is going to be a clique family because it is generated by the dependencies between pairs of elements. Another issue is the smallest forbidden subfamily. All families with size greater then the forbidden size will be accepted automatically. The two issues of the largest and smallest size of a forbidden substructure help to determine nature of subclass closed families.

Saturday, March 28, 2015

Algebraic set theory

The theory of sets can be described by a boolean algebra equipped with a singleton function which converts between any atom in the boolean algebra into its corresponding member value. Sets can then be described within this algebraic structure entirely in terms of the join operation of the boolean algebra and the singleton function. This allows us to describe sets entirely in terms of algebraic set theory.

The only element in a boolean algebra which does not contain any atoms is the lower bound element of the boolean algebra. By using this lower bound element, the join operation of the boolean algebra, and the singleton function we can produce elements of the pure elements of the algebra. These pure elements correspond to the pure sets which we generally encounter in set theory. Some algebras of sets are limited to only pure elements and others are not.

Saturday, February 28, 2015

Atoms of a lattice

Given a distributive lattice then we can determine that the atoms of that lattice are those elements that cover the lower bound of that lattice. In other words they are the singleton elements of that lattice. For example in the case of the lattice of sets under inclusion the atoms of that lattice are the singleton sets. The atoms of a lattice play an interesting role in the description of that lattice.

In the case of the lattice of sets we find that any given entity can be converted to a singleton set containing only that entity and likewise any singleton set containing only a single entity can be converted into back into that entity. This means that the function to convert entities into singleton sets is a one to one correspondence. This singleton function is not described by the order on the sets so it is outside of the underlying order theory. A lattice ordered structure can be extended with such a singleton function to be produced a more advanced structure of this sort.

Thursday, January 1, 2015

2014 year in review

Within the year 2014 I maintained my focus on order theory and then I began to examine set systems which are equivalent to suborders of a boolean algebra. Being a suborder each set system is partially ordered and each partial order can be embedded into a boolean algebra often in a variety of ways. In particular, given a partial order we can convert that partial order into the set system by taking the set of all sets of elements of principal ideals of that partial order. We can also convert that partial order into a distributive lattice by taking the set of lower sets though that does not preserve order. In this way the theory of set systems subsumes the theory of partial orders. Everything we can say about partial orders can also be expressed in terms of set systems. As a result of this fact, set systems became a primary concern of mine in the past year.

Through my exploration of set systems as suborders of boolean algebras I later came to consider suborders of other distributive lattices. In particular, we can consider suborders of distributive lattices that are defined by multiset inclusion. In this way we can examine the idea of multiset systems in addition to set systems. An interesting facet of the theory of multiset systems is that we can convert any ordered collection into a multiset system regardless of cardinality just as we can convert any ordered collection into a set system using the kuratowski pair. After considering the theory of suborders of distributive lattices like these we can generalize and then consider the theory of suborders of a partial order in general.

As the notion of set systems as suborders of a boolean algebra has been explored my ontology has continued to expand as these notions have been explored. As a result an ontology of set systems including a wide variety of classes of set systems has been produced including classes of set systems which are defined entirely by their order characteristics. In this way the ontology has expanded to deal with sets as well as sets whose members are all sets. These are distinguished from objects which are not ontologically classified as sets and sets which contain elements that are not classified as sets. As an ontology deals with sets and classes itself it is sensible that one of the most basic things to be classified in an ontology are such sets and classes. This is the approach that I am now taking to ontology engineering.