{'fraction_non_alphanumeric': 0.06282438608722597, 'fraction_numerical': 0.008985978774498412, 'mean_word_length': 3.645555955379633, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Random Linear Extensions of Grids

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.


Introduction
A grid poset -or more succinctly, a grid -is a product of chains. Grids make appearances in a surprisingly diverse range of mathematics. The lattice of submultisets of a multiset is a grid, including the extreme case of the Boolean lattice; the lattice of positive divisors of an integer is a grid; conjoint analysis (a branch of economic preference theory) is concerned with grids as sets of goods or products; Ferrers diagrams and plane partitions are lower-sets (i.e., order ideals) of two and three dimensional grids, respectively; the theory of poset order dimension (q.v. [21]) can be viewed as studying criteria for embeddability into grids.
In many of these contexts, one of the most important objects of study is the linear extension, i.e., a linear ordering of the vertices of the grid which respects the original ordering. Linear extensions of posets are an object of extensive study in their own right, and the specialization to grids has raised many an interesting question. Brightwell and Tetali [1] recently pinned down the asymptotics for the number of linear extensions of the Boolean lattice, and the question of when such a linear extension is representable is a central issue in the area(s) known by the names "qualitative", "subjective", and "comparative" probability (q.v. [6,7,8,13]). Marketing researchers (e.g., [12]) are interested in eliciting customers' personal extensions of product grids with few queries in order to determine pricing. Linear extensions of a two dimensional grid correspond to Young Tableaux, objects to which a huge amount of attention has been devoted (and for which the interested reader is directed to [20] as a starting point). The list goes on.
Frequently, it is a natural question to ask what a random linear extension of a grid looks like. While specific aspects of this inquiry have been addressed in the literature (witness, e.g., [2,16]), the general setting, per se, does not appear to have been addressed, and so we hope to initiate some interest in the topic with the present work. Naturally, there are many ways to attack the issue of describing a random structure, and we focus on one: the so-called jump number.
The jump number of a poset is the minimum number of times that a linear extension "jumps" from an element of the poset to an incomparable one. (Formal definitions appear in the next section.) This quantity, which in some sense measures how vertical or stratified a poset is, is well-studied. (See, for example, [4,14,19].) We are interested in the question of what the jump number of a random linear extension of a grid is. In particular, we show that, for a grid whose dimension is not too high, the jump number is almost surely close to the maximum possible number of jumps in any linear extension. Notably, the proof uses information-theoretic arguments, an approach that appears to be gaining recognition as a powerful tool for attacking questions about linear extensions.
In the next section, we provide the necessary definitions. The following section addresses the issue of counting linear extensions of grids, and the following section looks at the extreme jump numbers of such extensions. Section 4 contains the main results on random linear extensions of grids, and we conclude with several open-ended questions in this area.
Suppose P is a finite poset. Define T (P ), the transposition graph of P , to be the induced subgraph of B n whose vertices are the linear extensions of P for some (fixed) labelling of the vertices of P by [|P |]. Note that T (P ) = B n , the 1-skeleton of the permutahedron, if P is an n-element antichain. We are interested in studying the linear extensions of P = [m] n , a product of n chains of length m, which we term a grid.
Let r(x), for x ∈ [m] n , denote the rank of x = (x 1 , . . . , x n ), i.e., 1 + n j=1 (x j − 1). The s th rank-level r −1 (s) we will denote by W s . We write L k for L −1 (k), i.e., k th element of the ordering given by L, and L S = j∈S L j .
A jump of a linear extension L of a poset is an integer k ∈ [|P |], which we will refer to as a "time", so that L k ≺ L k+1 . The jump number s(P ) of a poset P is the least number of jumps over all linear extensions of P . It is not hard to see that s(P ) is simply the minimum degree of T (P ). The average jump numbers(P ), which corresponds to the average degree of the graph T (P ), is just the average number of jumps over all linear extensions of P .

Vertex Count
First, we give an estimate for the number of vertices in T ([m] n ). Proposition 1.
Proof. Note that a simple lower bound for the number of extensions of any ranked poset is the product of the factorials of its rank-level sizes. Let a 1 , . . . , a m(n−1)+1 denote the rank-level sizes of the poset [m] n , i.e., a j = |W j |, the j th Whitney number. We claim that, for any sequence of positive integers where x! = Γ(x + 1) for x ∈ R. To see this, take the log of both sides: This equation clearly holds, by Jensen's inequality, if we can show that log x! is a convex function of x. The second derivative of log Γ(x) is the trigamma function, with well-known representation a quantity which is clearly positive for x > −1. Therefore, we may conclude that (1) holds. By defining a m(n−1)+2 , . . . , a mn = 0, we may apply this to the sequence a 1 , . . . , a mn , yielding For the upper bound, we note that one can think of "building up" a linear extension by choosing the next element at each step, and the set of possible "next elements" is an antichain. It is well known that [m] n is Sperner, i.e., its largest antichain is its largest rank-level. It is also rank-symmetric and unimodal; therefore, its largest rank-level is the "middle" one, i.e., rank ⌊n(m − 1)/2⌋ + 1. This is the number of ways to write ⌊n(m − 1)/2⌋ + 2 as a sum of n integers in [m], a quantity bounded by Therefore, an upper bound for the number of linear extensions is given by the m n -th power of this quantity.
In the case that the poset in question is not necessarily equilateral, it is not hard to extend the above argument in the case of an upper bound.

Lemma 2. The number of linear extensions of
Proof. We show, inductively, the claim that the largest antichain in P has size at most |P |/ max j a j . This clearly implies the lemma. First, note that the k = 1 case is trivial. Now, suppose the claim is true for k − 1. Since P is Sperner, we need only consider the size of its rank-levels. The cardinality |W s | is given by the number of solutions to where 1 ≤ x j ≤ a j is an integer. Without loss of generality, we may assume that a k = min j a j . Then we may write Invoking the inductive hypothesis, we have

Degree Sequence Extremes
Think of a linear extension L of a poset P being "built up" an element at a time, so that the j th element of L is "added at time j". Then, given an integer k with 1 ≤ k ≤ |P |, define a pit to be any minimal element of i.e., a pit is an element of P which could be "next" in any linear extension which agrees with L up to time k. Let pits(L, k) denote the number of pits at time k. Note that the map L ′ j : [m] n → [m n ] which agrees with L except on the j th and (j + 1) st elements, but has those two elements swapped, is a bona fide extension of P = [m] n if and only if L j+1 ⊁ L j . Therefore, deg(L) is the number of j so that L j+1 ⊁ L j , i.e., the number of "good" times j. If the (j + 1) st element of L is chosen uniformly at random, then the probability that j is bad is d + (L j )/pits(L, j), where d + (v) is the number of elements covering v in the poset. Note that good times correspond exactly to jumps. Proof. We begin by noting that there are m n − 1 possible times j. At least two are always bad: the first and the last. Indeed, the first is bad because L 1 = (1, . . . , 1) and L 2 must cover this. If L 2 ⊁ L 1 , then there is a z ∈ [m] n with L 1 < z < L 2 so that L(z) > 2, contradicting that fact that L is a linear extension of [m] n . Similarly, if L m n ⊁ L m n −1 , then there is a z ∈ [m] n with L m n −1 < z < L m n so that L(z) < m n − 1, again, a contradiction. Therefore, deg(L) ≤ m n − 3 for all L.
On the other hand, this bound is achievable. Indeed, let L be the linear extension so that r(x) < r(y) implies L(x) < L(y), with the lexicographic ordering within each W s . Within each rank-level, there are no bad times. The only possible bad times occur during the transition from W s to W s+1 . However, note the first element of W s is the vector (x 1 , . . . , x n ) constructed inductively by letting for k = 1, . . . , n, since this is the smallest quantity ≥ 1 so that writing x k+1 +· · ·+x n = s+n−1− k j=1 x j does not require any integers greater than m on the left-hand side. The first coordinate will then be s − (n − 1)(m − 1) if s > (n − 1)(m − 1) and 1 otherwise. Similarly, the last element of W s is the vector (x 1 , . . . , x n ) constructed inductively by letting x j , m} for k = 1, . . . , n, since this is the largest quantity ≤ m so that writing x k+1 + · · · + x n = s + n − 1 − k j=1 x j does not require any integers less than 1 on the left-hand side. The first coordinate will then be s if s ≤ m and m otherwise.
The third inequality only fails when n = m = 2, where it is easy to check that the claimed upper bound is correct. The fourth inequality is satisfied whenever s < n(m − 1), i.e., s is not the second-to-largest or largest rank. Therefore, no element is succeeded by an element that covers it, except for the first and the second-to-last elements in the ordering. This implies that deg(L) = m n − 3.
For the minimum degree, we appeal to [11].

Average Jump Number
Let H[X] denote the entropy of the random variable X, E[X] the expectation of X, and P[A] the probability of the event A. We will write lg for the logarithm base 2.
The following theorem shows that, in fact, T ([m] n ) is "almost regular" whenever n = o(log m). Remark. Here we can take "sufficiently large" to mean that n ≥ 2 and m ≥ 41.
Proof. If we let L be a linear extension of [m] n chosen uniformly at random, then where β(n) = (1 + lg n)/(n − 1). Suppose that, for all k ∈ I ⊂ [m n ], we have where the third factor has an extra factor of n because no element of [m] n is covered by more than n elements. Continuing the computation, we find that Taking Q = lg n lg m/3 yields We can apply the fact that the maximum degree in T ([m] n ) is m n − 3 to get the following more quantitative result. Of course, one can use this statement to conclude that the set of pits at most times in a random linear extension is, with high probability, a constant fraction of the size of a maximal antichain. The conclusion is fairly weak, however, and only applies in the log n = o(log m) regime. On the other hand, a simpler proof yields a better conclusion, as the next result demonstrates. Combining this with (2) and writing η(r) = E[#k pits(L, k) = r], we find T r=1 η(r) lg r ≥ (n − 1)m n (lg m − β(n)). ( Suppose that T r=ǫT η(r) < m n (1 + (1 + lg n)/ lg ǫ) for some ǫ ∈ (0, 1). Then contradicting (3). Therefore, the expected fraction of times k when pits(L, k) < ǫT is at most −(1 + lg n)/ lg ǫ.
By applying Markov's inequality we immediately conclude the following.
Corollary 8. For ∆ ≥ 1, the probability that L has more than times k when pits(L, k) < 2 −R me 2 n−1 is at most ∆ −1 .

Notes
We conjecture that, even when the dimension is large, the average jump number is close to the maximum jump number. It would be interesting to describe more precisely the integer sequence pits(L, k) for random choices of L. Proposition 7 gets at this issue, but there is obviously much left to ask. Is the sequence pits(L, k) unimodal with high probability after convolution with a short interval in k? What are the higher moments of random jump numbers? To what extent is the statistic s(·) respected by Cartesion product? Which posets have their average jump number substantially different from the maximum jump number? What does it say about the relationship between the height and width of a poset if one knows thats(P ) is close to the maximum?

Acknowledgments
Thank you to Angelika Steger and ETH-Zürich for their hospitality and support for the months during which this work was done. Thank you also to Jochem Giesen and Eva Schuberth for providing valuable insights. Finally, gratitude to Graham Brightwell for allowing me to pick his encyclopedic knowledge of poset theory.