Friday, May 24, 2013

Product orders

Every divisibility relation is the product of total orders.

Wednesday, May 22, 2013

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.

Saturday, May 18, 2013

Vertex targets list

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.

Friday, May 17, 2013

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.

Friday, May 10, 2013

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.

Sunday, May 5, 2013

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.

Sunday, April 14, 2013

Approximating irrational numbers using intervals

Every irrational number can be progressively approximated using rational intervals. Here is a sequence of intervals that approximate $\sqrt{2}$:
[-Infinity Infinity]
[0 2]
[4/3 5/3]
[11/8 10/7]
[24/17 27/19]
[65/46 58/41]
[140/99 157/111]
[379/268 338/239]
[816/577 915/647]
[2209/1562 1970/1393]
[4756/3363 5333/3771]
[12875/9104 11482/8119]
[27720/19601 31083/21979]
[75041/53062 66922/47321]
[161564/114243 181165/128103]
[437371/309268 390050/275807]

This sequence of intervals is produced by the continued fraction representation for $\sqrt{2}$ which is 1,2,2,2,2,2,2,... with an infinite sequence of twos.