On Dilworth's decomposition theorem

For every countable po set P without infinite chains there exists a partition (C_j: j?I) of P into pairwise disjoint chains and an antichain A such that C_j∩A≠Ø for every i?I.     

A Ramsey theorem for partial orders with linear extensions

We prove a Ramsey theorem for finite sets equipped with a partial order and a fixed number of linear orders extending the partial order. This is a common generalization of two recent Ramsey theorems due to Sokić. As a bonus, our proof gives new arguments for these two results.     

The algebra of set functions II: An enumerative analogue of Hall’s theorem for bipartite graphs

Triesch (1997) [25] conjectured that Hall’s classical theorem on matchings in bipartite graphs is a special case of a phenomenon of monotonicity for the number of matchings in such graphs. We prove this conjecture for all graphs with sufficiently many edges by deriving an explicit monotonic formula counting matchings in bipartite graphs.This formula follows from a general duality theory which we develop for counting matchings. Moreover, we make use of generating functions for set functions as introduced by Lass [20], and we show how they are useful for counting matchings in bipartite graphs in many different ways.     

Minkowski’s theorem for arbitrary convex sets

V. Klee extended a well-known theorem of Minkowski to non-compact convex sets. We generalize Minkowski’s theorem to convex sets which are not necessarily closed.     

A panconnectivity theorem for bipartite graphs

Let $G$ be a simple $m\times n$ bipartite graph with $m\ge n$. We prove that if the minimum degree of $G$ satisfies $\delta \left(G\right)\ge m∕2+1$, then $G$ is bipanconnected: for every pair of vertices $x,y$, and for every appropriate integer $2\le ?\le 2n$, there is an $x,y$-path of length $?$ in $G$.     

Berge’s theorem for the maximum charge problem

In 1957 Berge [C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957) 842–844] established that a matching is maximum if and only if there are no augmenting paths in the graph. In this paper we prove Berge’s result for a generalization of the matching problem—the maximum charge problem with capacity constraints. We show that a charge is maximum if and only if there is no alternating path, or lasso, along which the charge can be augmented.     

On a vector space analogue of Kneser’s theorem

In a previous paper [X. Hou, K.H. Leung, Q. Xiang, A generalization of an addition theorem of Kneser, J. Number Theory 97 (2002) 1-9], the following result was established: let E⊂K be fields such that the algebraic closure of E in K is separable over E. Let A,B be E-subspaces of K such that 0<dim_EA<∞ and 0<dim_EB<∞. Then dim_EAB?dim_EA+dim_EB-dim_EH(AB), where AB is the E-space generated by {ab:a∈A,b∈B} and H(AB)={x∈K:xAB⊂AB}. The separability assumption was essential in the proof of this result. However, even without the separability assumption, no counterexample is known. The present paper shows that no counterexample can be found if dim_EA?5.     

A min-max theorem for plane bipartite graphs

We consider a partitioning problem, defined for bipartite and 2-connected plane graphs, where each node should be covered exactly once by either an edge or by a cycle surrounding a face. The objective is to maximize the number of face boundaries in the partition. This problem arises in mathematical chemistry in the computation of the Clar number of hexagonal systems. In this paper we establish that a certain minimum weight covering problem of faces by cuts is a strong dual of the partitioning problem. Our proof relies on network flow and linear programming duality arguments, and settles a conjecture formulated by Hansen and Zheng in the context of hexagonal systems [P. Hansen, M. Zheng, Upper Bounds for the Clar Number of Benzenoid Hydrocarbons, Journal of the Chemical Society, Faraday Transactions 88 (1992) 1621-1625].     

On a generalization of Jentzsch’s theorem

Let E be a compact subset of with connected, regular complement and let G(z) denote Green’s function of Ω with pole at ∞. For a sequence (p_n)_nΛ of polynomials with degp_n=n, we investigate the value-distribution of p_n in a neighbourhood U of a boundary point z₀ of E if G(z) is an exact harmonic majorant of the subharmonic functions

in . The result holds for partial sums of power series, best polynomial approximations, maximally convergent polynomials and can be extended to rational functions with a bounded number of poles.     

A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders

Let L=u ₁ , u ₂ , ..., u _k be a linear extension of a poset P. Each pair (u _i , u _i+1 ) of unrelated elements in P is called a jump of L. The jump number problem is to find L with the minimum number of jumps. The problem is known to be NP-hard even on bipartite posets. Here we present a linear time algorithm for it in 2-dimensional bipartite posets. We also discuss briefly some weighted cases.     

A combinatorial proof of Marstrand’s theorem for products of regular Cantor sets

In a paper from 1954 Marstrand proved that if K⊂R² has a Hausdorff dimension greater than 1, then its one-dimensional projection has a positive Lebesgue measure for almost all directions. In this article, we give a combinatorial proof of this theorem when K is the product of regular Cantor sets of class C^1+α, α>0, for which the sum of their Hausdorff dimension is greater than 1.     

A separation theorem for the weak s-convex orders

The present paper extends to higher degrees the well-known separation theorem decomposing a shift in the increasing convex order into a combination of a shift in the usual stochastic order followed by another shift in the convex order. An application in decision making under risk is provided to illustrate the interest of the result.     

On Fraïssé’s conjecture for linear orders of finite Hausdorff rank

We prove that the maximal order type of the wqo of linear orders of finite Hausdorff rank under embeddability is φ₂(0), the first fixed point of the ε-function. We then show that Fraïssé’s conjecture restricted to linear orders of finite Hausdorff rank is provable in  +“φ₂(0) is well-ordered” and, over , implies  +“φ₂(0) is well-ordered”.     

A Hermitian analogue of the Bröcker-Prestel theorem

The Bröcker-Prestel local-global principle characterizes weak isotropy of quadratic forms over a formally real field in terms of weak isotropy over the Henselizations and isotropy over the real closures of that field. A Hermitian analogue of this principle is presented for algebras of index at most two. An improved result is also presented for algebras with a decomposable involution, algebras of Pythagorean index at most two, and algebras over SAP and ED fields.     

A comparative analysis of methods for constructing weak orders from partial orders

This paper compares three methods (sequel, cardinal, maximal) for constructing a weak order from a partial order on a finite set. The constructed weak orders include the partial order. To evaluate the methods, several different selection disciplines were used to stochastically generate partial orders from a fixed linear order. The error of a weak order which includes a generated partial order is a function of the number of ordered pairs added to the partial order to get the weak order which are the reverse of ordered pairs in the fixed linear order. In all cases, the sequel and cardinal mean errors were much lower than the maximal mean error. In most but not all cases, the cardinal mean error was lower than the sequel mean error.     

On the equivalence of the Mizoguchi–Takahashi fixed point theorem to Nadler’s theorem

In this work, we prove that on a metrically convex complete metric space, the Mizoguchi–Takahashi theorem is equivalent to Nadler’s theorem. Also, we obtain its equivalence on a compact metric space.     

A higher order analogue of the Carathéodory-Julia theorem

A higher order analogue of the classical Carathéodory-Julia theorem on boundary derivatives is proved.