number of partial orders modulo a fixed number

2010-09-28T22:31:26Z

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).

Answer by Aaron Meyerowitz for number of partial orders modulo a fixed number

2010-09-29T05:32:11Z

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.research.att.com/~njas/sequences/A047864 http://www.research.att.com/~njas/sequences/A001832

It also works for appropriate restricted classes such as series parallel networks with n labelled vertices and parallel edges allowed. http://www.research.att.com/~njas/sequences/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.

number of partial orders modulo a fixed number - MathOverflow

number of partial orders modulo a fixed number

Answer by Aaron Meyerowitz for number of partial orders modulo a fixed number