Tuesday, September 30, 2014

Managing complexity

Complexity is interpreted in a variety of ways. With mereology systems that have more parts tend to be more complex then ones that do not. Within information theory the notion of complexity is determined by Kolmogrov complexity. In computer science there is a notion of complexity called computational complexity which is related to the growth rate of the computation time with respect to argument size.

Information theory

Information theory studies the ways in which we can encode information. This includes the study of the lossless compression of information. Information theory is related to thermodynamics by Landauer's principle which is always related to reversible computing.

Saturday, August 30, 2014

Height two orders and convex families

Given a partially ordered set the convex sets of the partial order form an atomistic convex geometry and the height two partial orders form a subclass closed family. These two families correspond to one another as the minimal family that generates a convex family under the convex closure operation is always going to be a height two partial order. Consider the following height two family:
#{#{0} #{1} #{2} #{3} #{0 1 2} #{1 2 3}}
The convex closure of the above height two family is a family which contains all of the elements of the height two family plus those elements that are necessary to make the family convex:
#{#{0} #{1} #{2} #{3} #{0 1} #{0 2} 
  #{1 2} #{1 3} #{2 3} #{0 1 2} #{0 1 3}}
Certain partial orders can be both height two and convex. These include the dependency families which are the subsingleton closed nullfree rank two families. The dependency families correspond to the simple graphs in graph theory and they can also be produced from any atomistic height two order in which no element has more then two predecessors.

Sunday, August 24, 2014

Independent sets of Moore families

Lets suppose that we have a family of sets that forms a Moore family.
#{#{} #{0} #{1} #{2} #{0 1 2}}
Then the independent sets of that Moore family are precisely those sets that form power sets when intersected with all the sets of the Moore family. Here are the independent sets of the above Moore family:
#{#{} #{0} #{1} #{2}}
If a given Moore family is a family of flats formed from a matroid then the independent sets of that family can be used to reproduce the matroid. If the Moore family is instead an Alexandrov family then the independent sets are the cliques of the complement of the comparability relation of the specialization preorder. This means that the independent sets of an Alexandrov family form a clique complex.

Saturday, May 31, 2014

Monogenic semigroups

The monogenic semigroups are semigroups that are generated by a single element. All semigroups that are generated by at least two elements must contain distinct maximal proper subsemigroups corresponding to those elements. This means that all semigroups that contain only a single maximal proper subsemigroup are necessarily monogenic. Nonetheless, not all monogenic semigroups contain only one maximal proper subsemigroup.

The monogenic semigroups that contain only one maximal proper subsemigroup are called primary monogenic semigroups. Non-primary monogenic semigroups include cyclic groups that are of non-prime power orders. The prime power cyclic groups are called primary cyclic groups and hence they are primary monogenic semigroups. The primary monogenic semigroups can be used to generate the elements of any semigroup.

Friday, May 30, 2014

Perfect graphs

Amongst the set of all graphs the perfect graphs are particularly interesting. Perfect graphs subsume both comparability graphs and co-comparability graphs so they can describe both the comparability and the incomparability conditions of partial ordering relations. As the the perfect graphs exclude odd holes and odd anti-holes they are far easier to describe using partial orders themselves.

The trivially perfect graphs and the co trivially perfect graphs are perfect graphs that are of particular interest to us. They can both be described entirely using preorders produced by the immediate reachability conditions on the graphs. Equivalence graphs are trivially perfect and their complements the complete partite graphs are co trivially perfect.

The threshold graphs are both trivially perfect and co trivially perfect. The threshold equivalence graphs form a Moore family of graphs with their own closure operation defined by split completion. Both empty graphs and complete graphs belong to the class of threshold equivalence graphs.

Wednesday, April 30, 2014

Embedding partial orders in complete lattices

Given a partially ordered set we can always embed that partial order within a complete lattice through Dedekind completion so that partial order becomes a suborder of a complete lattice. For finite unique extrema partial orders this simply means adding bounds to the partial order to make it into a lattice. Otherwise there may need to be elements placed between others such as in the case of the [2 2] weak order.

If we represent partial orders as set systems then the process of embedding the partial order within a complete lattice is equivalent to the process of embedding the set system within a Moore family. We can always acquire such a set system by taking the Moore completion of the family of sets.

The general applicability of lattice theory to problems of order theory through the process of embedding partial orders in complete lattices makes me think that lattice theory should play a fundamental role in our understanding of order theory. With an understanding of complete lattices we can better understand partial orders in general.