Previous Results and Research Plans

Finite Ordered Sets: Structural Complexity and Ordered Sets

It has been a long-standing problem to ``characterize'' those finite ordered sets for which every order-preserving self map has a fixed point, beginning with the elegant lattice-theory results of Knaster, Tarski, and Davis. More recently, an algorithmic approach has been important, such as with the idea of dismantlability. A satisfying characterization of finite structures is often associated with a polynomial-time algorithm; our result shows that this may not be possible.
Theorem It is NP-complete to determine if a given ordered set has an order-preserving fixed-point-free self-map.
Some interesting problems remain, for instance:
Is there a natural self-computation for FPFMAP?
Applying a graph theoretic result [A. Lubiw 1981], it can be shown, even for length one, that it is NP-complete to determine if a given ordered set has a fixed-point free automorphism. We resolve the complexity of FPFMAP with a construction of length six, yet FPFMAP is polynomial for ordered sets of length one. It is of interest, therefore, to resolve the complexity of FPFMAP for ordered sets of length three, in particular. At about the same time as Lubiw's result, topologists and combinatorists became interested in the following question also concerning the structural complexity of order:
Are two given order-preserving maps homotopic?
I will continue investigation into the above problems using constructive methods and the current interactive proof techniques.

Infinite Ordered Sets: Chains, Antichains, and Partitions

Coloring Maximal Chains and Antichains

The most commonly studied substructures of an ordered set are its chains and antichains. A cutset is a subset of an ordered set that meets every maximal chain (dually, a fibre is a subset that meets every maximal antichain). Given an ordered set $P$, one can ask how large a cutset or fibre must be; for instance are $|P|/2$ elements necessary? From this question, one is led to consider 2-colorings for which every maximal chain (or antichain) receives both colors. From this viewpoint, one is reminded of Ramsey theory, and, in fact, Ramsey-type arguments play a strong role. Let us state the problem in a slightly more general fashion:
Given an ordered set, how many colors are needed so that each maximal chain (or antichain) receives at least two?
Early results [Duffus, Rödl, Sauer, and Woodrow, 1992] used an Erdös-Rado Ramsey theorem, thereby producing rather large examples. We have made considerable progress in finding smaller and more natural examples by exploiting properties of cartesian products of chains with gaps [D. Duffus, T. Goddard 1995 (accepted), 1996 (preprint)]:
Theorem There is a two-dimensional ordered set of cardinality $\aleph_1$ for which every subset or complement thereof contains a maximal chain. This holds even in ZFC.
Moreover, these techniques can be applied to the dual question to give the first results for 2-coloring maximal antichains in infinite ordered-sets:
Theorem There is a two-dimensional ordered set of cardinality $2^{2^{\aleph_0}}$ that must be colored with infinitely many colors before no monochromatic maximal antichains are present.
Still, much remains; for instance, is there an ordered set of size $\aleph_1$ for which every finite coloring leaves monochromatic maximal chains?

Aharoni's Conjecture

Dilworth's theorem is perhaps the best-known order-theoretic result, a generalization of which is the Greene-Kleitman theorem. When one considers the structural nature of such results, one is led to questions such as the following, raised by Aharoni and Korman:
Given an ordered set with no infinite antichain, does there exist an antichain partitition and a chain so that the chain meets each member of the partition?
This problem is believed to be very challenging; our positive result holds in a rather special situation.
Theorem If $C$ is any chain and $P$ is any finite ordered set, then $C \times P$ can be partitioned into antichains in such a way that there is a common chain meeting each of them.
I will continue by seeking results in other special cases, as the full problem has a strong connection with the König Duality theorem (so called by Aharoni and Korman), a deep result which is the product of a substantial body of work.

Pedagogy: Mathematics Classrooms On-line

How can networked computers improve mathematics education?
The World Wide Web is rapidly becoming a fixture in the academic and commercial spheres, however few resources exist to support the mathematics education of secondary and college students. We must experiment with hypertext and electronic interaction to see how they can enhance learning.

Currently [ http://sirius.mathcs.emory.edu/~goddard/math112] we have a message board for the class, along with assignment updates, the class syllabus, and even final grades. The system is very flexible. The main problem lies with making it approachable for students with little or no experience with computers; this will require progressive refinement.