{
  "id": "1103.3488",
  "version": "v4",
  "published": "2011-03-17T19:24:26.000Z",
  "updated": "2013-04-23T13:19:46.000Z",
  "title": "Sublattices of associahedra and permutohedra",
  "authors": [
    "Luigi Santocanale",
    "Friedrich Wehrung"
  ],
  "comment": "28 pages. In versions 1 and 2, there is an obvious bug on Page 1 (Introduction) in the definition of the Tamari lattice via binary bracketings: we should write that if $t$ is obtained by $s$ by substituting one occurrence of some (uv)w by u(vw), then $s$ lies below $t$ (and then take the reflexive, transitive closure). There is also a potentially troublesome misprint at the end of the proof of Lemma 11.4. These bugs were easy to fix, and are all corrected in version 3",
  "categories": [
    "math.CO"
  ],
  "abstract": "Gr\\\"atzer asked in 1971 for a characterization of sublattices of Tamari lattices (associahedra). A natural candidate was coined by McKenzie in 1972 with the notion of a bounded homomorphic image of a free lattice---in short, bounded lattice. Urquhart proved in 1978 that every associahedron is bounded (thus so are its sublattices). Geyer conjectured in 1994 that every finite bounded lattice embeds into some associahedron. We disprove Geyer's conjecture, by introducing an infinite collection of lattice-theoretical identities that hold in every associahedron, but not in every finite bounded lattice. Among those finite counterexamples, there are the permutohedron on four letters P(4), and in fact two of its subdirectly irreducible retracts, which are Cambrian lattices of type A. For natural numbers m and n, we denote by B(m,n) the (bounded) lattice obtained by doubling a join of m atoms in an (m+n)-atom Boolean lattice. We prove that B(m,n) embeds into an associahedron iff min(m,n) is less than or equal to 1, and that B(m,n) embeds into a permutohedron iff min(m,n) is less than or equal to 2. In particular, B(3,3) cannot be embedded into any permutohedron. Nevertheless we prove that B(3,3) is a homomorphic image of a sublattice of the permutohedron on 12 letters.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2013-04-23T13:19:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "associahedron",
      "permutohedron",
      "sublattice",
      "free lattice-in short",
      "finite bounded lattice embeds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1103.3488S"
    }
  }
}