number of partial orders modulo a fixed number - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T04:08:44Z http://mathoverflow.net/feeds/question/40390 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40390/number-of-partial-orders-modulo-a-fixed-number number of partial orders modulo a fixed number Martin Erickson 2010-09-28T22:31:26Z 2010-09-30T06:10:47Z <p>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}.</p> <p>We see that the units digits of these numbers appear to cycle with a period of length four: 1, 3, 9, 9.</p> <p>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.</p> <p>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). </p> http://mathoverflow.net/questions/40390/number-of-partial-orders-modulo-a-fixed-number/40421#40421 Answer by Aaron Meyerowitz for number of partial orders modulo a fixed number Aaron Meyerowitz 2010-09-29T05:32:11Z 2010-09-30T06:10:47Z <p>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?</p> <p><strong>later</strong> The argument seems as if it should work for bipartite graphs on n labelled vertices and also connected bipartite graphs <em>except for powers of 2</em> The data at OEIS supports this as far as it goes, ignoring the numbers for less than 3 vertices. <a href="http://www.research.att.com/~njas/sequences/A047864" rel="nofollow">http://www.research.att.com/~njas/sequences/A047864</a> <a href="http://www.research.att.com/~njas/sequences/A001832" rel="nofollow">http://www.research.att.com/~njas/sequences/A001832</a></p> <p>It also works for appropriate restricted classes such as series parallel networks with n labelled vertices and parallel edges allowed. <a href="http://www.research.att.com/~njas/sequences/A053554" rel="nofollow">http://www.research.att.com/~njas/sequences/A053554</a></p> <p>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.</p>