A tileorder is a double order, i.e. a set equipped with two partial orders and , which can be realized by a dissection of a rectangle into finitely many subrectangles, the subrectangles being the elements of , in such a way that iff “lies below” , while iff “lies to the left of” . Interestingly and importantly, such orders can also be characterized in purely combinatorial, and effectively verifiable, terms.
Such orders are of interest in double category theory, since these are the arrangements of 2-cells in a double category which could potentially be composed (although in a general double category, not all of them can actually be composed).
Suppose given a dissection of a rectangle into finitely many subrectangles. Define to be the set of subrectangles, and for write if there exists a finite list such that for each , the right edge of intersects the left edge of in more than one point. Define similarly using top and bottom edges instead of left and right. Clearly and are partial orders.
A set equipped with two partial orders and (a priori, unrelated) is called a double order. A double order which arises in this way from a rectangle dissection is called a tileorder.
Todd: Maybe I’m missing what you mean by “dissection”, but off the bat it looks like you are allowing the “pinwheel” as a possible dissection (I hope it is clear what the pinwheel is; Dawson discusses it in one of his papers), but this is the kind of configuration not interpretable in double categories.
Mike Shulman: Yes, we are allowing the pinwheel, even though it is not always composable in a double category. That’s what I meant to imply above by
arrangements of 2-cells in a double category which could potentially be composed (although in a general double category, not all of them can actually be composed)
but maybe that isn’t sufficiently clear. The notion of tileorder is purely geometric/combinatorial, and you then have to ask which tileorders are composable in a double category (essentially, all that don’t contain a pinwheel). (BTW, a picture of the pinwheel can be found here.)
As proven by Dawson and Paré, tileorders can be characterized in purely combinatorial terms in a couple of interesting ways.
A double order is said to have the -parallel maximal chain property if whenever and are maximal -chains in , and we have and with , , and , then there exists an such that , , , and . In other words, two maximal -chains cannot “swap places” in the -order without intersecting.
Dually, we define the -parallel maximal chain property.
A double order is said to have the orthogonal maximal chain property if every maximal -chain intersects every maximal -chain exactly once.
A double order is a tileorder iff it has both parallel maximal chain properties and the orthogonal maximal chain property.
A double order is strongly antisymmetric if two unequal elements are never related (in either direction) by both and . That is, if , then at most one of , , , and holds.
A double order is rectangular if iff , and similarly iff .
A double order is total if for any , there exists a such that either , or , or , or .
A double order has the first -orthogonal butterfly factorization property if given with , , , and , there exists an with and . The second such property is defined by replacing by , but not changing . The -orthogonal such properties are defined by switching the roles of and .
A double order has the -parallel butterfly factorization property if given with , , , and , there exists an with and . The -parallel such property is defined by switching the roles of and .
A double order is a tileorder iff it is strongly antisymmetric, rectangular, total, and has all the orthogonal and parallel butterfly factorization properties.