Phase transitions in the evolution of partial orders (Q5937243): Difference between revisions

Given \(P_n\), the class of all labeled posets on \([n]= \{1,\dots, n\}\), to provide a ``count'' can mean giving an estimate up to some degree of accuracy, such as the original celebrated Kleitman-Rothschild estimate \(\log_2|P_n|= {1\over 2} n^2+ O(n^{3/2}\log_2 n)\) and improvements by themselves and others. Given a partial order \(P\), the number of comparable pairs (typically roughly \((3/16)n^2\)) is taken as a (time) parameter whose ``cohort'' (at the same value of both order and that parameter) should show sufficient similarity of structure to permit, if not an exact count, then at least a Kleitman-Rothschild type estimate for that cohort, especially when \(n\) becomes large, for asymptotic results. If \(0< d< 1/2\), and the (time) parameter is \([dn^2]\) (the nearest integer to \(dn^2\)), if \(P_{n,d}\) denotes this cohort, then \(c(d)= \lim_{n\to\infty}\log_2|P_{n,d}|/n^2\) (provided this limit exists) is an example of such an asymptotic description of the behavior of ``cohorts''. The function \(c(d)\) can be interpreted as a type of entropy function, with \(0< d\leq 1/8\) yielding \(c(d)= {1\over 4} H(4d)\), \(H(x)= -x\log_2x-(1- x)\log_2(1- x)\) illustrating this interpretation according to Kleitman-Rothschild. The description and determination of \(c(d)\) for \(0< d<{1\over 2}\) is the main purpose of this very substantial paper, replete with a variety of very elegant results and proof techniques reminding readers of notions derived from analytic number theory, statistical mechanics, thermodynamics and also random graph theory become poset theory. Even optimization theory is packaged in the description, as in the notion of ``feasibility'', and certain computations are deemed ``technical'' more so than others. This large opus should do honor to Kleitman-Rothschild, Dhar and others concerned with counting finite posets in ``an earlier age'' as well as to encourage others to carry these investigations even further.