Theory and Applications of Categories, Vol. 1, No. 7, 1995, pp. 146–155.

A FORBIDDEN-SUBORDER CHARACTERIZATION OF BINARILY-COMPOSABLE DIAGRAMS IN DOUBLE CATEGORIES

ROBERT DAWSON

Transmitted by R. J. Wood

ABSTRACT. Tilings of rectangles with rectangles, and tileorders (the associated double order structures) are useful as “templates” for composition in double categories. In this context, it is particularly relevant to ask which tilings may be joined together, two rectangles at a time, to form one large rectangle. We characterize such tilings via forbidden suborders, in a manner analogous to Kuratowski’s characterization of planar graphs.

1. Introduction

A double category, D, is a category object in Cat. (The concept of a double category was first introduced by Ehresmann [3] in 1963.) As such, it can be thought of as consisting of a collection D of objects, a collection D_{h} of horizontal morphisms, a collection D_{v} of vertical morphisms, and a collection D_{□} of double morphisms (“cells”). ⟨D, D_{h}⟩ is a category; so are ⟨D, D_{v}⟩, ⟨D_{h}, D_{□}⟩, and ⟨D_{v}, D_{□}⟩. Thus, the elements of D_{□} have two compositions: the “horizontal” composition which D has as an object of Cat and the “vertical” composition which D has as a category object. We will use juxtaposition to denote the horizontal composition, and a dot to denote vertical composition. In the same way that it is natural to visualize objects and morphisms of a category as dots and arrows (although the “Australian” dual notation has its advantages), it is natural to think of cells as rectangles, with an object at each corner, and an arrow on each edge.

D_{□} is a category under each composition operation. Moreover, these two categories (which share the same morphisms, although not all of the same objects – the domain and codomain functions of one are not the same in general as those of the other) are linked by the middle four interchange axiom (αβ) · (γδ) = (α · γ)(β · δ) whenever the compositions on both sides are defined. In fact, an “object-free” presentation of the theory of double categories may be given in just this way: any collection of cells D with two composition operations {·, ∘}, such that ⟨D, ·⟩ and ⟨D, ∘⟩ are categories, which obeys the middle four interchange axiom, and in which the vertical and horizontal identity operations commute, is a double category. This presentation makes it clear that the theory of double categories has not only the dualities op and co, which reverse horizontal and vertical morphisms respectively, but also the duality trans which interchanges horizontal and vertical.

Supported by a grant from NSERC

Received by the editors 18 August 1995 and, in revised form, 21 September 1995.

Published on 16 October 1995

1991 Mathematics Subject Classification : 18D05, 05B45 .

Key words and phrases: Double categories, tileorders, binary composition, Hasse diagrams, forbidden suborders.

\begin{matrix}c \\ ◯ \end{matrix} Robert Dawson 1995. Permission to copy for private use granted.

Every cell in a double category has a horizontal domain and codomain (“left and right edge”). However, we cannot consider them as structureless “objects”; rather, as they are arrows of the category ⟨D, D_{v}⟩, we must consider their compositions and factorisations. In particular, the question of when a pair of cells in a double category is compatible for horizontal composition is much more complicated than the corresponding question in a (single) category. In a category, either the codomain of f is the domain of g or they are disjoint; in a double category, the right edge of α may intersect the left edge of β in one of several different ways. Some are illustrated in Figure 1; only in the first case is composition possible. Vertical composition, of course, is equally problematic.

α β  α β  α β  α β

Figure 1: Some ways in which two cells can share a boundary

Moreover, performing one composition may make compositions possible which were not previously possible, or render a previously possible composition impossible. In Figure 2, β and δ may be composed, but α cannot be composed with anything; however, if we compose β with γ, then α may be composed with β · γ but δ cannot be composed with anything. Such situations do not arise in ordinary categories.

α  β γ  δ

Figure 2: Cells whose compositions are interdependent

In [1], R. Paré and I showed that if a compatible arrangement of double cells in a double category has a composite, then that composite is unique. That is, there may be a choice of the order in which a composition is performed; but the associativity axioms and the middle four interchange force the final composite reached by each route to be the same. We observed, as part of the motivation for this result, that it is not necessarily true that a rectangular arrangement of double cells can be composed in any way at all. The simplest example of such a diagram is the pinwheel (Figure 3).

In this paper, we will answer the question of when a rectangular diagram in a double category is composable. It is clear, from the definition of a double category, that composability is determined only by the shape of the diagram; no diagram of the form shown

γ α δ ϵ β

Figure 3: The pinwheel configuration

in Figure 3 can be composed directly. (Indirect composition, in which some cells are first factorized, will not be considered here: see [1] for a treatment of this topic.) Therefore, the appropriate structures to consider are the tilings of rectangles by rectangles.

In [2], it was shown that tilings of rectangles by rectangles may be represented by a certain class of double orders ⟨T, ≤, ⪯⟩ where T is the set of tiles, ≤ is the reflexive and transitive relation generated by the pairs A ≤ B such that the right edge of A intersects the left edge of B in more than one point, and ⪯ is the reflexive and transitive relation generated by the pairs A ⪯ B such that the top edge of A intersects the bottom edge of B in more than one point. These double orders are called tileorders; their properties are explored in [2].

1.1. Definition. A tiling of a rectangle is binarily composable if repeatedly replacing two tiles with a common edge by a single tile which is their union can eventually reduce the tiling to a single tile.

An example of a tiling which is not binarily composable is the pinwheel shown in Figure 3. By contrast, the tiling shown in Figure 4 is binarily composable. Note that if we start in the wrong way, say by composing the tiles α_{1} and α_{2} on the top edge, we may reach a dead end. Thus, we might also ask which tilings are randomly binarily composable; that is, which ones do not have any “wrong moves”.

α_{1}  α_{2}  β γ  δ ϵ

Figure 4: A composable configuration

It is clear that any tiling determines a unique tileorder. Moreover, as the information given by a tileorder allows us to determine whether two elements are immediate neighbours, and how the immediate neighbours of an element are ordered, we may consider two tilings to be equivalent if they have the same tileorder. We may therefore call a tileorder (randomly) binarily composable without confusion, should it be determined by a tiling with this property. Composing two tiles in a tiling identifies the corresponding elements in its tileorder; thus instances of binary compositions inside tilings induce double-order-preserving quotient maps between their tileorders. It is traditional to indicate single order relations on finite sets by Hasse diagrams, using points for elements and downwards-pointing arrows for the generating “immediately above” relation. Tileorders, having two order relations, may be indicated using two styles of arrow; we will use solid-shafted arrows a ← b for a ≤ b and dotted-shafted arrows [figure: a; b] for a ⪯ b.

It is easy to show that any tileorder may be so represented using arrows that do not cross: for instance, by realising it as a tiled rectangle, and joining the centers of adjacent tiles by arrows of the appropriate type. Moreover, a diagram so generated will always have the heads of the “vertical” arrows lower than their tails, and the heads of the “horizontal” arrows to the left of their tails. Of course, it would be clearer to use (nearly) vertical arrows to represent the vertical relation, and (nearly) horizontal arrows for the horizontal relation. If, for every ϵ > 0, we may construct a diagram for a tileorder with the orientation of the horizontal arrows within ϵ radians of the x axis, and that of the vertical arrows within ϵ radians of the y axis, we will call that tileorder neat.

1.2. Theorem. A tileorder is neat if and only if it is binarily composable.

There is a well-known theorem of Kuratowski [4] that a graph is non-planar if and only if it contains a subdivision of the complete graph K^{5} on 5 vertices or the complete bipartite graph K^{3,3} on two sets of three vertices. (A graph G is a subdivision of a graph G′ if G′ may be obtained from G by replacing paths by single edges; that is, by binary composition of edges.) In this paper, we shall present an analogous characterization of the binarily-composable tileorders.

1.3. Definition. A pinwheel double order is one of the two configurations

[figure: or; a; c; d; b; e; a; c; d; b; e]

As ≤ and ⪯ are order relations, hence reflexive and transitive, the definition permits two or more elements to be the same, and does not require them to be immediate neighbours. A pinwheel is degenerate if all of its elements are the same; if all of its elements are distinct, it is proper. (In Section 2, we shall show that every pinwheel is of one or the other of these types.)

1.4. Theorem. A tileorder fails to be binarily composable if and only if every sequence of binary compositions eventually yields a tileorder with a proper pinwheel as a sub-double-order.

It is tempting to conjecture the stronger assertion that the binarily composable tileorders are precisely those which do not contain a pinwheel. However, this is not the case, as shown by Figure 5. The pinwheel is present in a sense, but “some assembly is required”, corresponding to Kuratowski’s use of subdivisions of K^{5} and K^{3,3} rather than the graphs themselves.

Figure 5: A noncomposable configuration with no pinwheel

2. Proof of Theorem 1.2

The following lemmas will be understood to include their various duals.

2.1. Lemma. If K is a maximal ≺-chain in a tileorder T, then T_{K} = {t ∈ T : (∃k ∈ K)(t ≤ k)} is a tileorder under the inherited double order.

Proof. A maximal ≺-chain in a double order is a chain of elements a_{0} ≺ a_{1} ≺ ⋯ ≺ a_{n} that cannot be extended to a larger such chain. Maximal <-chains are defined analogously. We say that a double order has the orthogonal maximal chain property (OMCP) if, whenever K is a maximal ≺-chain and L is a maximal <-chain, they have exactly one element in common. If, whenever K and L are maximal ≺-chains with elements k_{1} ≺ k_{2} ∈ K, l_{1} ≺ l_{2} ∈ L, such that k_{1} < l_{1}, k_{2} > l_{2}, there exists x ∈ K ∩ L with k_{1} ≺ x ≺ k_{2}, l_{1} ≺ x ≺ l_{2}, we say that the double order has the ≺-parallel maximal chain property (≺-PMCP). The <-parallel maximal chain property (<-PMCP) is defined similarly. It is shown in Theorem 4 of [2] that a double order is a tileorder if and only if it has the orthogonal and parallel maximal chain properties.

We must therefore show that these properties are inherited by the suborder T_{K}. The ≺-PMCP is obviously inherited, as maximal ≺-chains of T_{K} are also maximal ≺-chains of T. The OMCP and <-PMCP involve maximal <-chains of T_{K}, which may be extended to maximal <-chains of T. In each case, the required intersection certainly occurs in T; it remains to show that the element x at which the intersection occurs is in T_{K}. In the orthogonal case, x is in a maximal ≺-chain of T_{K}, hence in T_{K}. In the <-parallel case, we have x < k_{2} for an element k_{2} of one of the <-chains of T_{K}; thus x itself is in T_{K}. We conclude that T_{K} has all the maximal chain properties, and is a tileorder.

2.2. Lemma. Let a,b be objects in a tileorder. Then at least one of the following holds:

(∃x_{1}, x_{2}) (a ⪯ x_{1} ≤ b, a ≤ x_{2} ⪯ b),
(∃x_{1}, x_{2}) (a ⪰ x_{1} ≤ b, a ≤ x_{2} ⪰ b),

(∃x_{1}, x_{2}) (a ⪯ x_{1} ≥ b, a ≥ x_{2} ⪯ b),
(∃x_{1}, x_{2}) (a ⪰ x_{1} ≥ b, a ≥ x_{2} ⪰ b).

Proof. Construct a tiled rectangle whose tileorder is T; and let A,B be the rectangles represented by a,b. Let X_{1} be the tile which contains the intersection of a vertical line through the center of A and a horizontal line through the center of B, while X_{2} is the tile containing the intersection of a horizontal line through the center of A and a vertical line through the center of B. These are represented by objects x_{1},x_{2} in T, which clearly have the desired relations to a and b.

2.3. Lemma. If the objects of a tileorder T can be partitioned into two nonempty subsets T_{1} and T_{2}, each connected under the double order structure inherited from T, such that no object of T_{1} is an immediate vertical neighbour of an object of T_{2}, then the restrictions ⟨T_{1}, ≤, ⪯⟩ and ⟨T_{2}, ≤, ⪯⟩ are themselves tileorders; and if T_{1} and T_{2} are binarily composable, so is T.

Proof. No object of T_{1} is above or below any object of T_{2}, and T is connected, so some object of T_{1} is (without loss of generality) to the left of some object of T_{2}. Consider the set R of objects in T_{1} with no right neighbour in T_{1}.

Let r_{1},r_{2} be elements of R. By Lemma 2.2 there exist objects x_{1}, x_{2} ∈ T such that (without loss of generality) r_{1} ⪯ x_{1} ≤ r_{2} and r_{1} ≤ x_{2} ⪯ r_{2}. As no object of T_{1} has any vertical neighbours in T_{2}, x_{2} ∈ T_{1}; but as r_{1} has no right neighbour in T_{1}, we must have r_{1} = x_{2} ⪯ r_{2}. As for every two elements r_{1}, r_{2} of R, we have either r_{1} ⪯ r_{2} or r_{1} ⪰ r_{2}, R is a ≺-chain. Moreover, as the rightmost upper and lower neighbours of any element of R are themselves in R, R is a maximal chain in ⟨T, ≺⟩ . By Lemma 2.1, ⟨T_{1}, ≤, ⪯⟩ is a tileorder; by a similar argument, so is ⟨T_{2}, ≤, ⪯⟩ . If T_{1} and T_{2} are binarily composable, their compositions are rectangles with a common vertical edge, and may themselves be composed.

We are now ready to prove Theorem 1.2. Suppose that a tileorder T is the composition of neat tileorders, without loss of generality T_{1}·T_{2}. We may construct neat Hasse diagrams for T_{1} and T_{2}, and scale them to a vertical range of (−ϵ, ϵ). If we translate the diagram of T_{1} so that all of its x-coordinates of every point are less than -1, and similarly position the diagram of T_{2} so that all of its x-coordinates are greater than 1, then the horizontal arrows connecting the two subdiagrams must make an angle of less than ϵ with the horizontal axis. Thus T is neat; and so, by induction, are all binarily composable tileorders.

To show that every neat tileorder is binarily composable, we will again use induction. Assume as an inductive hypothesis that T is a neat tileorder with n objects, and that every neat tileorder with fewer objects than T is binarily composable. Construct a Hasse diagram for T in which every arrow is within an angle of 1/2n of the appropriate axis. Without loss of generality, assume that the longest arrow of this diagram is an arrow of the horizontal ordering, of length 1. By rotating the entire diagram through an angle of at most 1/2n, it may be made parallel with the x-axis. After this rotation, the arrows of the vertical ordering (which have length ≤ 1) must still make an angle of less than 1/n with the y-axis; so the x-coordinates of the domain and codomain of any vertical arrow differ by at most sin(1/n) < 1/n. Thus, if there is a sequence of distinct nodes (a_{i} : i = 1, …, m) such that for each i, a_{i} ≺ a_{i+1} or a_{i} ≻ a_{i+1}, the x-coordinates of a_{1} and a_{m} must differ by at most (m − 1)/n, which, as m ≤ n, is less than 1. We conclude that the domain and codomain of the longest horizontal arrow are in different components of the vertical order ⟨T, ⪯⟩ . However, if the objects of a tileorder can be partitioned into two subsets, joined only by horizontal arrows, then by Lemma 2.3 those subsets are themselves tileorders. As they are neat, and have fewer than n elements, by the inductive hypothesis they are composable; and so again by Lemma 2.3, T is also composable.

3. Proof of Theorem 1.4

Theorem 1.4 may be subdivided into the two following propositions:

3.1. Proposition. No tileorder which contains a pinwheel is binarily composable.

3.2. Proposition. Every nontrivial tileorder contains either a binarily composable pair or a pinwheel.

3.3. Lemma. [Strong Antisymmetry] If a ⪯ b and a ≤ b in a tileorder, then a = b.

Proof. see ([2], §3).

3.4. Lemma. Every pinwheel is either degenerate or proper.

Proof. Applying antisymmetry and strong antisymmetry (Lemma 3.3), we can show that if any two elements are the same, then all of them are. For instance, if a = b, then b ≥ d and a ⪰ d, so a = b = d; by a similar argument, c=d and d=e (see Figure 6).

[figure: a; c; d; b; e]

Figure 6: A pinwheel about to collapse

To prove Proposition 3.1, we will show that if a tileorder ⟨T, ≤, ⪯⟩ contains a proper pinwheel, and if another tileorder ⟨T′, ≤′, ⪯′⟩ is obtained from the first by composition, then the second tileorder also contains a proper pinwheel. The proposition follows immediately from this; and it suffices to prove this for a single composition.

As observed in the Introduction, instances of binary compositions in tilings induce double-order-preserving quotient maps between their tileorders. Any double-order-pre-serving map between tileorders must preserve pinwheels. Moreover, at most two of the five elements of a proper pinwheel can be identified by a single composition; so the image of the pinwheel cannot be degenerate. Thus, by Lemma 3.4, it is proper.

Now we prove Proposition 3.2. Suppose that some tileorder contained neither a composable pair nor a pinwheel. Then there would be a minimal such counterexample (that is, one that contained no other properly.) Take ⟨T, ≤, ⪯⟩ to be such, and let {T_{i}} be any realisation of it as a tiling of the unit square S = [0, 1] × [0, 1] by rectangles T_{i} .

Define n(y) to be the number of (closed) rectangles of this tiling which contain points (x, y) for some x ∈ [0, 1]. (If all the points with that y-coordinate in a rectangle are shared with another rectangle, let each contribute 1/2 rather than 1 to n(y); this is not truly important, but is convenient.) By reversing the square (and dualising the tileorder) if necessary, we may always make n(0) ≥ n(1); without loss of generality, let us assume this to be so. Consider the lowest rectangle touching the lowest edge of S. Let its height be h. As no binary compositions are possible, it must be strictly lower than its neighbours to the left and right, and have two or more upper neighbours; therefore n(h + ϵ) > n(0) ≥ n(1). It follows that there must be some horizontal edge at which n(y) decreases with increasing y. At such an edge, there must be a vertex at which 3 rectangles meet in a ⊤ configuration. Consider such a vertex, v, whose height is minimal among all such vertices. Here, two adjacent rectangles (C and D, in Figure 7) have the space immediately above their shared upper vertex filled by one rectangle A.

[figure: F; E; C; D; A; B; v; w]

Figure 7: A pinwheel in a non-composable tileorder

As C and D are assumed not to be binarily composable, it follows that their lower edges may not be collinear. One of them (without loss of generality C, and on the left) extends lower than the other. Neither of them can have more than one lower neighbour (by our assumption that the lowest ⊤ is at v). Let those neighbours be F and E respectively. They must be strictly wider than C and D, as otherwise a vertical binary composition would be possible. Extend the right edge of E upwards (dashed in Figure 7). This meets the rightwards extension of the upper edges of C and D (dotted in Figure 7) at the point w. The line segment from the upper right corner of D to w must intersect the interior of a rectangle B; otherwise w and the lower right corner of D would be the corners of either a single rectangle of the tiling (composable with D) or a proper tiled subrectangle. In either case, our assumptions would be violated. However, this forces B to be to the right of D and A, and above E. This completes a pinwheel, with corners A, B, C, E and center D, and contradicts our hypotheses.

4. Random binary composability

When an object has a property which asserts that a certain multiple-stage task can be completed, it is often interesting to ask whether that completion requires strategy, or whether a solution may be obtained, without backtracking, by any algorithm that avoids breaking the obvious rules. For example, if a graph is Eulerian from a given vertex, a properly-planned circuit starting at that vertex will visit every vertex once. If it is randomly Eulerian from that vertex, though, the circuit need not be planned; until the circuit is completed, there will always be an unvisited vertex accessible. Similarly, we may ask when a tiling is randomly binarily composable. Using the results derived above, we get the following characterization.

4.1. Definition. A factorized pinwheel is a configuration containing five (possibly trivial) rectangular subtileorders, such that if each is replaced by a single tile a pinwheel results.

4.2. Proposition. A tiling is randomly binarily composable if and only if it does not contain a factorized pinwheel.

Proof. Clearly, if a tiling does contain five subrectangles (trivial or not) in a pinwheel, and if all can be composed, then any sequence of compositions that begins by composing the elements of those subrectangles will create a pinwheel. If any of the subrectangles cannot be composed, then it contains a pinwheel itself. In either case, the pinwheel blocks the composition of the original tiling. Conversely, if there is no such configuration, then after any number of compositions, no pinwheel exists. Therefore, by Proposition 3.2, a further composable pair exists (unless the tiling has been completely composed to a single tile); so by induction the composition may be completed.

Acknowledgement

I would like to thank Robert Paré for valuable discussions on this and related topics, and the anonymous referee for several most useful suggestions on the presentation.

References

[1] R. Dawson and R. Paré, General Associativity and General Composition for Double Categories, Cahiers de Topologie et Géométrie Différentielle Catégoriques 34 (1993) 57-79

[2] R. Dawson and R.Paré, Characterising Tileorders, Order 10 (1993), 111-128

[3] C. Ehresmann, Catégories Structurées, Ann. Sci. Ecole Norm. Sup. 80 (1963), 349-425

[4] Kuratowski, K., Sur la problème des courbes gauches en topologie, Fund. Math. 15 (1930) 271-283

Dept. of Mathematics and Computing Science Saint Mary’s University Halifax, Nova Scotia Canada B3H 3C3

Email: rdawson@husky1.stmarys.ca

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/1995/v1n7.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/gopher/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi and Postscript format. Details will be emailed to new subscribers and are available by WWW/gopher/ftp. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and LaTEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at URL http://www.tac.mta.ca/tac/ or by anonymous ftp from ftp.tac.mta.ca in the directory pub/tac/info. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@triples.math.mcgill.ca Lawrence Breen, Université de Paris 13: breen@dmi.ens.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, University of Genoa: carboni@vmimat.mat.unimi.it P. T. Johnstone, University of Cambridge: ptj@pmms.cam.ac.uk G. Max Kelly, University of Sydney: kelly m@maths.su.oz.au Anders Kock, University of Aarhus: kock@mi.aau.dk F. William Lawvere, State University of New York at Buffalo: mthfwl@ubvms.cc.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.ruu.nl Susan Niefield, Union College: niefiels@gar.union.edu Robert Paré, Dalhousie University: pare@cs.dal.ca Andrew Pitts, University of Cambridge: ap@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@charlie.math.unc.edu Ross Street, Macquarie University: street@macadam.mpce.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca R. W. Thomason, Université de Paris 7: thomason@mathp7.jussieu.fr Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Sydney: walters b@maths.su.oz.au R. J. Wood, Dalhousie University: rjwood@cs.da.ca