3
$\begingroup$

Does anyone know of an early published reference for the (very easy) fact that all finite posets can be represented as the poset of divisibility of a finite set of integers?

Page 1 of Birkhoff's Lattice Theory (1940) talks about the poset of divisibility of all positive integers, and I assume this must have been known to Birkhoff, but I can't find this specific fact in his book.

I ask because the Wikipedia article on comparability graphs uses as a reference a 2001 publication by Chartrand et al that studies the comparability graphs of divisibility posets of integers but appears to be unaware of any past work on comparability graphs or divisibility posets. It seems ridiculous to credit them with the connection between comparability and divisibility (both because their publication was so late and because they didn't fully make that connection themselves) so I'd like a better reference.

Improve this question
$\endgroup$
5
  • $\begingroup$ This seems like such a trivial fact that I'm not sure it would be stated anywhere. $\endgroup$
    – Sam Hopkins
    Commented Apr 25, 2019 at 1:20
  • 1
    $\begingroup$ Feynman on trivial theorems: e-reading.club/chapter.php/71262/21/… $\endgroup$
    – Todd Trimble
    Commented Apr 25, 2019 at 1:33
  • 1
    $\begingroup$ It is trivial that every finite poset (indeed, every poset) $P$ can be represented by a collection of sets with the subset relation. (Let $x\in P$ correspond to $\{y\in P\,|\,y\leq x\}$.) The divisors of a squarefree integer with $r$ prime factors is isomorphic to the lattice of subsets of an $r$-element set. Thus I don't see the point of representing posets by integer divisibility. $\endgroup$
    – Richard Stanley
    Commented Apr 25, 2019 at 2:08
  • 1
    $\begingroup$ I agree that it's trivial. I did say "very easy" in my question. But I would still like a reference. $\endgroup$
    – David Eppstein
    Commented Apr 25, 2019 at 5:40
  • $\begingroup$ The least integer $r$ for which a finite poset $P$ is a subposet of the poset $D_n$ of divisors of some integer $n$ with $r$ distinct prime factors is the (order) dimension of $P$. This concept goes back to Dushnik and Miller (1941). Dimension is usually defined in terms of subposets of $\mathbb{Z}^r$, which is clearly equivalent to the definition in terms of $D_n$. $\endgroup$
    – Richard Stanley
    Commented Apr 25, 2019 at 13:30

0

Reset to default

You must log in to answer this question.