22
$\begingroup$

Let p(n) be the number of partial orders on the set {1,...,n}. From the Online Encyclopedia of Integer Sequences, we find that the known values of p(n) are {1,1,3,19,219,4231,130023,6129859,431723379,44511042511,6611065248783,1396281677105899,414864951055853499,171850728381587059351,98484324257128207032183,77567171020440688353049939,83480529785490157813844256579,122152541250295322862941281269151,241939392597201176602897820148085023}.

We see that the units digits of these numbers appear to cycle with a period of length four: 1, 3, 9, 9.

Experiments with other moduli indicate that given a prime modulus m, the sequence cycles with a period of length m-1. If the modulus m is a prime power, then the period appears to be of length phi(m), where phi is Euler's phi-function. For any modulus m, the period appears to be of length the least common multiple (LCM) of the constituent period lengths. For example, if m=12, the period appears to be of length LCM(phi(4),phi(3))=LCM(2,2)=2.

I don't know how to prove this conjecture and I don't see any reference to it. If proved, perhaps this result together with an asymptotic estimate for p(n) could be used to find higher values of p(n).

$\endgroup$
13
  • 2
    $\begingroup$ The link to the OEIS sequence A001035: oeis.org/A001035 $\endgroup$ Sep 28, 2010 at 22:38
  • 2
    $\begingroup$ This is a really nifty conjecture. My gut is skeptical that the period will always work out to exactly $p-1$, but even the claim that a period exists is cool. The only way I can think of approaching it is to show (for fixed $p$) that almost all posets have an automorphism of order $p$, so they don't contribute to the count mod $p$, and proving some sort of recursion for posets without such an automorphism. Good luck! $\endgroup$ Sep 28, 2010 at 22:53
  • 2
    $\begingroup$ Since Aut(P) is a subgroup of S_n, another way to state this is that we only care about the cases where Aut(P) and S_n have the same p-sylow. In other words, we want to look at posets which are preserved by Sylow_p(S_n). Since Sylow_p(S_n) is pretty easy to describe explicitly, this might be a good starting point. $\endgroup$ Sep 28, 2010 at 23:08
  • 3
    $\begingroup$ Ah, if I'd gone over to page 2 in the above Borevich reference, I'd have seen that your conjecture is Theorem 1. He doesn't give a detailed proof (or even a reference - apparently 'it is recounted in another place' !) but does give some hints. $\endgroup$
    – dke
    Sep 28, 2010 at 23:52
  • 4
    $\begingroup$ Just to add: Borevich eventually wrote up a proof of your conjecture here springerlink.com/content/g654831527p1561v $\endgroup$
    – dke
    Sep 29, 2010 at 11:19

1 Answer 1

17
$\begingroup$

For q prime, enlarge $\{ 1,\cdots,m \}$ to a set of size $n=m+(q-1)$ by replacing $m$ by $q$ clones $m_1 , m_2 , \cdots , m_q$ and consider the $q$-cycle $\sigma=(m_1\ m_2\ \cdots \ m_q)$. It acts on the set of partial orders of the $n$-set and each of its orbits has size 1 or size q. Each orbit of size 1 arises from a unique partial order of the $m$-set by having all $p$ clones behave identically to the original. This proves that $p(m+(q-1)) \equiv p(m) \mod q $ I think I see how to generalize to $q^k$ but I'll have to think about it. The same idea should apply to a wider variety of structures, but which ones?

later The argument seems as if it should work for bipartite graphs on n labelled vertices and also connected bipartite graphs except for powers of 2 The data at OEIS supports this as far as it goes, ignoring the numbers for less than 3 vertices. http://www.oeis.org/A047864 http://www.oeis.org/A001832

It also works for appropriate restricted classes such as series parallel networks with n labelled vertices and parallel edges allowed. http://www.oeis.org/A053554

Here is my argument for why $p(n+\phi(q^2)) \equiv p(n) \mod q^2$. I think it generalizes to $q^k$: Further enlarge the $n$ set above to one of size $m+q^2-1=n+\phi(q^2)=N$ by replacing each clone $m_i$ by $q$ clones $m_{i1}, m_{i2}, \cdots ,m_{iq}$ and consider the $q^2$ cycle $$\tau=(m_{11}m_{21}\cdots m_{q1}m_{12}m_{22}\cdots m_{q,q})$$ It acts on partial orders of the $N$-set and the action has orbits of size 1, $q$ and $q^2$. The orbits of size less than $q^2$ are in bijective correspondence with the orbits of the same size for the action of $\sigma$ on partial orders of the $n$-set.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.