{
  "id": "1303.3652",
  "version": "v2",
  "published": "2013-03-15T01:10:05.000Z",
  "updated": "2014-03-05T15:16:52.000Z",
  "title": "Structure and enumeration of (3+1)-free posets",
  "authors": [
    "Mathieu Guay-Paquet",
    "Alejandro H. Morales",
    "Eric Rowland"
  ],
  "comment": "28 pages, 5 figures. New version includes substantial changes to clarify the construction of skeleta and the enumeration. An extended abstract of this paper appears as arXiv:1212.5356",
  "categories": [
    "math.CO"
  ],
  "abstract": "A poset is (3+1)-free if it does not contain the disjoint union of chains of length 3 and 1 as an induced subposet. These posets play a central role in the (3+1)-free conjecture of Stanley and Stembridge. Lewis and Zhang have enumerated (3+1)-free posets in the graded case by decomposing them into bipartite graphs, but until now the general enumeration problem has remained open. We give a finer decomposition into bipartite graphs which applies to all (3+1)-free posets and obtain generating functions which count (3+1)-free posets with labelled or unlabelled vertices. Using this decomposition, we obtain a decomposition of the automorphism group and asymptotics for the number of (3+1)-free posets.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-03-05T15:16:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15",
      "05A16"
    ],
    "keywords": [
      "bipartite graphs",
      "general enumeration problem",
      "finer decomposition",
      "automorphism group",
      "posets play"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1303.3652G"
    }
  }
}