First-Fit is Linear on Posets Excluding Two Long Incomparable Chains

A poset is (r+s)(\underline{r}+\underline{s})-free if it does not contain two incomparable chains of size r and s, respectively. We prove that when r and s are at least 2, the First-Fit algorithm partitions every (r+s)(\underline{r}+\underline{s})-free poset P into at most 8(r − 1)(s − 1)w chains, where w is the width of P. This solves an open problem of Bosek et al. (SIAM J Discrete Math 23(4):1992–1999, 2010).     

Markov Chains on Graded Posets

We consider two types of discrete-time Markov chains where the state space is a graded poset and the transitions are taken along the covering relations in the poset. The first type of Markov chain goes only in one direction, either up or down in the poset (an up chain or down chain). The second type toggles between two adjacent rank levels (an up-and-down chain). We introduce two compatibility concepts between the up-directed transition probabilities (an up rule) and the down-directed (a down rule), and we relate these to compatibility between up-and-down chains. This framework is used to prove a conjecture about a limit shape for a process on Young’s lattice. Finally, we settle the questions whether the reverse of an up chain is a down chain for some down rule and whether there exists an up or down chain at all if the rank function is not bounded.     

The Involutory Dimension of Involution Posets

The involutory dimension, if it exists, of an involution poset P:=(P,,) is the minimum cardinality of a family of linear extensions of , involutory with respect to , whose intersection is the ordering . We show that the involutory dimension of an involution poset exists iff any pair of isotropic elements are orthogonal. Some characterizations of the involutory dimension of such posets are given. We study prime order ideals in involution posets and use them to generate involutory linear extensions of the partial ordering on orthoposets. We prove several of the standard results in the theory of the order dimension of posets for the involutory dimension of involution posets. For example, we show that the involutory dimension of a finite orthoposet does not exceed the cardinality of an antichain of maximal cardinality. We illustrate the fact that the order dimension of an orthoposet may be different from the involutory dimension.     

On-Line Dimension of Semi-Orders

We analyze the on-line dimension of partially ordered sets as a value of a two-person game between Algorithm and Spoiler. The game is played in rounds. Spoiler presents an on-line order of width at most w, one point at a time. Algorithm maintains its realizer, i.e., the set of d linear extensions which intersect to the presented order. Algorithm may not change the ordering of the previously introduced elements in the existing linear extensions. The value of the game val(w) is the least d such that Algorithm has a strategy against Spoiler presenting any order of width at most w. For interval orders Hopkins showed that val $(w) \leqslant 4w-4$ . We analyze the on-line dimension of semi-orders i.e., interval orders admitting a unit-length representation. For up-growing semi-orders of width w we prove a matching lower and upper bound of w. In the general (not necessarily up-growing) case we provide an upper bound of 2w.     

Order Dimension,Strong Bruhat Order and Lattice Properties for Posets

We determine the order dimension of the strong Bruhat order on finite Coxeter groups of types A, B and H. The order dimension is determined using a generalization of a theorem of Dilworth: dim (P)=width(Irr(P)), whenever P satisfies a simple order-theoretic condition called here the dissective property (or clivage). The result for dissective posets follows from an upper bound and lower bound on the dimension of any finite poset. The dissective property is related, via MacNeille completion, to the distributive property of lattices. We show a similar connection between quotients of the strong Bruhat order with respect to parabolic subgroups and lattice quotients.     

On Weighted Kernels of Two Posets

A recent result of Aharoni Berger and Gorelik (Order 31(1), 35–43, 2014) is a weighted generalization of the well-known theorem of Sands Sauer and Woodrow (Theory Ser. B 33(3), 271–275, 1982) on monochromatic paths. The authors prove the existence of a so called weighted kernel for any pair of weighted posets on the same ground set. In this work, we point out that this result is closely related to the stable marriage theorem of Gale and Shapley (Amer. Math. Monthly 69(1), 9–15, 1962), and we generalize Blair’s theorem by showing that weighted kernels form a lattice under a certain natural order. To illustrate the applicability of our approach, we prove further weighted generalizations of the Sands Sauer Woodrow result.     

Forcing Posets with Large Dimension to Contain Large Standard Examples

The dimension of a poset P, denoted \(\dim (P)\), is the least positive integer d for which P is the intersection of d linear extensions of P. The maximum dimension of a poset P with \(|P|\le 2n+1\) is n, provided \(n\ge 2\), and this inequality is tight when P contains the standard example \(S_n\). However, there are posets with large dimension that do not contain the standard example \(S_2\). Moreover, for each fixed \(d\ge 2\), if P is a poset with \(|P|\le 2n+1\) and P does not contain the standard example \(S_d\), then \(\dim (P)=o(n)\). Also, for large n, there is a poset P with \(|P|=2n\) and \(\dim (P)\ge (1-o(1))n\) such that the largest d so that P contains the standard example \(S_d\) is o(n). In this paper, we will show that for every integer \(c\ge 1\), there is an integer \(f(c)=O(c^2)\) so that for large enough n, if P is a poset with \(|P|\le 2n+1\) and \(\dim (P)\ge n-c\), then P contains a standard example \(S_d\) with \(d\ge n-f(c)\). From below, we show that \(f(c)={\varOmega }(c^{4/3})\). On the other hand, we also prove an analogous result for fractional dimension, and in this setting f(c) is linear in c. Here the result is best possible up to the value of the multiplicative constant.     

Posets with Cover Graph of Pathwidth two have Bounded Dimension

Joret, Micek, Milans, Trotter, Walczak, and Wang recently asked if there exists a constant d such that if P is a poset with cover graph of P of pathwidth at most 2, then dim(P)=d. We answer this question in the affirmative by showing that d=17 is sufficient. We also show that if P is a poset containing the standard example S ₅ as a subposet, then the cover graph of P has treewidth at least 3.     

On the Decomposition of Order-Separable Posets of Countable Width into Chains

Order - A partially ordered set X has countable width if and only if every collection of pairwise incomparable elements of X is countable. It is order-separable if and only if there is a countable...     

Dimension Preserving Contractions and a Finite List of 3-Irreducible Posets

This paper introduces new poset operations—dimension-preserving contractions. These contractions are used to change a poset into a similar, but simpler, poset with the same dimension. In particular, they can be used to turn the well-known infinite list of 3-irreducible posets into seventeen 3-irreducible, noncontractible posets (up to duality).     

On the Dimension of Posets with Cover Graphs of Treewidth 2

In 1977, Trotter and Moore proved that a poset has dimension at most 3 whenever its cover graph is a forest, or equivalently, has treewidth at most 1. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth 3. In this paper we focus on the boundary case of treewidth 2. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth 2 (Biró, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth 2. We show that it is indeed the case: Every such poset has dimension at most 1276.     

Degenerate Convex Hulls On-Line in Any Fixed Dimension

Randomized algorithms have, since the pioneering work of Clarkson and Shor, occupied the front stage of computational geometry. Yet despite their simplicity, they often cannot handle or be extended to cope with degenerate cases. The main goal of this paper is to show how, for the special case of convex hulls, a simple modification of the formulation of an on-line algorithm by Boissonnat et al., based on that of Clarkson and Shor, can handle the case of degenerate sets of points for computing convex hulls on-line in R ^d , for a fixed . At the same time, a standard randomized analysis allows us to prove the expected time complexity to be within , where k is the dimension of the convex hull. The latter bound is always . The analysis uses connections between regions, pivots, flags, and barycentric triangulations. Received May 30, 1998, and in revised form March 26, 1999.     

Planar Posets,Dimension, Breadth and the Number of Minimal Elements

In recent years, researchers have shown renewed interest in combinatorial properties of posets determined by geometric properties of its order diagram and topological properties of its cover graph. In most cases, the roots for the problems being studied today can be traced back to the 1970’s, and sometimes even earlier. In this paper, we study the problem of bounding the dimension of a planar poset in terms of the number of minimal elements, where the starting point is the 1977 theorem of Trotter and Moore asserting that the dimension of a planar poset with a single minimal element is at most 3. By carefully analyzing and then refining the details of this argument, we are able to show that the dimension of a planar poset with t minimal elements is at most 2t + 1. This bound is tight for t = 1 and t = 2. But for t ≥ 3, we are only able to show that there exist planar posets with t minimal elements having dimension t + 3. Our lower bound construction can be modified in ways that have immediate connections to the following challenging conjecture: For every d ≥ 2, there is an integer f(d) so that if P is a planar poset with dim(P) ≥ f(d), then P contains a standard example of dimension d. To date, the best known examples only showed that the function f, if it exists, satisfies f(d) ≥ d + 2. Here, we show that lim _d→∞ f(d)/d ≥ 2.     

Schmidt's Conjecture on Normality for Dimension Two

The aim of this article is to prove the two-dimensional case of Wolfgang Schmidt's conjecture for normality with respect to matrices. Specifically we show that if S and T are two by two almost integer ergodic matrices, then normality with respect to S implies normality with respect to T if and only if S^p = T^q for some positive integers p and q.     

A Non-Messing-Up Phenomenon for Posets

We classify finite posets with a particular sorting property, generalizing a result for rectangular arrays. Each poset is covered by two sets of disjoint saturated chains such that, for any original labeling, after sorting the labels along both sets of chains, the labels of the chains in the first set remain sorted. We also characterize posets with more restrictive sorting properties. Received October 19, 2005     

Energy Scattering Theory for Electromagnetic NLS in Dimension Two

We study the well-posedness and long-time behavior of solution to both defocusing and focusing nonlinear Schr?dinger equations with scaling critical magnetic potentials in dimension two.In the defocusing case, and under the assumption that the initial data is radial, we prove interaction Morawetz-type inequalities and show the scattering holds in the energy space. The magnetic potential considered here is the Aharonov–Bohm potential which decays likely the Coulomb potential |x|~(-1).     

A Local-Global Principle for Macaulay Posets

We consider the shadow minimization problem (SMP) for Cartesian powers P ⁿ of a Macaulay poset P. Our main result is a local-global principle with respect to the lexicographic order L ⁿ . Namely, we show that under certain conditions the shadow of any initial segment of the order L ⁿ for n 3 is minimal iff it is so for n = 2. These conditions include such poset properties as additivity, shadow increasing, final shadow increasing and being rank-greedy. We also show that these conditions are essentially necessary for the lexicographic order to provide nestedness in the SMP.