Research Statement


Barry Allen Balof


My main research focus has been in partially ordered sets. For a set, such as the integers, we have a notion of what it means for one integer to be `less than' another. This definition is trichotomous, that is, given x and y we have either x=y, x < y or y < x. The integers are hence totally ordered or linearly ordered. If, however, we redefine what we mean by `less than', some interesting possibilities arise. If we say that a < P b if and only if a divides b and a ¼ b, we lose the trichotomy we had in our original definition. Indeed, 2\not < 3, 3\not < 2 and 2 ¼ 3. This is an example of a partial ordering on the set of integers, and we generalize the definition as follows.
A Partially Ordered Set, or poset is a set X together with a binary relation P that is asymmetric, irreflexive, and transitive. We denote the partialy ordered set, or poset by the pair (X, P). One will often denote (x,y) ‘ P by x < y for x, y ‘ X. If neither x < y nor y < x in a poset, we say that x and y are incomparable and write x||y. A geometric representation, in its most general form, assigns a geometric figure to each element of the set and imposes relations on the figures that correspond to relations in the ordered set. Given a certain type of geometric representation, we have an associated class of geometric orders, that is, the class of all orders that posess such a geometric representation.
The earliest notions of geometric orders are those of interval orders, first studied formally by Fishburn and Mirkin independently. In an interval representation, we assign each element of our ordered set an interval on the real line, with x < y in (X, P) if and only if the interval corresponding to x lies entirely to the left of the interval corresponding for y. An interval order cannot contain four elements a, b, c, d with a < b, c < d, but a\not < d and c\not < b. Fishburn and Mirkin proved that this necessary condition is also sufficient, and in so doing, characterized interval orders.
A natural extension of the interval order question gives rise to the notion of a semiorder, an interval order in which all intervals have the same length. A semiorder has the same four element restriction as do interval orders, but it has the further restriction that it cannot contain four elements a, b, c, d with a < b < c and d incomparable to all three. Scott and Suppes proved that, once again, the necessary condition is also sufficient, thus characterizing semiorders.
An expansion on the idea of the interval order into two dimensions gives us trapezoid orders, first defined by Larry Langley in 1993. In this geometric representation, all elements of the poset are assigned trapezoids, all of which have their bases on two predetermined parallel baselines. One element is less than another in the poset if and only if the two trapezoids don't intersect and the trapezoid for the first lies entirely to the left of that for the second. Stephen Ryan's doctoral thesis defines and classifies many types two dimensional geometric representations of orders including trapezoid orders and triangle orders (a representation on two parallel baselines where each object is a triangle and intersects one of the baselines in an interval, the other in a point.
Habib, Möhring, and Kelly further generalized the idea of geometric representations by introducing tube dimension, a representation of an ordered set in n dimensions, where the geometric objects lie in the convex hull formed by n mutually parallel baselines. Josh Laison further refined this notion by introducing (n, i, f)-tube orders, where all the geometric objects are convex polytopes, each one intersecting i of the n baselines in intervals, and each posessing f free vertices which don't lie on any baseline. The previous heirarchy of ordered sets fits into this notion. An interval order is just a (1,1,0) tube order, a trapezoid order is a (2,2,0) tube order, a triangle order is a (2,1,0) order, and so on.
It was here that my own research began. My thesis addresses two main questions dealing with (n,i,f) tube orders.

1. Unit versus Proper: A unit representation of an (n,i,f)-tube order is one in which all the polytopes have the same volume; a unit order is one with a unit representation. A proper representation is one in which no polytope properly contains another; similarly, a proper order is one with a proper representation. It is clear, geometrically that any unit order has a proper representation. I seek to find out which classes of proper ordered sets have unit representations. It is a classic theorem that every proper interval order has a unit interval representation and vice versa. The corresponding statement for trapezoid orders is false. In my thesis, I find examples, both finite and infinite of proper but not unit (2,0,1) tube orders (the so-called free triangle orders)

2. Comparability Invariance: The comparability graph of an ordered set has the elements of the set as vertices and an edge between every pair of comparable elements. Each transitive orientation of this graph will give rise to an ordered set, possibly different than the original. A property of an ordered set is said to be a comparability invariant if every orientation of a comparability graph for an ordered set having that property has that property as well. In my thesis, I examine whether being a unit triangle order, a free triangle order, or a unit free triangle order is a comparability invariant.

In addition, I developed a new class of (2,0,1) tube orders by placing further restrictions on the free vertices. These constrained triangle orders arose out of trying to draw (3,0,0)-tube orders in 3D space. I've addressed the unit and proper questions for constrained triangle orders, as well as examples of sets that do not posess such a representation.


There is a plethora of open questions connected to the (n,i,f) tube orders that I seek to continue work on in the coming years. Further classification of the (n,i,f) tube orders with minimal separating examples between various classes and classification theorems like those for interval orders and semiorders. I believe that our method for constructing a non-unit free triangle order will extend to higher dimensions, so work there could prove fruitful. I'd like to find a method that will work in solving all the comparability invariance questions for the (n,i,f) tube orders.
The question of comparability invariance leads to other questions in Graph Theory. The origins of the theory behind interval orders were first graph theoretic in nature, taken from the topic of intersection graphs. While the graph theoretic questions gave the impetus for the study of the ordered sets, their questions further generalize the idea of geometric intersections. I continue to be interested in these questions, particularly in the generalizations of interval graphs currently being researched at the University of Colorado.
Another largely unexplored area surrounding these orders is that of recognition. At this time, it is unknown whether there is a polynomial time algorithm to recognize whether an ordered set is an (n,i,f) tube order for n „ 2, or even whether such a problem is NP-complete. During my last year of school I hope to lay the groundwork necessary to obtain some of these results by studying general complexity theory and algorithms. Some of the two dimensional orders lack any type of recognition algorithm whatsoever, these problems seem quite approachable.


Another area of mathematics in which I have a vested interest is Algebraic Combinatorics, specifically in symmetric functions and representation theory. I have studied with Rosa Orellana while at Dartmouth. I found her course on symmetric functions quite engaging and motivating to look for unsolved problems in these areas. I ran a seminar during the fall of my third year of graduate school where we read Bruce Sagan's introductory book on the representation theory of the symmetric group, and began work reading about representation theory of Lie Groups and its connection to partition theory. Additionally, we ran another seminar where we read a paper of Mercedes Rosas on the computation of Kronecker Coefficients. This term we hope to continue our work combining representation theory and symmetric functions by working on some open questions in that area in our seminar.


I find combinatorics, and ordered set theory in particular, to be quite tractable to the inquisitive young mathematician without a great deal of background work necessary to tackle the deep questions. I therefore feel that the material is quite appropriate for undergraduate research, and am excited about making these opportunities available to my students as my career continues. I have long been an advocate for increasing the opportunites for undergraduates to do research in mathematics. As I started my career, I found that opportunities were sparse. I was fortunte to have the strong guidance of Professors John Watkins and Fred Tinsley at Colorado College and Gary Sherman at Rose-Hulman Institute of Technology. In addition, my own advisor Ken Bogart has worked with undergraduates during my time here, and has even let me take over in guiding such projects during his sabbatical terms. I hope to maintain strong ties to the undergraduate population by providing them with research opportunities and guidance throughout my career.

File translated from TEX by TTH, version 3.38.
On 14 Oct 2003, 10:43.