On-Line Chain Partitions of Orders: A Survey

On-line chain partition is a two-player game between Spoiler and Algorithm. Spoiler presents, point by point, a partially ordered set. Algorithm assigns incoming points (immediately and irrevocably) to the chains which constitute a chain partition of the order. The value of the game for orders of width w is a minimum number val(w) such that Algorithm has a strategy using at most val(w) chains on orders of width at most w. There are many recent results about variants of the general on-line chain partition problem. With this survey we attempt to give an overview over the state of the art in this field. As particularly interesting aspects of the article we see:

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.     

Symmetric 2-Structures,a Classification

We classify symmetric 2-structures ${(P, \mathfrak{G}_1, \mathfrak{G}_2, \mathfrak{K})}$ , i.e. chain structures which correspond to sharply 2-transitive permutation sets (E, Σ) satisfying the condition: “ ${(*) \, \, \forall \sigma, \tau \in \Sigma : \sigma \circ \tau^{-1} \circ \sigma \in \Sigma}$ ”. To every chain ${K \in \mathfrak{K}}$ one can associate a reflection ${\widetilde{K}}$ in K. Then (*) is equivalent to “ ${(**) \, \, \forall K \in \mathfrak{K} : \widetilde{K}(\mathfrak{K}) = \mathfrak{K}}$ ” and one can define an orthogonality “ ${\perp}$ ” for chains ${K, L \in \mathfrak{K}}$ by “ ${K \perp L \Leftrightarrow K \neq L \wedge \widetilde{K}(L) = L}$ ”. The classification is based on the cardinality of the set of chains which are orthogonal to a chain K and passing through a point p of K. For one of these classes (called point symmetric 2-structures) we proof that in each point there is a reflection and that the set of point reflections forms a regular involutory permutation set.     

Metrization of Weighted Graphs

We find a set of necessary and sufficient conditions under which the weight ${w: E \rightarrow \mathbb{R}^{+}}$ on the graph G = (V, E) can be extended to a pseudometric ${d : V \times V \rightarrow \mathbb{R}^{+}}$ . We describe the structure of graphs G for which the set ${\mathfrak{M}_{w}}$ of all such extensions contains a metric whenever w is strictly positive. Ordering ${\mathfrak{M}_{w}}$ by the pointwise order, we have found that the posets $({\mathfrak{M}_{w}, \leqslant)}$ contain the least elements ρ _0,w if and only if G is a complete k-partite graph with ${k \, \geqslant \, 2}$ . In this case the symmetric functions ${f : V \times V \rightarrow \mathbb{R}^{+}}$ , lying between ρ _0,w and the shortest-path pseudometric, belong to ${\mathfrak{M}_{w}}$ for every metrizable w if and only if the cardinality of all parts in the partition of V is at most two.     

Nash equilibria on topological semilattices

A function ${u : X \to \mathbb{R}}$ defined on a partially ordered set is quasi-Leontief if, for all ${x \in X}$ , the upper level set ${\{x\prime \in X : u(x\prime) \geq u(x)\}}$ has a smallest element; such an element is an efficient point of u. An abstract game ${u_{i} : \prod^{n}_{j=1} X_j \to \mathbb{R}, i \in \{1, \ldots , n\}}$ , is a quasi-Leontief game if, for all i and all ${(x_{j})_{j \neq i} \in \prod_{j \neq i} X_{j}, u_{i}((x_{j})_{j \neq i};-) : X_{i} \to \mathbb{R}}$ is quasi-Leontief; a Nash equilibrium x* of an abstract game ${u_{i} :\prod^{n}_{j=1} X_{j} \to \mathbb{R}}$ is efficient if, for all ${i, x^{*}_{i}}$ is an efficient point of the partial function ${u_{i}((x^{*}_{j})_{j \neq i};-) : X_{i} \to \mathbb{R}}$ . We establish the existence of efficient Nash equilibria when the strategy spaces X _i are topological semilattices which are Peano continua and Lawson semilattices.     

Descriptions of exceptional sets in the circles for functions from the Bergman space

Let D be a domain in $\mathbb{C}^2 $ . For w ∈ $\mathbb{C}$ , let D_w=\{z \in $\mathbb{C}$ \, \vert \, (z,w)\in D\}. If f is a holomorphic and square-integrable function in D, then the set E(D, f) of all w such that f(., w) is not square-integrable in D _w is of measure zero. We call this set the exceptional set for f. In this note we prove that for every 0 < r < 1, and every G _δ-subset E of the circle C(0,r)=\{z \in $\mathbb{C}$ \, \vert \, \vert z \vert = r \},there exists a holomorphic square-integrable function f in the unit ball B in $\mathbb{C}$ ² such that E(B, f) = E.     

Inequalities for the Coefficients of Meromorphic Starlike Functions with Nonzero Pole

In this article we consider functions f that are meromorphic and univalent in the unit disc ${\mathbb{D}}$ with pole at the point ${z = p \in (0, 1)}$ and having a Taylor expansion at the origin of the form $$f(z) = z + \sum _{n=2}^{\infty}a_n(f)z^n, \quad |z| < p.$$ The class of functions that satisfy the above conditions and map the unit disc such that ${\overline{\mathbb{C}} \setminus f(\mathbb{D})}$ is starlike with respect to a point w ₀ ( ≠ 0, ∞) will be denoted by Σ *(p, w ₀). We generalize and sharpen an inequality for a ₂(f), ${f \in \Sigma^*(p,w_0)}$ , proved by Miller (Proc Am Math Soc 80:607–613, 1980) by use of the coefficients a _n (f), n ≥ 3.     

Universal Polynomial Expansions of Harmonic Functions

Let Ω be a domain in ? ^N such that $\left(\mathbb{R}^{N}\cup\lbrace\infty\rbrace\right)\setminus\Omega$ is connected. It is known that, for each w?∈?Ω, there exist harmonic functions on Ω that are universal at w, in the sense that partial sums of their homogeneous polynomial expansion about w approximate all plausibly approximable functions in the complement of Ω. Under the assumption that Ω omits an infinite cone, it is shown that the connectedness hypothesis on $\left(\mathbb{R}^{N}\cup\lbrace\infty\rbrace\right)\setminus\Omega$ is essential, and that a harmonic function which is universal at one point is actually universal at all points of Ω.     

A ℤ-Simplex Algorithm with partial updates

The Simplex primal and dual methods, for the solution of $$\max \left\{ {c^T x:Ax = b, x \geqslant 0} \right\},$$ were presented previously in terms of certain bases ? and \(\mathbb{Y}\) ofN(A) andR(A ^T ) respectively. In these implementations, called the ?-Simplex Algorithm and the \(\mathbb{Y}\) -Dual Method, the bases ? and \(\mathbb{Y}\) (giving the edges of the polyhedron in question at the given basic feasible solution) are updated at each iteration. In this paper we show that only partial updates of ? are needed in the ?-Simplex Algorithm, analogously to the partial updates in the Revised Simplex Algorithm. Similar results can be given for the \(\mathbb{Y}\) -Dual Method.     

Analogues of Ramanujan’s partition identities

Ramanujan discovered that $$\sum_{n=0}^\infty p(5n+4)q^n=5 \prod_{j=1}^\infty \frac{(1-q^{5j})^5}{(1-q^j)^6}, $$ where p(n) is the number of partitions of n. Recently, H.-C. Chan and S. Cooper, and H.H. Chan and P.C. Toh established several analogues of Ramanujan’s partition identities by employing the theory of modular functions. Very recently, N.D. Baruah and K.K. Ojah studied the partition function $p_{[c^{l}d^{m}]}(n)$ which is defined by $$\sum_{n=0}^\infty p_{[c^ld^m]}(n)q^n= \frac{1}{\prod_{j=1}^\infty (1-q^{cj})^{l}(1-q^{dj})^m}. $$ They discovered some analogues of Ramanujan’s partition identities and deduced several interesting partition congruences. In this paper, we provide a uniform method to prove some of their results by utilizing an addition formula. In the process, we also establish some new analogues of Ramanujan’s partition identities and congruences for $p_{[c^{l}d^{m}]}(n)$ .     

A Representation of a Point Symmetric 2-Structure by a Quasi-Domain

In a symmetric 2-structure ${\Sigma =(P,\mathfrak{G}_1,\mathfrak{G}_2,\mathfrak{K})}$ we fix a chain ${E \in \mathfrak{K}}$ and define on E two binary operations “+” and “·”. Then (E,+) is a K-loop and for ${E^* := E {\setminus}\{o\}}$ , (E ^*,·) is a Bol loop. If ${\Sigma}$ is even point symmetric then (E,+ ,·) is a quasidomain and one has the set ${Aff(E,+,\cdot) := \{a^+\circ b^\bullet | a \in E, b \in E^*\}}$ of affine permutations. From Aff(E, +, ·) one can reproduce via a “chain derivation” the point symmetric 2-structure ${\Sigma}$ .     

Vector partition functions and generalized dahmen and micchelli spaces

This is the first of a series of papers on partition functions and the index theory of transversally elliptic operators. In this paper we only discuss algebraic and combinatorial issues related to partition functions. The applications to index theory are in [4], while in [5] and [6] we shall investigate the cohomological formulas generated by this theory. Here we introduce a space of functions on a lattice which generalizes the space of quasipolynomials satisfying the difference equations associated to cocircuits of a sequence of vectors X, introduced by Dahmen and Micchelli [8]. This space $ \mathcal{F}(X) $ contains the partition function $ {\mathcal{P}_{(X)}} $ . We prove a “localization formula” for any f in $ \mathcal{F}(X) $ , inspired by Paradan's decomposition formula [12]. In particular, this implies a simple proof that the partition function $ {\mathcal{P}_{(X)}} $ is a quasi-polynomial on the Minkowski differences $ \mathfrak{c} - B(X) $ , where c is a big cell and B(X) is the zonotope generated by the vectors in X, a result due essentially to Dahmen and Micchelli.     

Common Borel Radii of an Algebroid Function and Its Derivative

In this article, by comparing the characteristic functions, we prove that for any ν-valued algebroid function w(z) defined in the open unit disk with ${\limsup_{r\rightarrow1-}T(r,w)/\log\frac{1}{1-r}=\infty}$ and the hyper order ρ ₂(w)?=?0, the distribution of the Borel radii of w(z) and w′(z) is the same. This is the extension of G. Valiron’s conjecture for the meromorphic functions defined in ${\widehat{\mathbb{C}}}$ .     

Algebras of Convolution Type Operators with Piecewise Slowly Oscillating Data. II: Local Spectra and Fredholmness

Let ${\mathcal{B}_{p,w}}$ be the Banach algebra of all bounded linear operators acting on the weighted Lebesgue space ${L^p(\mathbb{R},w)}$ , where ${p\in(1,\infty)}$ and w is a Muckenhoupt weight. We study the Banach subalgebra ${\mathfrak{U}_{p,w}}$ of ${\mathcal{B}_{p,w}}$ generated by all multiplication operators aI ( ${a\in PSO^\diamond}$ ) and all convolution operators W ⁰(b) ( ${b\in PSO_{p,w}^\diamond}$ ), where ${PSO^\diamond\subset L^\infty(\mathbb{R})}$ and ${PSO_{p,w}^\diamond\subset M_{p,w}}$ are algebras of piecewise slowly oscillating functions that admit piecewise slowly oscillating discontinuities at arbitrary points of ${\mathbb{R}\cup\{\infty\}}$ , and M _p,w is the Banach algebra of Fourier multipliers on ${L^p(\mathbb{R},w)}$ . Under some conditions on the Muckenhoupt weight w, using results of the local study of ${\mathfrak{U}_{p,w}}$ obtained in the first part of the paper and applying the theory of Mellin pseudodifferential operators and the two idempotents theorem, we now construct a Fredholm symbol calculus for the Banach algebra ${\mathfrak{U}_{p,w}}$ and establish a Fredholm criterion for the operators ${A\in\mathfrak{U}_{p,w}}$ in terms of their Fredholm symbols. In four partial cases we obtain for ${\mathfrak{U}_{p,w}}$ more effective results.     

Jump number and width

The maximum jump number of ordered sets having width w and tower number t, denoted by s(w, t), satisfies $$c_l tw\lg w \leqslant s\left( {w,t} \right) \leqslant tw\lg w$$ for some positive constants c ₁ and c ₂. Specifically, we can obtain c ₁=1/8 and c ₂<11/10. When w and t are sufficiently large and w is a power of 2, then $$\left( {\frac{1}{2} - \varepsilon } \right)tw\lg w \leqslant s\left( {w,t} \right) < \frac{7}{{10}}tw\lg w$$ This gives an answer to a problem posed by W. T. Trotter ([3], Problem 15).     

Algebras of Convolution Type Operators with Piecewise Slowly Oscillating Data. I: Local and Structural Study

Let ${\mathcal{B}_{p,w}}$ be the Banach algebra of all bounded linear operators acting on the weighted Lebesgue space ${L^{p}(\mathbb{R}, w)}$ , where ${p \in (1, \infty)}$ and w is a Muckenhoupt weight. We study the Banach subalgebra ${\mathfrak{A}_{p,w}}$ of ${\mathcal{B}_{p,w}}$ generated by all multiplication operators aI ( ${a \in PSO^{\diamond}}$ ) and all convolution operators W ⁰(b) ( ${b \in PSO_{p,w}^{\diamond}}$ ), where ${PSO^{\diamond} \subset L^{\infty}(\mathbb{R})}$ and ${PSO_{p,w}^{\diamond} \subset M_{p,w}}$ are algebras of piecewise slowly oscillating functions that admit piecewise slowly oscillating discontinuities at arbitrary points of ${\mathbb{R} \cup \{\infty\}}$ , and M _p,w is the Banach algebra of Fourier multipliers on ${L^{p}(\mathbb{R}, w)}$ . Under some conditions on the Muckenhoupt weight w, we construct a Fredholm symbol calculus for the Banach algebra ${\mathfrak{A}_{p,w}}$ and establish a Fredholm criterion for the operators ${A \in \mathfrak{A}_{p,w}}$ in terms of their Fredholm symbols. To study the Banach algebra ${\mathfrak{A}_{p,w}}$ we apply the theory of Mellin pseudodifferential operators, the Allan–Douglas local principle, the two idempotents theorem and the method of limit operators. The paper is divided in two parts. The first part deals with the local study of ${\mathfrak{A}_{p,w}}$ and necessary tools for studying local algebras.     

The normal distribution and repeated games

For a reperated zero-sum two-person game with incomplete information discussed byZamir, it is proved here that \(\mathop {\lim }\limits_{n \to \infty } \sqrt n v_n (p) = \phi (p)\) whereφ (p) is the normal density function evaluated at itsp-quantile (i.e. \(\phi (p) = \frac{1}{{\sqrt {2\pi } }}e^{ - ({1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2})x^2 } p\) where \(\frac{1}{{\sqrt {2\pi } }}\mathop {\smallint ^p }\limits_{ - \infty }^x e^{ - ({1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2})x^2 } dx = p\) . Here for 0?p?1, (p, 1 ?p) is the a priori probability distribution on two states of nature, the actual state of nature is known to the maximizer but not to the minimizer.v _n (p) is the minimax value of the game withn stages.     

Balanced domains and convexity

For a quasi-balanced domain, we study holomorphic mappings ${F : D \times D \to D}$ such that F(z, z) = z and F(z, w) = F(w, z) for any ${z, w \in D}$ . We show that in many cases the existence of such a function is equivalent to the convexity of the domain D.     

Geometric ergodicity and the spectral gap of non-reversible Markov chains

We argue that the spectral theory of non-reversible Markov chains may often be more effectively cast within the framework of the naturally associated weighted-L _∞ space ${L_\infty^V}$ , instead of the usual Hilbert space L ₂?=?L ₂(π), where π is the invariant measure of the chain. This observation is, in part, based on the following results. A discrete-time Markov chain with values in a general state space is geometrically ergodic if and only if its transition kernel admits a spectral gap in ${L_\infty^V}$ . If the chain is reversible, the same equivalence holds with L ₂ in place of ${L_\infty^V}$ . In the absence of reversibility it fails: There are (necessarily non-reversible, geometrically ergodic) chains that admit a spectral gap in ${L_\infty^V}$ but not in L ₂. Moreover, if a chain admits a spectral gap in L ₂, then for any ${h\in L_2}$ there exists a Lyapunov function ${V_h\in L_1}$ such that V _h dominates h and the chain admits a spectral gap in ${L_\infty^{V_h}}$ . The relationship between the size of the spectral gap in ${L_\infty^V}$ or L ₂, and the rate at which the chain converges to equilibrium is also briefly discussed.     

On the Relaxed Colouring Game and the Unilateral Colouring Game

In the paper we introduce the new game—the unilateral \({\mathcal{P}}\) -colouring game which can be used as a tool to study the r-colouring game and the (r, d)-relaxed colouring game. Let be given a graph G, an additive hereditary property \({\mathcal {P}}\) and a set C of r colours. In the unilateral \({\mathcal {P}}\) -colouring game similarly as in the r-colouring game, two players, Alice and Bob, colour the uncoloured vertices of the graph G, but in the unilateral \({\mathcal {P}}\) -colouring game Bob is more powerful than Alice. Alice starts the game, the players play alternately, but Bob can miss his move. Bob can colour the vertex with an arbitrary colour from C, while Alice must colour the vertex with a colour from C in such a way that she cannot create a monochromatic minimal forbidden subgraph for the property \({\mathcal {P}}\) . If after |V(G)| moves the graph G is coloured, then Alice wins the game, otherwise Bob wins. The \({\mathcal {P}}\) -unilateral game chromatic number, denoted by \({\chi_{ug}^\mathcal {P}(G)}\) , is the least number r for which Alice has a winning strategy for the unilateral \({\mathcal {P}}\) -colouring game with r colours on G. We prove that the \({\mathcal {P}}\) -unilateral game chromatic number is monotone and is the upper bound for the game chromatic number and the relaxed game chromatic number. We give the winning strategy for Alice to play the unilateral \({\mathcal {P}}\) -colouring game. Moreover, for k ≥  2 we define a class of graphs \({\mathcal {H}_k =\{G|{\rm every \;block \;of\;}G \; {\rm has \;at \;most}\; k \;{\rm vertices}\}}\) . The class \({\mathcal {H}_k }\) contains, e.g., forests, Husimi trees, line graphs of forests, cactus graphs. Let \({\mathcal {S}_d}\) be the class of graphs with maximum degree at most d. We find the upper bound for the \({\mathcal {S}_2}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_3}\) and we study the \({\mathcal {S}_d}\) -unilateral game chromatic number for graphs from \({\mathcal {H}_4}\) for \({d \in \{2,3\}}\) . As the conclusion from these results we obtain the result for the d-relaxed game chromatic number: if \({G \in \mathcal {H}_k}\) , then \({\chi_g^{(d)}(G) \leq k + 2-d}\) , for \({k \in \{3, 4\}}\) and \({d \in \{0, \ldots, k-1\}}\) . This generalizes a known result for trees.