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.