Random Linear Extensions of Grids

Joshua Cooper

REVIEW

Random Linear Extensions of Grids

Joshua Cooper

Combinatorics · Submitted 22 Feb 2006 · 21 references

Pith's verdict: Plausible and well-written, but the main proof's concentration step is wrong in a way that needs new ideas, not just tweaks.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDmath/0602509 (version 1)

Pith ID4XZGRIXB, Pith's permanent record of this paper and its review

CitationJoshua Cooper. "Random Linear Extensions of Grids." arXiv:math/0602509 (2006). https://pith.science/paper/4XZGRIXB

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Colleague,

The main claim — that for grids [m]^n with n not too large relative to log m, a uniform random linear extension is almost maximally jumpy — is clean and plausible, and the entropy route is a sensible way to attack it. If Theorem 5 were rigorous, it would be a nice addition to the thin literature on random linear extensions of products of chains.

What is genuinely new is the focus on the average jump number (equivalently, the average degree of the transposition graph) rather than the extremal jump number, plus the entropy framework. Proposition 1 gives solid bounds on the number of linear extensions, Theorem 3 correctly pins the maximum degree at m^n − 3, and the open questions are thoughtful.

The soft spot is the proof of Theorem 5, and there are two distinct problems. First, the antichain bound T is set to (me/2)^{n−1}, and then lg T is replaced by (n−1)lg m. That replacement is false because lg(e/2) > 0. This is repairable by using the sharper bound T ≤ m^{n−1} (from Lemma 2 or the Sperner property). Second, and more seriously, the step converting a lower bound on conditional entropy into a high-probability statement about the next element is not justified. The valid contrapositive of their argument gives only that the event "some outcome has probability > ε" has probability at least ε, not at most ε. The paper asserts the opposite. A simple mixture example shows high average conditional entropy does not force the stated concentration. Without grid-specific structure to rule out such mixtures, the final expectation bound does not follow. This is a load-bearing gap, not a typo.

The theorem may still be true — a direct argument bounding the probability that the next element covers a pit could well salvage it — but that argument is absent. The writing is honest and clear, and the paper does not overclaim beyond this.

I would send this to a serious referee, but with the expectation of major revision. As it stands, I would not rely on Theorem 5 in my own work.

Yours,

Referee report

Major objections (3)

[Section 5, proof of Theorem 5] The proof sets T = (me/2)^{n-1} as an upper bound on the largest antichain and then, in the chain of inequalities after the line '≤ S((n−1) lg m − Q) + (mn − |I|) lg T', replaces lg T by (n−1) lg m. This substitution is false, because lg T = (n−1) lg m + (n−1) lg(e/2) > (n−1) lg m. The argument can be repaired by invoking Lemma 2 to take T = m^{n−1}, in which case lg T = (n−1) lg m exactly, but the current text is invalid and the repair must be stated explicitly.
[Section 5, proof of Theorem 5] The step from high conditional entropy to the claimed high-probability bound on the most likely next element is logically incorrect. Let E be the event that some outcome of L_{k+1}|L[k] has probability greater than epsilon. The proof assumes P(E) >= 1 - epsilon and derives an upper bound on H; the contrapositive gives only P(E) < 1 - epsilon, not P(E) <= epsilon. Consequently, the assertion 'with probability at least 1 − ε, no outcome of L_{k+1}|L[k] is likelier than probability 2Q/((n−1) lg m)' does not follow. The final degree bound multiplies by (1 − ε)(1 − nε), so this gap is load-bearing; a mixture of peaked and uniform conditional distributions shows the general implication is false without grid-specific structure.
[Section 3, proof of Proposition 1] Inequality (1) is false as stated for arbitrary positive integers b_j. For example, with s = 3 and (b_1, b_2, b_3) = (1, 1, 100), the left side is 100! while the right side is ((2/3) * 102)!^3 = (68!)^3, and 100! < (68!)^3. The Jensen argument using convexity of log Γ(x) proves instead the inequality with the arithmetic mean (1/s) Σ b_j, not with ((s−1)/s) Σ b_j. Since the proof of Proposition 1 uses inequality (1) to obtain the entropy lower bound (2), this is another load-bearing point that needs correction; the corrected inequality still yields the intended type of bound for the grid rank sizes.

Minor objections (6)

[Section 3, Proposition 1] The notation 'm(n−1)+1' should presumably be 'n(m−1)+1', since the grid [m]^n has n(m−1)+1 rank levels.
[Section 5, proof of Theorem 5] The set I is used without a formal definition; it should be defined as the set of times k for which H[L_{k+1}|L[k]] < (n−1) lg m − Q.
[Section 5, proof of Theorem 5] There is an unmatched parenthesis in the expression 'at least mn(1 − (1 + lg n))/Q)'; it should read 'mn(1 − (1 + lg n)/Q)'.
[Section 1] The citation to Brightwell and Tetali is given as [1], but reference [1] is by Bae and Kim; the intended reference appears to be [3], 'The number of linear extensions of the Boolean lattice'.
[Section 5, Proposition 7] The symbol '϶' used in the proof is nonstandard; replace it with 'such that' or an equivalent phrase.
[Section 5, Theorem 5 remark] The remark 'sufficiently large m and n' is imprecise; the stated condition is simply n >= 2 and m >= 41.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

For grids [m]^n with n = o(log m), a random linear extension has, with high probability, within a vanishing fraction of the maximum possible number of incomparable adjacent pairs.

The reading

A grid poset is a collection of points with n coordinates, each an integer from 1 to m. One point is below another when all coordinates of the first are no larger. A linear extension is a list of all m^n points from bottom to top that respects this rule. When two neighboring points in the list are incomparable, so neither is below the other, that step is called a jump.

The paper asks how many jumps a random linear extension has. The maximum possible number of jumps is the number of adjacent slots minus two unavoidable non-jumps at the beginning and end, so m^n minus 3. The main theorem says that when the dimension n is tiny compared to log m, the average number of jumps is at least m^n times (1 minus a small error term). In other words, almost every adjacent pair is a jump, so a random ordering is nearly as jumpy as possible.

The proof is information-theoretic. A uniformly random linear extension has very high entropy, about (n-1)m^n log m bits. At almost every step, the next point can be chosen from many still-available minimal points, and no single candidate has high probability. Since each point has at most n immediate successors, the chance that the next point is comparable to the current one is small. The exceptions account for only a small fraction of all steps, giving the claimed bound.

Extended reading notes

Core claim

Theorem 5: the average degree in the transposition graph T([m]^n), i.e., the average jump number, is at least m^n (1 - sqrt(48 lg n / lg m)) for n ≥ 2 and m ≥ 41. If true, when n = e^{o(log m)}, the average number of jumps in a uniform random linear extension is within o(m^n) of the maximum possible value m^n - 3.

Load-bearing premise

The entropy proof of Theorem 5 assumes the conditional entropy of the next element is at most (n-1)lg m, which requires the number of available minimal elements (pits) at every step to be at most m^{n-1}. The paper instead states the cruder bound T = (me/2)^{n-1} for the largest antichain and then incorrectly substitutes lg T ≤ (n-1)lg m. The theorem is only as solid as this pit-count bound being valid at the value used in the calculation.

Original abstract

A grid poset -- or grid for short -- is a product of chains. We ask, what does a random linear extension of a grid look like? In particular, we show that the average "jump number," i.e., the number of times that two consecutive elements in a linear extension are incomparable in the poset, is close to its maximum possible value. The techniques employed rely on entropy arguments. We finish with several interesting questions about this wide-open area.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,083 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.22 · human participants 0.01 · controlled comparison 0.04 · randomized assignment 0.02 · states quantitative result 0.66 · compares with prior results 0.14 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

A grid poset -- or grid for short -- is a product of chains. We ask, what does a random linear extension of a grid look like? In particular, we show that the average "jump number," i.e., the number of times that two consecutive elements in a linear extension are incomparable in the poset, is close to its maximum possible value. The techniques employed rely on entropy arguments. We finish with several interesting questions about this wide-open area.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	A grid poset -- or grid for short -- is a product of chains.	background 1.00	0.05	0.02	asserted 1.00
s1	We ask, what does a random linear extension of a grid look like?	background 0.62	0.20	0.03	unclear 0.98
s2	In particular, we show that the average "jump number," i.e., the number of times that two consecutive elements in a linear extension are incomparable in the poset, is close to its maximum possible value.	result 1.00	0.95	0.88	asserted 1.00
s3	The techniques employed rely on entropy arguments.	method 1.00	0.70	0.02	asserted 0.99
s4	We finish with several interesting questions about this wide-open area.	future work 1.00	0.51	0.02	unclear 0.80

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (21)

[1]

D. R. Bae, J. Y. Kim, The jump number of P × n, Ars Combin. 60 (2001), 149-159

View on Pith 2001
[2]

G. Brightwell, Random k-dimensional orders: width and number of linear extensions, Order 9 (1992), no. 4, 333–342

View on Pith 1992
[3]

G. Brightwell, P. Tetali, The number of linear extensions of the Boo lean lattice, Order 20 (2003), no. 4, 333–345

View on Pith 2003
[4]

M. Chein and M. Habib, The jump number of dags and posets: an introduction, Combinatorics 79 (Proc. Colloq., Univ. Montreal, Mon- treal, Que., 1979), Part II, Ann. Discrete Math. 9 (1980), 189-1 94

View on Pith 1980
[5]

S. Felsner, K. Reuter, The linear extension diameter of a poset, SIAM J. Discrete Math. 12 (1999), no. 3, 360–373

View on Pith 1999
[6]

P. C. Fishburn, The axioms of subjective probability, Statist. Sc i. 1 (1986), no. 3, 335–358

View on Pith 1986
[7]

P. C. Fishburn, Finite linear qualitative probability, J. Math. Psych . 40 (1996), no. 1, 64–77

View on Pith 1996
[8]

P. C. Fishburn, Failure of cancellation conditions for additive linear orders, J. Combin. Des. 5 (1997), no. 5, 353–365

View on Pith 1997
[9]

Z. F¨ uredi, K. Reuter, The jump number of suborders of the po wer set order, Order 6 (1989), no. 1, 101–103

View on Pith 1989
[10]

V. V. Lozin, M. U. Gerber, On the jump number problem in heredit ary classes of bipartite graphs, Order 17 (2000), no. 4, 377–385

View on Pith 2000
[11]

H. C. Jung, On the product of some posets: jump number, gre ediness, Ars Combin. 40 (1995), 109-120. 12

View on Pith 1995
[12]

R. L. Keeney, H. Raiﬀa, Decisions with multiple objectives: prefe r- ences and value tradeoﬀs, Wiley Series in Probability and Mathemati- cal Statistics, John Wiley & Sons, New York-London-Sydney, 1976

View on Pith 1976
[13]

C. H. Kraft, J. W. Pratt, A. Seidenberg, Intuitive probability o n ﬁnite sets, Ann. Math. Statist. 30 (1959) 408–419

View on Pith 1959
[14]

M. Naatz, The graph of linear extensions revisited, SIAM J. Disc rete Math. 13 (2000), no. 3, 354–369

View on Pith 2000
[15]

M. Pouzet, K. Reuter, I. Rival, N. Zaguia, A generalized permut ahe- dron, Algebra Universalis 34 (1995), no. 4, 496–509

View on Pith 1995
[16]

B. Pittel, D. Romik, Limit shapes for random square Young tablea ux, to appear in Adv. Appl. Math

View on Pith
[17]

K. Reuter, The jump number and the lattice of maximal antichain s, Combinatorics of ordered sets (Oberwolfach, 1988), Discrete Ma th. 88 (1991), no. 2-3, 289–307

View on Pith 1991
[18]

K. Reuter, Linear extensions of a poset as abstract convex s ets, Preprint Hamburger Beitr¨ age zur Mathematik, Heft 56 (1996)

View on Pith 1996
[19]

K. Reuter, The comparability graph and the graph of linear exte n- sions of a poset, Preprint Hamburger Beitr¨ age zur Mathematik, H eft 57 (1996)

View on Pith 1996
[20]

R. P. Stanley, Enumerative combinatorics, Cambridge Studies in Ad- vanced Mathematics, 49, Cambridge University Press, Cambridge, 1997

View on Pith 1997
[21]

W. T. Trotter, Combinatorics and partially ordered sets: Dimen sion theory, Johns Hopkins Series in the Mathematical Sciences, Johns Hop- kins University Press, Baltimore, MD, 1992. 13

View on Pith 1992

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

D. R. Bae, J. Y. Kim, The jump number of P × n, Ars Combin. 60 (2001), 149-159

View on Pith 2001

[2] [2]

G. Brightwell, Random k-dimensional orders: width and number of linear extensions, Order 9 (1992), no. 4, 333–342

View on Pith 1992

[3] [3]

G. Brightwell, P. Tetali, The number of linear extensions of the Boo lean lattice, Order 20 (2003), no. 4, 333–345

View on Pith 2003

[4] [4]

M. Chein and M. Habib, The jump number of dags and posets: an introduction, Combinatorics 79 (Proc. Colloq., Univ. Montreal, Mon- treal, Que., 1979), Part II, Ann. Discrete Math. 9 (1980), 189-1 94

View on Pith 1980

[5] [5]

S. Felsner, K. Reuter, The linear extension diameter of a poset, SIAM J. Discrete Math. 12 (1999), no. 3, 360–373

View on Pith 1999

[6] [6]

P. C. Fishburn, The axioms of subjective probability, Statist. Sc i. 1 (1986), no. 3, 335–358

View on Pith 1986

[7] [7]

P. C. Fishburn, Finite linear qualitative probability, J. Math. Psych . 40 (1996), no. 1, 64–77

View on Pith 1996

[8] [8]

P. C. Fishburn, Failure of cancellation conditions for additive linear orders, J. Combin. Des. 5 (1997), no. 5, 353–365

View on Pith 1997

[9] [9]

Z. F¨ uredi, K. Reuter, The jump number of suborders of the po wer set order, Order 6 (1989), no. 1, 101–103

View on Pith 1989

[10] [10]

V. V. Lozin, M. U. Gerber, On the jump number problem in heredit ary classes of bipartite graphs, Order 17 (2000), no. 4, 377–385

View on Pith 2000

[11] [11]

H. C. Jung, On the product of some posets: jump number, gre ediness, Ars Combin. 40 (1995), 109-120. 12

View on Pith 1995

[12] [12]

R. L. Keeney, H. Raiﬀa, Decisions with multiple objectives: prefe r- ences and value tradeoﬀs, Wiley Series in Probability and Mathemati- cal Statistics, John Wiley & Sons, New York-London-Sydney, 1976

View on Pith 1976

[13] [13]

C. H. Kraft, J. W. Pratt, A. Seidenberg, Intuitive probability o n ﬁnite sets, Ann. Math. Statist. 30 (1959) 408–419

View on Pith 1959

[14] [14]

M. Naatz, The graph of linear extensions revisited, SIAM J. Disc rete Math. 13 (2000), no. 3, 354–369

View on Pith 2000

[15] [15]

M. Pouzet, K. Reuter, I. Rival, N. Zaguia, A generalized permut ahe- dron, Algebra Universalis 34 (1995), no. 4, 496–509

View on Pith 1995

[16] [16]

B. Pittel, D. Romik, Limit shapes for random square Young tablea ux, to appear in Adv. Appl. Math

View on Pith

[17] [17]

K. Reuter, The jump number and the lattice of maximal antichain s, Combinatorics of ordered sets (Oberwolfach, 1988), Discrete Ma th. 88 (1991), no. 2-3, 289–307

View on Pith 1991

[18] [18]

K. Reuter, Linear extensions of a poset as abstract convex s ets, Preprint Hamburger Beitr¨ age zur Mathematik, Heft 56 (1996)

View on Pith 1996

[19] [19]

K. Reuter, The comparability graph and the graph of linear exte n- sions of a poset, Preprint Hamburger Beitr¨ age zur Mathematik, H eft 57 (1996)

View on Pith 1996

[20] [20]

R. P. Stanley, Enumerative combinatorics, Cambridge Studies in Ad- vanced Mathematics, 49, Cambridge University Press, Cambridge, 1997

View on Pith 1997

[21] [21]

W. T. Trotter, Combinatorics and partially ordered sets: Dimen sion theory, Johns Hopkins Series in the Mathematical Sciences, Johns Hop- kins University Press, Baltimore, MD, 1992. 13

View on Pith 1992