{"id":1673,"date":"2015-06-15T01:00:11","date_gmt":"2015-06-15T01:00:11","guid":{"rendered":"http:\/\/blogs.ams.org\/visualinsight\/?p=1673"},"modified":"2016-07-13T01:23:29","modified_gmt":"2016-07-13T01:23:29","slug":"lattice-of-partitions","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/visualinsight\/2015\/06\/15\/lattice-of-partitions\/","title":{"rendered":"Lattice of Partitions"},"content":{"rendered":"
\n
\"Lattice<\/a>

Lattice of Partitions of a 4-Element Set – Tilman Piesk<\/p><\/div>\n<\/div>\n

This picture by Tilman Piesk<\/a> shows the 15 partitions of a 4-element set, ordered by refinement. Coarser partitions are connected to finer ones by lines going down. In the ‘coarsest’ partition, on top, all 4 elements are in the same subset. In the ‘finest’ one, on bottom, each of the 4 elements is in its own subset.<\/p>\n

A partition<\/a> of a set $S$ is a way of writing it as a disjoint union of nonempty subsets called blocks<\/b>. There is a natural 1-1 correspondence between partitions $S$ and equivalence relations on $S$, so the two concepts are just different ways of thinking about the same thing. <\/p>\n

We say the equivalence relation $\\sim$ is finer<\/b> than the equivalence relation $\\sim’$ if<\/p>\n

$$ x \\sim y \\; \\implies x \\sim’ y $$<\/p>\n

In this situation we also say that $\\sim’$ is coarser<\/b> than $\\sim$. We also use these words for the partitions corresponding to these equivalence relations. A partition $\\pi$ is finer than a partition $\\pi’$ iff every block of $\\pi$ is contained in a block of $\\pi’$. <\/p>\n

This puts a partial ordering on the set $\\Pi(S)$ of all partitions of $S$: we say $\\pi \\le \\pi’$ if $\\pi$ is finer than $\\pi’$. In fact this makes $\\Pi(S)$ into a complete lattice<\/a>. This lattice is much subtler than the lattice of subsets of $S$: for example, it typically fails to be distributive<\/a>.<\/p>\n

Puzzle 1:<\/b> Can you see how the lattice here fails to be distributive? If $p \\vee q$ is the coarsest partition finer than both $p$ and $q$, and $p \\wedge q$ is the finest partition that is coarser than both $p$ and $q$, you want to find partitions with<\/p>\n

$$ p \\wedge (q \\vee r) \\ne (p \\wedge q) \\vee (p \\wedge r) $$<\/p>\n

or<\/p>\n

$$ p \\vee (q \\wedge r) \\ne (p \\vee q) \\wedge (p \\vee r) $$<\/p>\n

The lattice of partitions $\\Pi(S)$ also typically lacks the Sperner property<\/a>. In other words, the largest possible set of partitions of $S$, none of which is finer than any other, does not consist of all partitions with a specific number of blocks. However, the first proof of this, due to E. R. Canfield, only constructed counterexamples when $S$ has more than about $6.5 \\cdot 10^{24}$ elements! The challenge of understanding these counterexamples in full detail has a fascinating history, some of which is told here:<\/p>\n

• E. Rodney Canfield, On a problem of Rota<\/a>, Adv. Math.<\/i> 29<\/b> (1978), 1–10.<\/p>\n

• Ronald Graham, Maximum antichains in the partition lattice<\/a>, The Mathematical Intelligencer<\/i> 2<\/b> (1978), 84–86.<\/p>\n

• E. Rodney Canfield and Larry H. Harper, A simplified guide to large antichains in the partition lattice<\/a>, December 13, 1999.<\/p>\n

Counting the number of partitions of an $n$-element set gives the $n$th Bell number<\/a> $B_n$. The Bell numbers have a nice generating function<\/a>:<\/p>\n

$$ \\displaystyle{ \\sum_{n = 0}^\\infty \\frac{B_n z^n}{n!} = e^{e^z – 1} }$$<\/p>\n

and Dobinski’s formula<\/a> is quite charming:<\/p>\n

$$ B_n = \\displaystyle{ \\frac{1}{e} \\sum_{k = 0}^\\infty \\frac{k^n}{k!} }.$$<\/p>\n

but to efficiently compute the Bell numbers, it is more practical to use this easily proved recurrence relation<\/a>:<\/p>\n

$$ \\displaystyle{ B_{n+1}= \\sum_{k=0}^{n} \\binom{n}{k} B_k .} $$<\/p>\n

\n
\"Genji-mon\"<\/a>

Genji-mon<\/p><\/div>\n<\/div>\n

The Tale of Genji<\/a><\/i> is a wonderful early Japanese novel written by the noblewoman Murasaki Shikibu sometime between 1008 and 1021 AD. It has 54 chapters. Above you see the 54 Genji-mon<\/a><\/b>: the traditional symbols for these chapters. Most of them follow a systematic mathematical pattern, but the ones in color break this pattern.<\/p>\n

Puzzle 2:<\/b> How is the green Genji-mon different from all the rest?<\/p>\n

Puzzle 3:<\/b> How are the red Genji-mon similar to each other?<\/p>\n

\nPuzzle 4:<\/b> How are the red Genji-mon different from all the rest?<\/p>\n

\nPuzzle 5:<\/b> If The Tale of Genji<\/i> had just 52 chapters, the Genji-mon could be perfectly systematic, without the strange features exhibited by those shown in color. What would the pattern be then?<\/p>\n

The lattice of partitions was drawn by Tilman Piesk<\/a> and placed on Wikicommons<\/a> under a Creative Commons Attribution 3.0 Unported<\/a> license. The chart of Genji-mon was created by ‘AnonMoos’ and put into the public domain on Wikicommons<\/a>. <\/p>\n

\n

Visual Insight<\/i> is a place to share striking images that help explain advanced topics in mathematics. I\u2019m always looking for truly beautiful images, so if you know about one, please drop a comment here<\/a> and let me know!<\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

This picture by Tilman Piesk<\/a> shows the 15 partitions of a 4-element set, ordered by refinement. Finer partitions are connected to coarser ones by lines going down. In the finest partition, on top, each of the 4 elements is in its own subset. In the coarsest one, on bottom, all 4 elements are in the same subset.<\/p>\n

<\/div>\n","protected":false},"author":66,"featured_media":1674,"comment_status":"open","ping_status":"closed","sticky":true,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[21,2],"tags":[],"class_list":["post-1673","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-combinatorics","category-images-library"],"jetpack_featured_media_url":"https:\/\/blogs.ams.org\/visualinsight\/files\/2015\/06\/lattice_of_partitions.png","jetpack_shortlink":"https:\/\/wp.me\/p42Vmc-qZ","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1673","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/users\/66"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/comments?post=1673"}],"version-history":[{"count":29,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1673\/revisions"}],"predecessor-version":[{"id":2739,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1673\/revisions\/2739"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media\/1674"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media?parent=1673"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/categories?post=1673"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/tags?post=1673"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}