Lattice Drawing

Exciting the new applications! A brief explanation, instructions, history.

If you are reading this if means your browser is not setup to support Java.

New Applications of this Applet

There are three exciting new programs that use this lattice drawing applet.

This amazing program allows you to have Maple and GAP draw lattices. So for example you can use either program to calculate the lattice of subgroups of a group and then ask for the diagram. The diagram is automatically brought up in a browser window. JavaMath
Universal Algebra Calculator [more to come]
Online Java Lattice Building Application This projects, which was written by Maarten Janssen as part of his thesis, lets you create lattices using Formal Concept Analysis and draws them with this applet. The authors have added several nice features to the applet which will be incorporated into our version.

Brief Explanation

This demonstrates my program for automatically generating lattice diagrams from abstract representations of lattices (or partially ordered sets). The goal is not make diagrams suitable for publication (I have a different program for that) but to allow my symbolic algebra program for lattices to be able to make a recognizable picture.

The program first calculates a rank function on the ordered set and uses this to determine the height of the elements. It then places the points in three space using the rank for the height, i.e., for the z-coordinate. The points of the same rank are arranged around a circle on a plane parallel to the x-y plane. Now we imagine forces acting on the elements. Comparable elements are attracted to each other while incomparable elements are repulsed.

These forces are applied several times in three phases. In the first phase the repulsive force is set to be very strong; in the second phase the attractive force is strong; and in the final phase the forces are balanced. You get each of these phases by pressing the Next button. The original program tried several projections from 3-space to 2-space, choosing the best one. With this demo you should use the rotation buttons to get the best projection.

Instructions

Choose a lattice from the list on the right. You can do this at any time. You can choose the current lattice to start its drawing over again.

The Next button moves to the next phase as described in the brief explanation above.
When done you need to use the rotate buttons to find the best projection. It's ok to use these buttons while the forces are being applied. You can even start the diagram rotating and then push the Next button.
After the three phases have been executed, pressing the Next button will apply the balanced forces several more times. During this phase (only) you can use the sliders to adjust the forces.
Input your own lattice!!! (or ordered set). Press the Input button and fill in the URL for a file with your lattice. Detailed instructions on what the URL should be and what the file should have.
Try inputing some of my lattices Press the Input button and fill in one of the following URLs.
- http://www.math.hawaii.edu/~ralph/lats/z3_2.lat
  This is the congruence lattice of the direct product of two copies of the 3 element algebra which is the reduct of the 3 element field to only its multiplication. The edges colored by their Tame Congruence Theory type. yellow is type 2 (group type) and black is type 5 (semilattice type). The whole Universal Algebra Calculator program is available.
- http://www.math.hawaii.edu/~ralph/lats/perm4.lat
  This is the lattice of all permutations on 4 letters with the weak Bruhat order. Nathalie Caspard has recently shown such lattices are bounded homomorphic images of free lattices.
- http://www.math.hawaii.edu/~ralph/lats/fl22n5.lat
  This is the lattice freely generated by two 2 element chains over the variety generated by N₅.
- http://www.math.hawaii.edu/~ralph/lats/geyer.lat
  Geyer had conjectured that a bounded homomorphic image of a free lattice and its congruence lattice would have the same number of elements. This is a counter-example found with my lattice program.
- http://www.math.hawaii.edu/~ralph/lats/con-geyer.lat
  This is the congruence lattice of the above lattice.

History

In the early 1980's I wrote programs to calculate in free lattices. Each element of a free lattice has a finite lattice associated with it which determines the important properties of the element. My program calculated this lattice but I needed to diagram it to see quickly what it was. I thought this would be easy: I would arrange the elements in levels and draw lines between covering pairs of elements. This produces a correct diagram (ignoring lines inadvertantly crossing over elements) but I soon discovered that even small lattices were unrecognizable using this drawing algorithm. Over the years the drawing program as been improved to its present form.

As part of his JavaMath project Andrew Solomon made several improvements to the applet. Among these is the mouse-over showing the labels of the elements which is important for both his application and in the UA Calculator. Of course he is responsible for the communication between the applet and Maple and Gap.

Chapter 11 of my joint book with J. B. Nation and Jarda Jezek, Free Lattices, which covers algorithms for finite lattices, includes some additional information on our drawing algorithm.

Standalone Version

This Java program can be run standalone. In this case you can input a file the describes your lattice by it upper covers. It could then be linked to other programs. Download the source code.

email:email me
Last updated: Mon Aug 26
Ralph Freese