{
  "id": "1706.04985",
  "version": "v1",
  "published": "2017-06-15T17:38:48.000Z",
  "updated": "2017-06-15T17:38:48.000Z",
  "title": "On the $1/3-2/3$ Conjecture",
  "authors": [
    "Emily J. Olson",
    "Bruce E. Sagan"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $(P,\\leq)$ be a finite poset (partially ordered set), where $P$ has cardinality $n$. Consider linear extensions of $P$ as permutations $x_1x_2\\cdots x_n$ in one-line notation. For distinct elements $x,y\\in P$, we define $\\mathbb{P}(x\\prec y)$ to be the proportion of linear extensions of $P$ in which $x$ comes before $y$. For $0\\leq \\alpha \\leq \\frac{1}{2}$, we say $(x,y)$ is an $\\alpha$-balanced pair if $\\alpha \\leq \\mathbb{P}(x\\prec y) \\leq 1-\\alpha.$ The $1/3-2/3$ Conjecture states that every finite partially ordered set which is not a chain has a $1/3$-balanced pair. We make progress on this conjecture by showing that it holds for certain families of posets. These include lattices such as the Boolean, set partition, and subspace lattices; partial orders that arise from a Young diagram; and some partial orders of dimension $2$. We also consider various posets which satisfy the stronger condition of having a $1/2$-balanced pair. For example, this happens when the poset has an automorphism with a cycle of length $2$. Various questions for future research are posed.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-15T17:38:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "06A07",
      "05A20",
      "05D99"
    ],
    "keywords": [
      "balanced pair",
      "partial orders",
      "linear extensions",
      "one-line notation",
      "finite poset"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}