On then-cutset property

For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖?k: Ifc(P)?n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 ⁿ denotes the Boolean lattice of all subsets of ann-element set, andB _n denotes the set of atoms and co-atoms of 2 ⁿ . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 ⁿ , thenc(P)?2^[n/2]?1; (iii) for everyn>3 there is a partially ordered setP containing 2 ⁿ such thatc(P)<c(2 ⁿ ); (iv) for every positive integern there is a positive integerN such that, ifB _m is contained in a partially ordered set having then-cutset property, thenm?N.     

Ladders in ordered sets

An ordered set P is said to have the 2-cutset property if for every element x of P there is a subset S of P whose elements are noncomparable to x, such that |S|2 and such that every maximal chain in P meets {x}S. It is shown that if P has the 2-cutset property and has width n then P contains a ladder of length [1/2(n–3)].     

Fractional dimension of partial orders

Given a partially ordered setP=(X, ), a collection of linear extensions {L ₁,L ₂,...,L _r } is arealizer if, for every incomparable pair of elementsx andy, we havex<y in someL _i (andy<x in someL _j ). For a positive integerk, we call a multiset {L ₁,L ₂,...,L _t } ak-fold realizer if for every incomparable pairx andy we havex<y in at leastk of theL _i 's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask. We prove various results about the fractional dimension of a poset.Research supported in part by the Office of Naval Research.     

A note on the circle containment problem

We extend a result due to Bárányet al. and prove the following theorem: given any setS ofn points in the plane, there are pointsx andy inS, such that every circle that containsx andy contains at least [5/84(n – 2)] other points ofS.     

Balancing poset extensions

We show that any finite partially ordered setP (not a total order) contains a pair of elementsx andy such that the proportion of linear extensions ofP in whichx lies belowy is between 3/11 and 8/11. A consequence is that the information theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: ifX is a totally ordered set about which we are given some partial information, and ife(X) is the number of total orderings ofX compatible with this information, then it is possible to sortX using no more thanC log₂ e (X) comparisons whereC is approximately 2.17.Supported in part by NSF Grant MCS83-01867.     

Illuminating high-dimensional convex sets

A setL of points in thed-spaceE ^d is said toilluminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d if for every setS _i inF and every pointx in the boundary ofS _i there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d . We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets.     

Identifying variable points on a smooth curve

LetX be a compact Riemann surface,n ≥ 2 an integer andx = [x ₁, …,x _n ] an unorderedn-tuple of not necessarily distinct points onX. Byf _x :X →Y _x we denote the normalization which identifies thex ₁, …,x _n and maps them to the only and universal singularity of a complex curveY _x . Thenf _x depends holomorphically onx and is uniquely determined by this parameter. In this context we consider the fine moduli spaceQ _X of all complex-analytic quotients ofX and construct a morphismS ⁿ (X) →Q _X such that each and everyf _x corresponds to the image of the pointx on then-fold symmetric powerS ⁿ (X). For everyn ≥ 2 the mappingS ⁿ (X) →Q _X is a closed embedding; the points of its image have embedding dimensionn(n ? 1) inQ _X . HenceS ²(X) is a smooth connected component ofQ _X . On the other hand, a deformation argument yields thatS ⁿ (X) is part of the singular locus of the complex spaceQ _X provided thatn ≥ 3.     

Retractability and the fixed point property for products

LetP, Q be ordered sets and letaP. IfP \ {a} is a retract ofP and setsP and {xP:x>p} (or its dual) have the fixed point property then, for each chain complete setP,P×Q has the fixed point property if and only if (P\{a})×Q has this property. This establishes the fixed point property for some products of ordered sets which are beyond the reach of all known product theorems.The work of the first of authors was supported in part by the K.B.N. Grant No. 2 2037 92 03.     

On Erdős-Rado numbers

In this paper new proofs of the Canonical Ramsey Theorem, which originally has been proved by Erd?s and Rado, are given. These yield improvements over the known bounds for the arising Erd?s-Rado numbersER(k; l), where the numbersER(k; l) are defined as the least positive integern such that for every partition of thek-element subsets of a totally orderedn-element setX into an arbitrary number of classes there exists anl-element subsetY ofX, such that the set ofk-element subsets ofY is partitioned canonically (in the sense of Erd?s and Rado). In particular, it is shown that $$2^{c1} .l^2 \leqslant ER(2;l) \leqslant 2^{c_2 .l^2 .\log l} $$ for every positive integerl≥3, wherec ₁,c ₂ are positive constants. Moreover, new bounds, lower and upper, for the numbersER(k; l) for arbitrary positive integersk, l are given.     

Fixed point theory and product,sub-, super-spaces

In this paper, we definen-segmentwise metric spaces and then we prove the following results:

1. (i)|Let (X, d) be ann-segmentwise metric space. ThenX ⁿ has the fixed point property with respect to uniformly continuous bounded functions if and only if, for any continuous functionF: C ^*(X) → C^*(X) and for anyn-tuple of distinct points x₁, x₂, ?, x_n ∈X, there exists anh ∈C ^*(X) such that $$F(h)(x_1 ) = h(x_1 ),i = 1,2,...,n;$$ whereC ^*(X) has either the uniform topology or the subspace product (Tychonoff) topology \((C^ * (X) \subseteq X^X )\) .
2. LetX _i (i = 1, 2, ?) be countably compact Hausdorff spaces such thatX ₁ × ? × X_n has the fixed point property for alln ∈N Then the product spaceX ₁ × X₂ × ? has the fixed point property. We shall also discuss several problems in the Fixed Point Theory and give examples if necessary. Among these examples, we have:
3. There exists a connected metric spaceX which can be decomposed as a disjoint union of a closed setA and an open setB such thatA andB have the fixed point property andX does not have.
4. There exists a locally compact metrizable spaceX which has the fixed point property but its one-point compactificationX ⁺ does not have the fixed point property.

Other relevant results and examples will be presented in this paper.     

Injective Banach spaces of typeC(T)

A Banach spaceX is aP _λ-space if wheneverX is isometrically embedded in another Banach spaceY there is a projection ofY ontoX with norm at most λ.C(T) denotes the Banach space of continuous real-valued functions on the compact Hausdorff spaceT. T satisfies the countable chain condition (CCC) if every family of disjoint non-empty open sets inT is countable.T is extremally disconnected if the closure of every open set inT is open. The main result is that ifT satisfies the CCC andC(T) is aP _λ-space, thenT is the union of an open dense extremally disconnected subset and a complementary closed setT _Asuch thatC(T_A) is aP _λ?1-space.     

Deviation of elements of a Banach space from a system of subspaces

We prove that if X is a real Banach space, Y ₁ ? Y ₂ ? ... is a sequence of strictly embedded closed linear subspaces of X, and d ₁ ≥ d ₂ ≥ ... is a nonincreasing sequence converging to zero, then there exists an element x ∈ X such that the distance ρ(x, Y _n ) from x to Y _n satisfies the inequalities d _n ≤ ρ(x, Y _n ) ≤ 8d _n for n = 1, 2, ....     

Tiling convex sets by translates

LetK be a compact, convex subset ofE ^dwhich can be tiled by a finite number of disjoint (on interiors) translates of some compact setY. Then we may writeK=X+Y, whereX is finite. The possible structures forK, X andY are completely determined under these conditions.     

The smallestn-uniform hypergraph with positive discrepancy

A two-coloring of the verticesX of the hypergraphH=(X, ε) by red and blue hasdiscrepancy d ifd is the largest difference between the number of red and blue points in any edge. A two-coloring is an equipartition ofH if it has discrepancy 0, i.e., every edge is exactly half red and half blue. Letf(n) be the fewest number of edges in ann-uniform hypergraph (all edges have sizen) having positive discrepancy. Erd?s and Sós asked: isf(n) unbounded? We answer this question in the affirmative and show that there exist constantsc ₁ andc ₂ such that $$\frac{{c_1 \log (snd(n/2))}}{{\log \log (snd(n/2))}} \leqq f(n) \leqq c_2 \frac{{\log ^3 (snd(n/2))}}{{\log \log (snd(n/2))}}$$ where snd(x) is the least positive integer that does not dividex.     

Homogeneity in finite ordered sets

A tower in an ordered set (X, ) is defined to be a subsetS ofX which has the property that for everysS there is a maximal chainC in {xX|xs} which is wholly contained inS. An ordered set (X, ) is called tower-homogeneous if every order isomorphism between towers in (X, ) can be extended to an automorphism of (X, ). It is shown that a finite ordered set is tower-homogeneous if and only if it can be built up from singletons stepwise by constructions of three different types.     

On certain non-Kahlerian strongly pseudoconvex manifolds

It has been conjectured that strongly pseudoconvex manifoldsX such that its exceptional setS is an irreducible curve can be embedded biholomorphically into some ? ^N ×P _m . In this paper we show that this is true, with one exception, namely when dim_? X = 3 and its first Chern classc ₁ (K _X ¦S) = 0 whereS ?P ₁ andK _X is the canonical bundle ofX. On the other hand, we explicitly exhibit such a 3-foldX that is not Kahlerian; also we construct non-Kahlerian strongly pseudoconvex 3-foldX whose exceptional setS is a ruled surface; those concrete examples naturally raise the possibility of classifying non-Kahlerian strongly pseudoconvex 3-folds.     

Sets of nonnegative matrices with positive inhomogeneous products

Let X be a set of k×k matrices in which each element is nonnegative. For a positive integer n, let P(n) be an arbitrary product of n matrices from X, with any ordering and with repetitions permitted. Define X to be a primitive set if there is a positive integer n such that every P(n) is positive [i.e., every element of every P(n) is positive]. For any primitive set X of matrices, define the index g(X) to be the least positive n such that every P(n) is positive. We show that if X is a primitive set, then g(X)?2^k?2. Moreover, there exists a primitive set Y such that g(Y) = 2^k?2.     

Semiorders and the 1/3–2/3 conjecture

A well-known conjecture of Fredman is that, for every finite partially ordered set (X, <) which is not a chain, there is a pair of elements x, y such that P(x, the proportion of linear extensions of (X, <) with x below y, lies between 1/3 and 2/3. In this paper, we prove the conjecture in the special case when (X, <) is a semiorder. A property we call 2-separation appears to be crucial, and we classify all locally finite 2-separated posets of bounded width.     

Extension of positive functionals on certain ordered spaces

An ordered linear spaceL is said to satisfy extension property (E1) if for every directed subspaceM ofL and positive linear functional ϕ onM, ϕ can be extended toL. A Riesz spaceL is said to satisfy extension property (E2) if for every sub-Riesz spaceM ofL and every real valued Riesz homomorphism ϕ onM, ϕ can be extended toL as a Riesz homomorphism. These properties were introduced by Schmidt in [5]. In this paper, it is shown that an ordered linear space has extension property (E1) if and only if it is order isomorphic to a function spaceL′ defined on a setX′ such that iff andg belong toL′ there exists a finite disjoint subsetM of the set of functions onX′ such that each off andg is a linear combination of the points ofM. An analogous theorem is derived for Riesz spaces with extension property (E2).