nLab
tileorder

Contents

Idea

A tileorder is a double order, i.e. a set TT equipped with two partial orders \le and \sqsubseteq, which can be realized by a dissection of a rectangle into finitely many subrectangles, the subrectangles being the elements of TT, in such a way that aba\sqsubseteq b iff aa “lies below” bb, while aba\le b iff aa “lies to the left of” bb. 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).

Definition

Suppose given a dissection of a rectangle into finitely many subrectangles. Define TT to be the set of subrectangles, and for a,bTa,b\in T write aba\le b if there exists a finite list a=x 0,x 1,,x n=ba= x_0, x_1, \dots, x_n = b such that for each ii, the right edge of x ix_i intersects the left edge of x i+1x_{i+1} in more than one point. Define aba\sqsubseteq b similarly using top and bottom edges instead of left and right. Clearly \le and \sqsubseteq are partial orders.

A set TT equipped with two partial orders \le and \sqsubseteq (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.)

Characterizations

As proven by Dawson and Paré, tileorders can be characterized in purely combinatorial terms in a couple of interesting ways.

Using maximal chain properties

A double order TT is said to have the \sqsubset-parallel maximal chain property if whenever KK and LL are maximal \sqsubseteq-chains in TT, and we have k 1,k 2Kk_1,k_2\in K and l 1,l 2Ll_1,l_2\in L with k 1k 2k_1 \sqsubset k_2, k 1l 1k_1 \le l_1, and l 2k 2l_2 \le k_2, then there exists an eKLe\in K\cap L such that k 1ek_1\sqsubset e, l 1el_1\sqsubset e, ek 2e\sqsubset k_2, and el 2e\sqsubset l_2. In other words, two maximal \sqsubseteq-chains cannot “swap places” in the \le-order without intersecting.

Dually, we define the <\lt-parallel maximal chain property.

A double order TT is said to have the orthogonal maximal chain property if every maximal \le-chain intersects every maximal \sqsubseteq-chain exactly once.

Theorem

A double order is a tileorder iff it has both parallel maximal chain properties and the orthogonal maximal chain property.

Using local configuration structure

A double order is strongly antisymmetric if two unequal elements are never related (in either direction) by both <\lt and \sqsubset. That is, if aba\neq b, then at most one of a<ba\lt b, b<ab\lt a, aba\sqsubset b, and bab\sqsubset a holds.

A double order is rectangular if c.(acb)\exists c.(a\sqsubseteq c \le b) iff d.(adb)\exists d.(a\le d \sqsubseteq b), and similarly c.(acb)\exists c.(a\sqsubseteq c \ge b) iff d.(adb)\exists d.(a\ge d \sqsubseteq b).

A double order is total if for any a,ba,b, there exists a cc such that either acba\sqsubseteq c \le b, or acba\sqsubseteq c \ge b, or bcab \le c \sqsubseteq a, or bcab\ge c \sqsubseteq a.

A double order has the first \sqsubset-orthogonal butterfly factorization property if given a,b,c,da,b,c,d with cac\sqsubseteq a, cbc\sqsubseteq b, dbd\sqsubseteq b, and dad\le a, there exists an ee with cebc\sqsubseteq e \sqsubseteq b and dead\le e \le a. The second such property is defined by replacing \le by \ge, but not changing \sqsubseteq. The <\lt-orthogonal such properties are defined by switching the roles of \sqsubseteq and \le.

A double order has the \sqsubset-parallel butterfly factorization property if given a,b,c,da,b,c,d with cac\sqsubseteq a, bcb\le c, dbd\sqsubseteq b, and dad\le a, there exists an ee with becb\le e \le c and dead\le e \le a. The <\lt-parallel such property is defined by switching the roles of \sqsubseteq and \le.

Theorem

A double order is a tileorder iff it is strongly antisymmetric, rectangular, total, and has all the orthogonal and parallel butterfly factorization properties.

References

  • Dawson and Paré, “Characterizing tileorders”

Revised on April 8, 2010 05:07:53 by Mike Shulman (75.3.151.132)