"All sessions in MacDonald Hall 121 and 120, on the campus of the University of Ottawa."
As a demonstration, we show several applications such as compiler data structures, entity relation diagrams, genealogical trees and computer networks.
Many parts of the intermediate representations of compilers are graphs. Graph visualization allows better understanding of the behavior of compilers. We present a list of applications of graph layout in compiler construction, their typical problems and the heuristics to solve them. As demonstration, we show a visualized compiler and the facilities to browse through the large graphs that occur in compilers.
Many of these results have a combinatorial flavor: what is the optimal size of a lattice L representing a given finite distributive lattice D? What is its optimal order dimension, length?
In this lecture, I will review the basic results and techniques.
Quite a bit of work has been done on simultaneously representing more than one finite distributive lattice. Most of the combinatorial questions of this aspect of representation theory are still open.
As for (i), the dominating part of the work done is about ordered sets consisting of just two layers from 2^n, and within that part, the major theme is their dimension. If n is odd, the two middle levels of 2^n have the same size, and an (open) conjecture now attributed to Havel states that the covering graph of such an ordered sets always admits a Hamiltonian path. Another question is which (bipartite) ordered sets allow a cover-preserving embedding into two consecutive levels of 2^n. A quite self-imposing problem is to count the isotone self-maps respectively the order automorphisms of a Boolean layer cake.
As for (ii), it is immediate that a Boolean layer cake is a lattice if and only if it consists of two adjacent levels of 2^n plus top and bottom. Concentrating on the case of levels 2 and 3, it is shown that these lattices have a large number of large (in a sense to be specified) sublattices. The enumeration and classification of such large sublattices sheds some light on the sublattice spectrum question and shows that there is no polynomial bound (in the size of the layer cake) for the number of maximal sublattices it does have. Sizes of minimal generating sets and computational aspects are also considered.
The latest research on linear extensions of ordered sets, concentrates on those which seem to have broad impact on other areas of combinatorial mathematics. Among the principal themes are (1) dimension, fractional dimension and related parameters; (2) balancing pairs and applications to sorting; and (3) partitioning, covering and packing problems.
While an exhaustive search algorithm for a fixed point free map is easily written it is also quite inefficient. We discuss a greedy algorithm by Xia which can be used to speed up the search for a fixed point free self map. The ideas used in creating this algorithm show close connections to two problems: the decision whether an ordered set has a fixed point free automorphism, respectively, the decision whether a given r-partite graph has an r-clique. These two problems are (in view of the work of Goddard, Lubiw and Williamson) NP-complete.
Retraction theorems leading to dismantling algorithms are another approach to the problem. We present the classical dismantling procedure by Rival and extensions by Li, Milner, Rutkowski, Fofanova and the author. These theorems give a polynomial algorithm to decide if an ordered set has the fixed point property for certain classes of ordered sets (height 1, width 2), and structural insights for other classes (chain-complete ordered sets with no infinite antichains, sets of (interval) dimension 2). The related issue of uniqueness of cores gives an insight into Birkhoff's problem regarding cancellation of exponents. We also discuss Walker's relational fixed point property for which the analogous problem has a satisfying solution.
Another variation on the retraction theme is the use of algebraic topology in deriving fixed point theorems instigated by Baclawski and Björner and continued, for example, by Constantin and Fournier. After a primer on the basic concepts of integer homology we present their retraction/dismantling procedures, which always prove acyclicity of the associated simplicial complex and then the fixed point property via a Lefschetz fixed point theorem. Differences and similarities with the above combinatorial procedures will be pointed out. The main problem in making these results accessible to entirely combinatorial proofs turns out to be the lack of a combinatorial/discrete analogue of the continuous concept of a weak retract, respectively, a deformation retract. We also present a class of ordered sets without the fixed point property, such that all proper retracts have the fixed point property that is induced via triangulations of n-spheres.
We conclude with an indication how, the arguments by Abian, Brown and Pelczar which prove that, in a chain-complete ordered set, existence of a point p with p less or equal to f(p) implies the existence of a fixed point, have recently found application to analysis in the work of Carl, Heikkila, Lakhshmikantham and others.
As a research tool it has substantially advanced the conjecture that every ordered set without autonomous subset has a perpendicular, that is, a companion ordered set on the same underlying set which shares no common isotone self-map except for the identity and the constant maps.
As a practical tool it is already in use extensively in applications bearing on decision-making for large data sets, for example, in career counselling, academic course selection, and degree audit.
One of the main features of GLAD, through the small utility program VGASHOW, is to provide the possibility to make slide presentations on VGA screens. Dozens of images can be compressed on a diskette and easily extracted in real time without the user's intervention, for organizing lectures, exhibitions, conferences.
As the graphic images that are the outcome of lattice analysis can be quite complex, another facility which is provided with the program consists in summarizing the process defining an image as a "scenario", which can be called back afterwards to regenerate the image when need be. Some 15 such scenarios accompany the program, which generate the set of "standard examples" that are documented in GLAD's on line help facility.
Advances in
the theory and practice of graph drawingAdvances (by Roberto Tamassia)
Graph Layout
for Applications in Compiler Construction (By G. Sander)
Boolean Layer
Cakes (by Jürg Schmid)
Generating Algebraic Laws from Imperative Programs (by H. Peter Gumm)
Algorithms for
the Fixed Point Property (by Bernd S. W. Schröder)
Preference
Structures and Their Numerical Representations (By Peter
Fishburn)
Attribute
exploration with background knowledge (By Bernhard Ganter)
Or contact the organizers directly:
Ivan Rival rival@csi.uottawa.ca
Nejib Zaguia zaguia@csi.uottawa.ca
Department of Computer Science, University of Ottawa, Ottawa K1N 6N5 Canada