Ordering list elements with component intervals

Every list induces an equivalence relation of its indexes called the kernel of the list. Every finite totally ordered set has a component interval which includes the parts of a partition of the indexes of a list. Here is an example in which we compute the component intervals:

(= (component-intervals [3 0 1 0 1 2 3 4])
   [[1 3] [2 4] [5 5] [0 6] [7 7]]

Since the set of intervals of a partially ordered set is itself partially ordered we know that we can partially order those five intervals to get the following ordering relation:

(= (order-from-list [3 0 1 0 1 2 3 4 ])
   [[1 0 1 0 1]
    [0 1 1 0 1]
    [0 0 1 0 1]
    [0 0 0 1 1]
    [0 0 0 0 1]]

The order type of the above partial ordering relation is the rooted tree {{{} 2} 1, {} 1}. Producing all the different configurations of a list that satisfy an unbounded partial order is a far more complex task that once achieved can be used to compute all the different permutations of a list by their ordering.

Product orders

Let $\mathbb{N}_k$ represent an elementary total order with $k$ elements. Every divisibility relation is the product of total orders. The divisibility lattice of 24 is $\mathbb{N}_2 \times \mathbb{N}_4$.

The prime signature of a number describes the divisibility lattice of a number up to isomorphism by describing it as a product of total orders. The number of divisors of a number is the size of this ordering relation and the number of prime factors of a number counting repetition turns it into a graded lattice.

Ordering ordering relations

Every partial ordering relation falls between two weak orders: a child weak order and a parent weak order. These two weak orders form an order interval. Of course weak orders themselves have a trivial component interval since their child and parent intervals are both equal.

The divisibility relation on the natural numbers $(\mathbb{N},|)$ is a suborder of the weak ordering relation induced by the big omega function which outputs the number of prime factors of a number counting multiplicity.

The width of a partial ordering relation is the size of its largest child total order and topologically sorting produces the parent total orders of the partial order.

Weakly ordering vertex targets

Given a strongly connected directed graph G we can produce a weak order of the vertices of G based upon their proximity to a vertex G:

(= (targets-list G 0)
   [#{0} #{1 2} #{3}])

We can represent the shape of a targets list by enumerating the sizes of each target set which provides a useful graph invariant. By examining the cubic graphs of size 8 we see that not all regular graphs are eccentricity regular and not all graphs that are both regular graphs and eccentricity regular are distance regular. We further see that not all distance regular graphs are isomorphic.

List forms

We can form bijections from a list of elements of some size to alternative representations for those lists. We can use this functionality to describe nesting structures to begin with:

(= (nesting '(def inc [x] (+ x 1)))
   '(0 1 [2] (3 4 5)))

We can use the catalan numbers to enumerate all binary bracketings of size n. Given such a nesting structure we can apply it back to a list:

(= ((nesting-function '((0 1) (2 3)) [10 20 30 40])
   '((10 20) (30 40)))

Matrices and grids use a special kind of nesting. Besides describing lists with nesting structures we can describe lists by associating indexes with keys in a hash.

Cyclic permutation groups

Iterating cycle structures:
We can begin by describing the effects of iteration on a cycle structure:

({1 6} {6 1} {3 2} {2 3} {3 2} {6 1})

Using this we can effectively determine the cycle structure of cyclic subgroups and cyclic supergroups of any given cyclic permutation group.

Cyclic permutation groups:
Given a permutation we can select a canonical generator for the permutation group generated by that permutation by selecting a permutation amongst the available iterates using the lexicographic ordering of permutations.

Clique complexes

Every undirected graph induces an abstract simplical complex called the clique complex and every abstract simplical complex induces an undirected graph called the 1-skeleton of the complex so in this sense undirected graphs and abstract simplical complexes are isomorphic structures.