EE 382V: Lattice Theory with Applications

EE 382V Vijay Garg Fall 2003

EE 382V: LATTICE THEORY WITH APPLICATIONS
MW 9:30 - 11:00
Fall 2003
Room: ENS 126
Unique Number: 15533

Instructor: Prof. Vijay Garg ; Office: ENS 516 ; Phone: 471-9424 ; e-mail: garg@ece.utexas.edu;
Office Hours: TTh 2:30-4:00 (or by appointment);
URL: http://www.ece.utexas.edu/~garg

Prerequisites: Graduate standing

Course Contents: Partial order and lattice theory now play an important role in many disciplines of computer science and engineering. For example, they have applications in distributed computing (vector clocks, global predicate detection), concurrency theory (pomsets, occurrence nets), programming language semantics (fixed-point semantics), and data mining (concept analysis). They are also useful in other disciplines of mathematics such as combinatorics, number theory and group theory. In this course, I will introduce important results in this theory along with their applications in computer engineering. The bias of the course wil be on computational aspects of lattice theory (algorithms) and on applications (esp. distributed systems). There is no final exam but there will be two exams during the course. The following topics will be covered in the course:

Posets: Basics Calculating height and width of a poset, Dilworth's theorem, decomposition of a poset
Lattices: Distributive and Modular Lattices, Lattices as algebraic structures, M3-N5 theorem.
Ideals Ideals and Filters, Birkhoff's Theorem, Join and Meet Irreducible Elements, Applications to Global Predicate Detection
Fixed Point Theorems: Complete Lattices, monotone and continuous functions, Knaster-Tarski theorem, Application to semantics of CSP
Sperner Property: Ranked Posets, Erdos-Szekeres Theorem, Sperner property, Hall's Theorem
Enumeration: Enumerating ideals in BFS, DFS, Lexical and Gray Code; enumerating level sets, enumeration of linear extensions.
Dimension Theory: Encoding posets, applications to encoding distributed computations, Hiraguchi's conjecture
Special Classes of Posets: 2-dimensional posets, series-parallel posets, interval posets.
Mobius Inversion: Mobius function and applications to number theory
Slicing: Slicing with applications to distributed computing and combinatorics

Grading: 25 % Assignments, 25 % Exam 1 (in-class), 20% Term paper, 5% Class presentation 25 % Exam 2.

Course Material:
Notes by the instructor. The following book is recommended (but not required).
Introduction to Lattices and Order by B.A. Davey and H.A. Priestley, Cambridge University Press.
Directory that contains handouts for the course

Course Evaluation: Standard ; Add/Drop Policy: Standard.
Disabilities statement: "The University of Texas at Austin provides upon request appropriate academic accommodations for qualified students with disabilities. For more information, contact the Office of the Dean of Students at 471-6259, 471-4641 TTY."