Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

December 26, 2022

Guillotine Partitions and the Hipparchus Operad

Posted by John Baez

If you dissect a square into nn similar rectangles, what proportions can these rectangles have? Folks on Mathstodon figured this out for n7n \le 7, and I blogged about it here recently. But I was left feeling that some deeper structure governed this problem.

Various people on Mathstodon, including Steven Stanicki, David Eppstein and Rahul Narain, convinced me of the importance of a certain class of dissections called ‘guillotine partitions’. I started suspecting that these were connected to an operad I once blogged about here: the ‘Hipparchus operad’. And last night I put some of the pieces together… though there is still more to do.

Last night I had insomnia, worrying about my aunt in a nursing home. To lull myself to sleep I thought about math. I had an idea about guillotine partitions.

In a ‘guillotine partition’ of a square you repeatedly slice off and remove rectangular pieces by cutting vertically or horizontally all the way through what’s left:

There are 6 types of guillotine partition where you make 2 cuts, so we say the 2nd Schröder number is 6:

The first few Schröder numbers S n S_n go like this:

S 0=1 S_0 = 1 S 1=2 S_1 = 2 S 2=6 S_2 = 6 S 3=22 S_3 = 22

etc. For example, S 3=22S_3 = 22 since there are 22 types of guillotine partition of a square with 3 cuts, as shown below:

We can arrange it so the cuts always go through equally spaced points lying on a diagonal line. This is a cheap way to make the idea of ‘type’ precise: we only count guillotine partitions with this property.

(It’s probably better to define a ‘type’ of guillotine partition as an equivalence class under a certain equivalence relation. Briefly: if you start with a guillotine partition, and move a horizontal cut up or down without it hitting another horizontal cut, or move a vertical cut right or light without it hitting another vertical cut, you get a guillotine partition of the same type. The trick with equally spaced points is just a way to choose one representative guillotine partition of each type.)

You can read more about the Schröder numbers here:

If we demand that the first cut be vertical we get half as many guillotine partitions… except when there are no cuts at all. This gives the ‘little Schröder numbers’:

x 0=1 x_0 = 1 x 1=1 x_1 = 1 x 2=3 x_2 = 3 x 3=11 x_3 = 11

etc. For example if we take the guillotine partitions with 3 cuts, and cross out those where the first cut is horizontal, we’re left with 11 of them:

You can read about the little Schröder numbers here:

The little Schröder numbers are now also called ‘Schröder–Hipparchus numbers’, because sometime between 50 and 120 AD Plutarch wrote:

Chrysippus says that the number of compound propositions that can be made from only ten simple propositions exceeds a million. Hipparchus, to be sure, refuted this by showing that on the affirmative side there are 103,049 compound statements….”

This was utterly mysterious until 1994, when David Hough, a math grad student, realized that 103,049 is the 9th little Schröder number!

Why was Hipparchus messing around with the little Schröder numbers around 150 BC?

It turns out the (n1)(n-1)st little Schröder number is also the number of planar trees with nn leaves where each node has 0, or 2, or 3, or 4, or 5, etcetera, children. Anything but one child!

For example this tree with 8 leaves is one of 4279 such trees, since the 7th little Schröder number, x 7x_7, is 4279:

Hipparchus was probably studying such trees with 10 leaves! There are 103,049 of them.

But wait! Why is the nth little Schröder number both:

the number of types of guillotine partition of a square with nn cuts, where the first cut is vertical

and

the number of planar trees with n+1n+1 leaves where each node has any number of children except 1

?

This is what I figured out in my bout of insomnia, after connecting little Schröder numbers to guillotine partitions.

Here’s a better way to phrase the question: why is

the number of types of guillotine partition of a square into nn rectangles, where the first cut is vertical

equal to

the number of planar trees with nn leaves where each node has any number of children except 1

?

There’s a nice bijective proof. Here’s how you can set up a 1-1 correspondence between such trees and such types of guillotine partitions:

Each node of your tree corresponds to a rectangle. The top node corresponds to the whole square you are partitioning. Then, when a node has nn children, you cut its rectangle into nn smaller rectangles using parallel lines any way you want. These are the node’s children.

As you work down the tree you first cut with vertical lines, then horizontal, then vertical, etc.

So, the first cuts are always vertical!

Using this correspondence, types of guillotine partitions of a square into nn rectangles where the first cut is vertical correspond to trees with nn leaves where each node that’s not a leaf has at least two children!

Almost a decade ago, I noticed that such trees are also operations in the free operad on one operation of arity 2, one operation of arity 3, etc. You could say this is the operad for ‘unbiased magmas’. I wrote about this here, and I called it the ‘Hipparchus operad’:

This blog post was a ‘meta-April-fool’s joke’, since it was strange, with a few jokes thrown in, but true in all important respects.

The Hipparchus operad has nice connections to other branches of math, as discussed in comments. For example the little Schröder numbers count the trees appearing when you barycentrically subdivide Stasheff’s associahedra! There are 11 trees here:

Each of these trees gives a type of guillotine partition of the square where the first cut is vertical.

So, there’s a lot to play with here!

I’m hoping this will help us understand this problem:

This only works for similar rectangles forming a guillotine partition of the square. But those are very interesting! For those, I think we just need to take a tree of the sort I’m describing, and label each leaf with ‘vertical’ or ‘horizontal’, to say whether that rectangle is tall and skinny, or short and squat. But some more thought is required.

This is the sort of thing that happens sometimes when I try to fall asleep by diverting my mind away from more unpleasant subjects. Does something like this happen to you too?

Anyway, I called my aunt today and she’s actually doing okay. I forgot to do it yesterday, on Christmas day. Aargh!!!

Sometimes I think pure math is just an elaborate trick to avoid confronting reality.

Acknowledgements

The pictures of guillotine partitions were drawn by Robertd and put on Wikicommons under a Creative Commons Attribution 3.0 Unported license. The picture of a tree is from Etienne Ghys’ article Quand beaucoup de courbes se rencontrent. The picture of a barycentrically subdivided Stasheff pentagon is from Tom Leinster’s book Higher Operads, Higher Categories.

Posted at December 26, 2022 9:42 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3436

3 Comments & 0 Trackbacks

Re: Guillotine Partitions and the Hipparchus Operad

In contrast to Guillotines, one might want to consider “Squared” Squares which, of course, can then be sub-tiled any way you like, and have been a Thing People Study for about a century; they have something to do with Kirchoff’s Rules, too, but I can’t remember the details. (I’ve been a welder fabricator for a year now and have much much less free time than I used to… but it pays reasonably!) here is one page in a website collecting such tilings

Posted by: Jesse C. McKeown on January 1, 2023 5:00 PM | Permalink | Reply to this

Re: Guillotine Partitions and the Hipparchus Operad

Thanks! Here’s a good overview of squaring the square and its connection to Kirchoff’s laws and resistor networks:

There are definitely connections to the current problem, but I haven’t gotten the details all worked out. I want to say more about this someday!

Posted by: John Baez on January 4, 2023 12:05 AM | Permalink | Reply to this

Re: Guillotine Partitions and the Hipparchus Operad

If you’re interested, here’s a 3D version of the Schroeder rectangulations (aka 3D guillotine partitions): https://robertdickau.com/schroederslices3d.html

Posted by: Robertd on January 29, 2024 12:32 AM | Permalink | Reply to this

Post a New Comment