{'fraction_non_alphanumeric': 0.04688089639757322, 'fraction_numerical': 0.008650468808963975, 'mean_word_length': 3.6167247386759582, 'pattern_counts': {'":': 0, '<': 17, '<?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': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sparsity and dimension

We prove that posets of bounded height whose cover graphs belong to a fixed class with bounded expansion have bounded dimension. Bounded expansion, introduced by Ne\v{s}et\v{r}il and Ossona de Mendez as a model for sparsity in graphs, is a property that is naturally satisfied by a wide range of graph classes, from graph structure theory (graphs excluding a minor or a topological minor) to graph drawing (e.g. graphs with constant book thickness). Therefore, our theorem generalizes a number of results including the most recent one for posets of bounded height with cover graphs excluding a fixed graph as a topological minor (Walczak, SODA 2015). We also show that the result is in a sense best possible, as it does not extend to nowhere dense classes; in fact, it already fails for cover graphs with locally bounded treewidth.

1. Introduction 1.1. Poset dimension and cover graphs. Partially ordered sets, posets for short, are studied extensively in combinatorics, set theory and theoretical computer science. One of the most important measures of complexity of a poset is its dimension. The dimension dim(P ) of a poset P is the least integer d such that points of P can be embedded into R d in such a way that x < y in P if and only if the point of x is below the point of y with respect to the product order on R d . Equivalently, the dimension of P is the least d such that there are d linear extensions of P whose intersection is P . Not surprisingly, dimension is hard to compute: Already deciding whether dim(P ) 3 is an NP-hard problem [29], and for every ε > 0, there is no n 1−ε -approximation algorithm for dimension unless ZPP=NP, where n denotes the size of the input poset [2]. Research in this area typically focus on finding witnesses for large dimension and sufficient conditions for small dimension; see e.g. [26] for a survey.
Posets are visualized by their diagrams: Points are placed in the plane and whenever a < b in the poset, and there is no point c with a < c < b, there is a curve from a to b going upwards (that is y-monotone). The diagram represents those relations which are essential in the sense that they are not implied by transitivity, known as cover relations. The undirected graph implicitly defined by such a diagram is the cover graph of the poset. That graph can be thought of as encoding the 'topology' of the poset.
There is a common belief that posets having a nice or well-structured drawing should have small dimension. But first let us note a negative observation by Kelly [13], from 1981, there is a family of posets whose diagrams can be drawn without edge crossingsundoubtedly qualifying as a 'nice' drawing-and with arbitrarily large dimension, see Figure 1. A key observation about Kelly's construction is that these posets also have large height. This leads us to our main theorem, which generalizes several previous works in this area. Theorem 1. For every class of graphs C with bounded expansion, and for every integer h 1, posets of height h whose cover graphs are in C have bounded dimension.

1.2.
Background. Theorem 1 takes its roots in the following result of Streib and Trotter [24]: Posets with planar cover graphs have dimension bounded in terms of their height. Note that this justifies the fact that height and dimension grow together in Kelly's construction. Joret, Micek, Milans, Trotter, Walczak, and Wang [11] subsequently proved that the same result holds in the case of cover graphs of bounded treewidth, of bounded genus, and more generally cover graphs that forbid a fixed apex graph as a minor. (Recall that a graph is apex if it can be made planar by removing at most one vertex.) In another direction, Füredi and Kahn [9] showed that posets with cover graphs of bounded maximum degree have dimension bounded in terms of their height. 1 All this was recently generalized by Walczak [28]: Posets whose cover graphs exclude a fixed b 1 graph as a topological minor have dimension bounded by a function of their height. (We note that Walczak's original proof relies on the graph structure theorems for graphs excluding a fixed topological minor; see [15] for an elementary proof.) Bounded degree graphs, planar graphs, bounded treewidth graphs, and more generally graphs avoiding a fixed (topological) minor are sparse, in the sense that they have linearly many edges. This remark naturally leads one to ponder whether simply having a sparse cover graph is enough to guarantee the dimension be bounded by a function of the height. This is exactly the question we address in this work. Our main contribution is to characterize precisely the type of sparsity that is needed to ensure the property. Before explaining it let us make some preliminary observations.
Clearly, asking literally that the cover graph has at most cn edges for some constant c, where n is the number of points of the poset, is not enough since one could simply consider the union of a standard example on Θ( √ n) points and a large antichain. Slightly less trivially, even requiring that property to hold for every subgraph of the cover graph (that is, bounding its degeneracy) is still not enough: Define the incidence poset I G of a graph G as the height-2 poset with point set V (G) ∪ E(G), where for a vertex v and an edge e we have v < e in P G whenever v is an endpoint of e in G (and no other relation). The fact that dim(I Kn ) log log n follows easily from repeated applications of the Erdős-Szekeres theorem for monotone sequences (see for instance [5]). Yet, the cover graph of I Kn is a clique where each edge is subdivided once, which is 2-degenerate.  To improve readability some inclusions are not drawn, e.g. k-planar graphs have locally bounded treewith.) classes with bounded expansion. Let us give some informal intuition, see Section 2 for the precise definitions. The key idea in both cases is to look at minors of bounded depth, that is, minors that can be obtained by first contracting disjoint connected subgraphs of bounded radius, and then possibly removing some vertices or edges. In a nowhere dense class it is required that bounded-depth minors exclude at least some graph (which can depend on the depth). In a class with bounded expansion the requirement is stronger: For every r 1, depth-r minors should be sparse, that is, their average degrees should be bounded by some function f (r).
It is well-known that graphs with no H-minors have average degree bounded by a function of H. Thus the corresponding class of graphs has bounded expansion, since the average degree of their minors is uniformly bounded by a constant. The class of graphs with no topological H-minors also has bounded expansion, though in that case the bounding function might not be constant anymore, see [18]. These remarks show that Theorem 1 generalizes the aforementioned result for cover graphs excluding a fixed graph as a topological minor, and hence the previous body of work as well.
In Figure 2 we give a summary of all the known results about posets with sparse cover graphs having their dimension bounded by a function of their height. We also mention the cases where dimension is bounded by an absolute constant, see the bottom part of the figure. Complementing our main result, we describe in Section 2 a family of height-2 posets whose cover graphs form a nowhere dense class and having unbounded dimension. Thus Theorem 1 cannot be extended to nowhere dense classes. The graphs constructed moreover have locally bounded treewidth, showing that this property alone is not sufficient either. Finally, in order to complete our study of sparse cover graphs following the theory of Nešetřil and Ossona de Mendez, we remark that another specialization of nowhere dense classes called almost wide classes also fail, in the sense that dimension is not bounded in terms of height for posets with cover graphs belonging to such a class.
(We postpone the rather technical definition of almost wide classes until Section 2.) 1.4. Applications. Let us now turn our attention to some applications of Theorem 1 in the context of graph drawing, where natural classes with bounded expansion appear that do not fit in the previous setting of excluding a (topological) minor. Consider for instance posets whose diagrams can be drawn with 'few' edge crossings. If we bound the total number of crossings, then the cover graphs have bounded genus, and hence earlier results apply. On the other hand, if we only bound the number of crossings per edge in the drawing, say at most k such crossings, then we come to the well-studied class of k-planar graphs. While k-planar graphs are sparse-Pach and Tóth [22] proved that their average degree is at most 8 √ k-they do not exclude any graph as a topological minor (assuming k 1), since every graph has a 1-planar subdivision: just start with any drawing of the graph in the plane and subdivide its edges around each crossing. Note however that this could require some edges to be subdivided many times. Indeed, one can observe that if an (< r)-subdivision of a graph G is k-planar then G is kr-planar. Combining this fact with Pach and Tóth's result, Nešetřil, Ossona de Mendez, and Wood [19] proved that the class of k-planar graphs has bounded expansion. Therefore, by Theorem 1, whenever a poset P has a k-planar cover graph, dim(P ) is bounded by a function of k and the height of P .
Another example is given by graphs with bounded book thickness. A book embedding of a graph is a collection of half-planes (pages) all having the same line as their boundary (the spine) such that all vertices of the graph lie on the line, every edge is contained in one of the half-planes, and edges on a same page do not cross. The book thickness (also known as stack number ) of a graph is the smallest number of pages in a book embedding. Clearly, every graph on n vertices with book thickness k has at most 2kn edges. Still, every graph has a subdivision with book thickness at most 3 (see e.g. [4]). Nešetřil et al. [19] observed that a result of Enomoto, Miyauchi, and Ota [6] easily implies that every class of graphs with bounded book thickness has bounded expansion. Therefore, by Theorem 1, whenever a poset P has a cover graph of book thickness at most k, its dimension is bounded by a function of k and the height of P .
Yet another class of graphs with bounded expansion from graph drawing is that of graphs with bounded queue number. A queue layout of a graph is an ordering of its vertices (the spine) together with an edge coloring such that there are no two nested monochromatic edges, where two edges are nested if all four endpoints are distinct and the endpoints of one edge induce an interval on the spine containing the endpoints of the other edge. Then the queue number of a graph is the minimum number of colors in a queue layout. Every graph has a subdivision with queue number 2, as proved by Dujmović and Wood [4], who also showed that graphs with bounded queue number form a class with bounded expansion. A challenging open problem in the area of queue layouts is to decide whether planar graphs have constant queue number (see e.g. [3]).
1.5. Proof overview. In the proof we use a characterization of classes with bounded expansion in terms of p-centered colorings. A p-centered coloring of a graph G is a vertex coloring of G such that, for every connected subgraph H of G, either some color is used exactly once in H, or at least p colors are used in H. Nešetřil and Ossona de Mendez [16] proved that a class C has bounded expansion if and only if there is a function f : N → N such that for every integer p 1 and every graph G ∈ C, there is a p-centered coloring of G using at most f (p) colors. Given a poset P of height h with cover graph in C, we work with a 2h-centered coloring φ of the cover graph with at most f (2h) colors.
Given this coloring φ, we focus on upsets of points x ∈ P : For each point y such that x y in P , we consider a sequence of cover relations x = z 1 < · · · < z k = y witnessing that x y, which we call a covering chain (thus this is a path from x going up to y in the diagram of P ). Such a covering chain defines a corresponding color sequence σ = (φ(z 1 ), . . . , φ(z k )), whose length is bounded by the height of P . We then exploit the fact that there are a bounded number of different color sequences and consider upsets of points w.r.t. a fixed color sequence σ. Focusing on such upsets, we uncover a wealth of structure, culminating in a proof that a certain family of subsets of points of P is laminar. In fact, we define one such laminar family for each subset of the set of color sequences. Once this is set up, we then exploit the underlying tree structure of these laminar families to bound the dimension of P .
We note that the idea for the first part of the proof-working with colored-upsets and proving that certain well-chosen families of sets are laminar-comes directly from a recent paper of Reidl, Villaamil, and Stavropoulos [23], who used it to obtain a new characterization of classes with bounded expansion in terms of 'neighborhood complexity'. Indeed, their proof method turned out to be perfectly fitted to approach our problem in a clean and simple way. As a result, the proof we present in this paper is shorter and simpler than the one we gave in the preliminary version of this paper [12]. Without going into details, that proof relied on a powerful decomposition of posets into layers called unfolding, introduced in the paper of Streib and Trotter [24], that emerged as a key technical tool in recent papers on poset dimension. We see it as an appealing feature of our proof that it avoids unfolding entirely. In fact, no background nor tool from poset theory is needed, except for the elementary notion of an alternating cycle (see Section 2.1).
The paper is organized as follows. In Section 2 we give the necessary definitions for all sparse classes of graphs depicted in Figure 2, as well as the necessary definitions regarding posets. Along the way, we also describe constructions of posets showing that Theorem 1 cannot be extended to the classes in grey in Figure 2. In Section 3 we give the proof of Theorem 1.

Definitions and preliminaries
2.1. Posets. Let us start with basic notions about posets. All posets considered in this paper are finite. Elements of a poset P are called points. Points x, y ∈ P are said to be comparable in P if x y or x y in P . Otherwise x and y are incomparable in P . A set of points C ⊆ P is a chain in P if the points in C are pairwise comparable. The height of P is the maximum size of a chain in P . We write x < y in P if it holds that x y and x = y. For distinct x, y ∈ P , if x < y in P and there is no z ∈ P with x < z < y in P then x < y is a cover relation of P . By cover(P ) we denote the cover graph of P , the (undirected) graph defined on the points of P where edges correspond to cover relations of P .
A linear extension L of P is a linear order on the ground set of P such that x y in L whenever x y in P . Linear extensions L 1 , . . . , L d form a realizer of P if their intersection is equal to P , that is, x y in P if and only if x y in L i for each i ∈ {1, . . . , d}. The dimension of P , denoted by dim(P ), is the least number d such that there is a realizer of P of size d.
We let Inc(P ) = {(x, y) ∈ P ×P | x is incomparable to y in P } denote the set of ordered pairs of incomparable points in P . A set I ⊆ Inc(P ) of incomparable pairs is reversible if there is a linear extension L of P that reverses each pair in I, that is, y < x in L for every (x, y) ∈ I.
We can rephrase the definition of dimension as follows: Assuming Inc(P ) = ∅, the dimension of P is the least positive integer d for which there exists a partition of Inc(P ) into d reversible sets. (Note that dim(P ) = 1 in case Inc(P ) = ∅.) In light of this statement, it is handy to have a simple criterion to decide when a set of incomparable pairs is reversible. This motivates the following definition. A sequence (x 1 , y 1 ), . . . , (x k , y k ) of k 2 pairs from Inc(P ) such that x i y i+1 holds in P for all i ∈ {1, . . . , k} (cyclically) is called an alternating cycle. It is well known (and easy to show) that a set I of incomparable pairs is reversible if and only if I does not contain any alternating cycle (see e.g. [25]). Indeed, this is the only fact about dimension that we will need in our proof.
2.2. Sparse graph classes. Next, we introduce the necessary definitions regarding graphs and give proper definitions for the graph classes mentioned in the introduction. All graphs in this paper are finite, simple, and undirected. Given a graph G we denote by V (G) and E(G) the vertex set and edge set of G, respectively. For a subset X ⊆ V (G) we denote by G[X] the subgraph of G induced by vertices in X. The distance between two vertices in G is the length of a shortest path between them. (Thus adjacent vertices are at distance 1; also, distance between two vertices in distinct components of G is set to +∞.) The set of all vertices at distance at most r from vertex v in G is denoted by N r G (v), and the subscript is omitted if G is clear from the context. The radius of a connected graph G is the least integer r 0 for which there is a vertex The treewidth of a graph G, denoted by tw(G), is the least integer t 0 for which there is a tree T and a family {T (v) | v ∈ V (G)} of non-empty subtrees of T such that |{v ∈ V (G) | x ∈ T (v)}| t + 1 for each node x of T , and V (T (u)) ∩ V (T (v)) = ∅ for each edge uv ∈ E(G). A class of graphs C has locally bounded treewidth if there exists a function f : R → R such that tw(G[N r (v)]) f (r) for every integer r 0, graph G ∈ C and vertex v ∈ V (G).
Given a partition X of the vertices of a graph G into non-empty parts inducing connected subgraphs, we denote by G/X the graph with vertex set X and edge set defined as follows: For two distinct distinct parts X, Y ∈ X , we have XY ∈ E(G/X ) if and only if there exist x ∈ X and y ∈ Y such that xy ∈ E(G). A graph H is a minor of G if H is isomorphic to a subgraph of G/X for some such partition X of V (G). A specialization of this notion is that of topological minors: H is a topological minor of a graph G if G contains a subgraph isomorphic to a subdivision of H. A class of graphs C is minor closed (topologically closed ) if every minor (topological minor, respectively) of a graph in C is also in C.
We pursue with the definitions of classes with bounded expansion and nowhere dense classes. A graph H is a depth-r minor (also known as an r-shallow minor ) of a graph G if H is isomorphic to a subgraph of G/X for some partition X of V (G) into nonempty parts inducing subgraphs of radius at most r. The greatest reduced average density (grad ) of rank r of a graph G, denoted by ∇ r (G), is defined as ∇ r (G) = max |E(H)| |V (H)| | H is a depth-r minor of G . A class of graphs C has bounded expansion if there exists a function f : R → R such that ∇ r (G) f (r) for every integer r 0 and graph G ∈ C. A class of graphs C is nowhere dense if for each integer r 0 there exists a graph which is not a depth-r minor of any graph G ∈ C.
It is easy to see that classes with locally bounded treewidth and classes with bounded expansion are nowhere dense. Note however that these two notions are incomparable.
Two classical examples of classes with locally bounded treewidth are graphs with bounded maximum degree, and graphs excluding some apex graph A as a minor. The latter is in fact a characterization of minor-closed classes with locally bounded treewidth: A minor-closed class C has locally bounded treewidth if and only if C excludes some apex graph, a fact originally proved by Eppstein [7].
Let us now define almost wide classes. For d 1, a set of vertices X in a graph G is d-independent if every two distinct vertices in X are at distance strictly greater than d in G. A class of graphs C is almost wide if there exists an integer s 0 such that for every integer d 1 there is a function f : R → R such that for every integer m 1, every graph G ∈ C of order at least f (m) contains a subset S of size at most s so that G − S has a d-independent set of size m. Nešetřil and Ossona de Mendez [17,Theorem 3.23] proved that a class of graphs excluding a fixed graph as a topological minor is almost wide. Moreover, they proved [17, Theorem 3.13] that every hereditary class of graphs that is almost wide is also nowhere dense. (Recall that a class is hereditary if it is closed under taking induced subgraphs.) 2.3. Posets with cover graphs in a nowhere dense class. As mentioned in the introduction, the statement of Theorem 1 cannot be pushed further towards nowhere dense classes. In fact, it already fails for classes with locally bounded treewidth and hereditary classes that are almost wide, as we now show. Our construction is based on the class of graphs G with ∆(G) girth(G), where ∆(G) and girth(G) denote the maximum degree and girth of G, respectively. This is a useful example of a hereditary class with locally bounded treewidth that is also almost wide but that does not have bounded expansion. (Indeed, this class is invoked several times in the textbook [18].) We will use in particular that the chromatic number of these graphs is unbounded. This is a well-known fact that can be shown in multiple ways; we can note for instance that the chromatic number of the n-vertex d-regular non-bipartite Ramanujan graphs with girth Ω d (log n) built by Lubotzky, Phillips, and Sarnak [14] have chromatic number Ω( √ d) (see [14]).

Proposition 2.
There exists a hereditary almost wide class of graphs C with locally bounded treewidth such that posets of height 2 with cover graphs in C have unbounded dimension.
Proof. For a graph G, the adjacency poset P G of G is the poset with point set This can be seen as follows. Fix a realizer L 1 , . . . , L d of P G . For every vertex v ∈ V (G), fix a number φ(v) = i such that b v < a v in L i . We claim that φ is a proper coloring of G. Consider any two adjacent vertices u and v in G and, say, φ(v) = i. Then a u b v < a v b u in L i , which witnesses that φ(u) = i. Therefore, dim(P G ) χ(G). Now let C denote the class of graphs G satisfying ∆(G) girth(G). As mentioned earlier, this class is hereditary, almost wide, and has locally bounded treewidth. This is not difficult to check (or see [18] for a proof).
The key observation about the class C in this context is that if G ∈ C, then cover(P G ) ∈ C. This can be seen as follows: First, clearly ∆(G) = ∆(cover(P G )), so it is enough to show girth(G) girth(cover(P G )). To show the latter, we remark that if C is a cycle of cover(P G ), then C naturally corresponds to a closed walk W in G of the same length. Moreover, every three consecutive vertices in that walk W are pairwise distinct, as follows from the adjacency poset construction. Hence, W contains a cycle, which is of length at most that of C. Therefore, girth(G) girth(cover(P G )), as claimed.
To summarize, graphs in C have unbounded chromatic number, implying that adjacency posets of these graphs have unbounded dimension. Yet, the cover graphs of these adjacency posets all belong to C, a hereditary almost wide class with locally bounded treewidth. This concludes the proof.

Proof of main theorem
There are a number of equivalent conditions for classes of graphs to have bounded expansion (see [20] for instance). As mentioned in the introduction, we use the following characterization in terms of p-centered colorings: A class C has bounded expansion if and only if there exists a function f : N → N such that for every integer p 1 and every graph G ∈ C there is a p-centered coloring of G using at most f (p) colors. Thus, the following theorem implies Theorem 1.
Theorem 3. If P is a poset of height h and its cover graph has a 2h-centered coloring using c colors, then dim(P ) 2 2h h+1 c h .
This section is devoted to the proof of Theorem 3. Let thus P be a poset of height h, and let φ be a 2h-centered coloring of the cover graph of P using colors from the set {1, . . . , c}.

3.1.
Signatures for covering chains. First, we refine the coloring φ of the cover graph of P as follows. For each x ∈ P , let h(x) denote the height of x in P , that is the size of a longest chain in P ending with x. For each x ∈ P we define φ * (x) := (φ(x), h(x)).
Note that φ * is a 2h-centered coloring as in general any refinement of a p-centered coloring is still a p-centered coloring, for every p 1.
We say that Q = (x 1 , x 2 , . . . , x ) is a covering chain of P if x i < x i+1 is a cover relation in P for each i ∈ {1, . . . , − 1}. In this case, we also say that Q is a covering chain from x 1 to x . Each covering chain Q = (x 1 , x 2 , . . . , x ) has a signature defined by (φ * (x 1 ), . . . , φ * (x )).
When σ = (φ * (x 1 ), . . . , φ * (x )) is the signature of Q, we also call Q a σ-covering chain. By our definition of φ * we have that the signature of Q is always proper, in the sense that no color appears more than once in the signature.
Let Σ be the set of all signatures of covering chains of P . A rough estimation yields that |Σ| h(hc) h . For each σ ∈ Σ, we let X σ denote the set of all points x in P such that there is a σ-covering chain starting from x. For illustration, each x in P belongs to X σ for σ = ((φ(x), h(x))). For x in P , the σ-upset U σ (x) of x is the set of all points y in P such that there is a σ-covering chain from x to y. Similarly, the σ-downset D σ (x) of x is the set of all points y in P such that there is a σ-covering chain from y to x.
Proof. Let Q x,y σ , Q x ,y σ be two σ-covering chains from x to y and from x to y , respectively. Suppose that these two paths share a common point z. We need to prove that U σ (x) = U σ (x ). Suppose for contradiction that U σ (x) = U σ (x ), and assume without loss of Let Q x ,y σ be a σ-covering chain from x to y (see Figure 3 for an illustration).
Clearly, the union U of the three paths Q x,y σ , Q x ,y σ and Q x ,y σ is a connected subgraph of the cover graph of P . Since these three paths have the same signature, we know that U is colored by φ * with at most h colors.
We claim that the two paths Q x,y σ and Q x ,y σ are vertex disjoint. Suppose that Q x,y σ and Q x ,y σ share a common element w. Combining the x-w portion of Q x,y σ with the w-y portion of Q x ,y σ we obtain a covering chain from x to y . Using that the signature σ is proper, it is easy to see that this covering chain from x to y also has signature σ. It follows that y ∈ U σ (x), contradicting our choice of y . Hence, Q x,y σ and Q x ,y σ are vertex disjoint, as claimed. It follows that no color of φ * is used exactly once on U , contradicting the fact that φ * is a 2h-centered coloring.
For σ ∈ Σ and elements x, y ∈ P , write x ∼ σ y if U σ (x) and U σ (y) intersect. By Lemma 4 we know that ∼ σ defines an equivalence relation on P ; denote by [x] σ the equivalence class of element x with respect to ∼ σ .
ForΣ ⊆ Σ, let XΣ denote the set of elements x of P for whichΣ is exactly the subset of signatures σ ∈ Σ such that U σ (x) is not empty, that is, Let FΣ be the family of subsets of XΣ defined as the union of the equivalence classes of ∼ σ for σ ∈Σ restricted to the set XΣ, plus all singletons in XΣ and the whole set XΣ. That is, A key observation is that these families are laminar. Recall that a family F is laminar if for every C, D ∈ F we have C ∩ D = ∅, or C ⊆ D, or D ⊆ C.
Proof. LetΣ and let C, D ∈ FΣ. We need to prove that C ∩ D = ∅, or C ⊆ D, or D ⊆ C. If one of the sets C, D is a singleton in XΣ or the whole set XΣ then we are done. Thus, the remaining case to consider is C = [c] σ ∩ XΣ and D = [d] σ ∩ XΣ, for c, d ∈ XΣ and σ, σ ∈Σ.
In order to get a contradiction, suppose that C − D = ∅, C ∩ D = ∅, and D − C = ∅. Thus, there are elements Since x 1 , x 2 , x 3 ∈ XΣ and σ, σ ∈Σ we know that the σ-upsets and σ -upsets of x 1 , x 2 and x 3 are not empty. Hence, there exist y 12 ∈ U σ (x 1 ) = U σ (x 2 ), y 23 ∈ U σ (x 2 ) = U σ (x 3 ), y 1 ∈ U σ (x 1 ), and y 3 ∈ U σ (x 3 ). Let Q x 1 ,y 1 σ denote a σ -covering chain from x 1 to y 1 , and define Q x 1 ,y 12 Consider the union of all these paths: Figure 3 for an illustration). Clearly, U is a connected subgraph of the cover graph of P , and all colors of φ * used on U come from σ and σ . Both σ and σ consist of at most h colors and we know moreover that they share at least one color, namely φ * (x 1 ) = φ * (x 2 ) = φ * (x 3 ). This means that U is colored by φ * with at most 2h − 1 colors.
Next, we show that each color of σ appears at least twice on U . To do so, we show that the two paths Q x 2 ,y 12 σ and Q x 3 ,y 3 σ are vertex disjoint. Indeed, if these two paths intersect then by Lemma 4 we would have U σ (x 2 ) = U σ (x 3 ) and therefore [ Analogously, we argue that each color of σ appears at least twice on U by showing that the two paths Q x 1 ,y 1 σ and Q x 2 ,y 23 σ are vertex disjoint. Indeed, if these two paths intersect then by Lemma 4 we would have U σ (x 1 ) = U σ (x 2 ) and therefore [ This shows that among the at most 2h − 1 colors used by φ * on U , none appears exactly once, contradicting the fact that φ * is a 2h-centered coloring.
Each laminar family of sets has a tree structure that is naturally associated to it: Let Σ ⊆ Σ. By Lemma 5, for each set S ∈ FΣ distinct from XΣ there is a unique inclusionwise minimal set S ∈ FΣ such that S S . We say that S is the parent of S. Consider the directed tree TΣ with vertices being sets in FΣ and with edges (S , S) whenever S is a parent of S. Then XΣ is the root of TΣ and the leaves of TΣ correspond to the singletons of XΣ. Observe also that for every x ∈ XΣ and σ ∈Σ the singletons of [x] σ ∩ XΣ are exactly the leaves of the subtree of TΣ rooted at [x] σ ∩ XΣ.
We take advantage of the tree structure of FΣ to define a linear order ≺Σ on XΣ that will be particularly useful. Fix an arbitrary preorder traversal of TΣ. Then, for distinct elements x, x ∈ XΣ we set x ≺Σ x if the singleton {x} is visited before {x } in the traversal of TΣ, and x ≺Σ x otherwise. In the first case we say that x lies to the left of x in XΣ, and to the right of x in XΣ in the second case. A crucial property of ≺Σ is that for every x ∈ XΣ and σ ∈Σ the points of [x] σ ∩ XΣ form an interval in ≺Σ. We emphasize this property with the following proposition.
3.3. Partitioning the incomparable pairs. Using the tools developed so far, we now show how to partition the set of incomparable pairs of P into a number of reversible sets that depends only on h. ForΣ ⊆ Σ let IncΣ(P ) := {(x, y) ∈ Inc(P ) | x ∈ XΣ, y ∈ P }. Clearly, Since |Σ| h(hc) h , there are at most 2 h(hc) h sets in the above partition of Inc(P ). We are going to refine this partition because the sets IncΣ(P ) are not necessarily reversible yet.
We need the following observation: Lemma 7. LetΣ ⊆ Σ and (x, y) ∈ IncΣ(P ). Then no two points x 1 , x 2 ∈ D σ (y) ∩ XΣ are such that Proof. Suppose to the contrary that there are points x 1 , x 2 ∈ D σ (y) ∩ XΣ such that We show that each set in this partition of Inc(P ) is reversible.
Proof. LetΣ ⊆ Σ and v ∈ VΣ, and suppose for a contradiction that IncΣ ,v (P ) is not reversible. Then IncΣ ,v (P ) contains an alternating cycle (x 1 , y 1 ), . . . , (x k , y k ). Shifting cyclically the pairs if necessary, we may assume that x 2 is leftmost among all x i 's with respect to ≺Σ. Consider a covering chain from x 1 to y 2 and another from x 2 to y 3 (if k = 2 then y 3 = y 1 ). Say they have signatures σ and σ respectively, and denote them by Q x 1 ,y 2 σ and Q x 2 ,y 3 σ . Clearly, σ, σ ∈Σ. Since x 2 ≺Σ x 1 and x 1 ∈ D σ (y 2 )∩XΣ, we conclude that v σ (x 2 , y 2 ) = 1.
As v(x 2 , y 2 ) = v = v(x 3 , y 3 ) we also obtain that v σ (x 3 , y 3 ) = 1 and v σ (x 2 , y 2 ) = 0. (In particular, this shows σ = σ .) Since v σ (x 3 , y 3 ) = 1 we know that there is x ∈ XΣ with x 3 ≺Σ x such that there is a σ-covering chain Q x ,y 3 σ from x to y 3 . Since x ∈ XΣ and σ ∈Σ, there is also a σ -covering chain Q x ,y σ from x to y , for some y in P . And finally, since x 2 ∈ XΣ and σ ∈Σ, there is a σ-covering chain Q x 2 ,y σ from x 2 to y , for some y in P . See Figure 4 for a possible situation. Now we consider the union U is a connected subgraph of the cover graph of P , and its vertives are colored by φ * with colors coming from σ and σ . Since σ and σ share at least one common color, namely φ * (x 2 ) = (φ(x 2 ), h(x 2 )), we see that at most 2h − 1 different colors appear on U .
We conclude that every color from σ is used at least twice on U (since Q x 2 ,y σ and Q x ,y 3 σ are disjoint), and that the same holds for colors from σ (since Q x 2 ,y 3 σ and Q x ,y σ are disjoint). This contradicts the fact that φ * is a 2h-centered coloring of the cover graph of P .
This concludes the proof of Theorem 3.

Concluding Remarks
Our main theorem reveals a connection between the notions of bounded expansion and order dimension. We think that this might actually provide a new characterization of classes with bounded expansion: Conjecture 9. Let C be a class of graphs closed under taking subgraphs. Then C has bounded expansion if and only if for each h 1, posets of height h whose cover graphs are in C have bounded dimension.
Note that Theorem 1 shows one of the two directions of this conjecture, the other one remains open.
As mentioned earlier, classes with bounded expansion can be characterized in various ways by asking that certain coloring numbers are bounded (this includes e.g. low treedepth colorings, generalised colorings, and centered colorings, see [21]). In most cases, if one asks instead the coloring numbers to be subpolynomially bounded in terms of the number n of vertices of the graph then this results in a characterization of nowhere dense classes. For instance, a class C is nowhere dense if and only if for every ε > 0 and p 1, every n-vertex graph in C has a p-centered coloring with O(n ε ) colors; see [10] for a survey of such characterizations. Perhaps one could similarly establish a subpolynomial bound on the dimension of bounded-height posets with cover graphs in a nowhere dense class? (This was suggested by Dan Král.) Problem 10. Is it true that if C is a nowhere dense class of graphs, then for every ε > 0 and h 1, posets on n points of height h and with cover graphs in C have dimension O(n ε )?