Compactness and subsets of ordered sets that meet all maximal chains

LetP be a chain complete ordered set. By considering subsets which meet all maximal chains, we describe conditions which imply that the space of maximal chains ofP is compact. The symbolsP ₁ andP ₂ refer to two particular ordered sets considered below. It is shown that the space of maximal chains (P) is compact ifP satisfies any of the following conditions: (i)P contains no copy ofP ₁ or its dual and all antichains inP are finite. (ii)P contains no properN and every element ofP belongs to a finite maximal antichain ofP. (iii)P contains no copy ofP ₁ orP ₂ and for everyx inP there is a finite subset ofP which is coinitial abovex. We also describe an example of an ordered set which is complete and densely ordered and in which no antichain meets every maximal chain.     

Decomposition of convex figures into similar pieces

If a convex plane figureP can be decomposed into finitely many nonoverlapping convex figures such that one of these pieces is similar toP, thenP is a polygon. Also, ifP can be decomposed into infinitely many nonoverlapping sets such that each of the pieces is similar toP, thenP is a polygon.     

A Cellular Triangle Containing a Specified Point

 Let P be a set of finite points in the plane in general position, and let x be a point which is not contained in any of the lines passing through at least two points of P. A line l is said to be a k-bisector if both of the two closed half-planes determined by l contain at least k points of P. We show that if any line passing through x is a -bisector and does not contain two or more points of P, then there exist three points P ₁, P ₂, P ₃ of P such that ΔP ₁ P ₂ P ₃ contains x and does not contain points of P in its interior, and such that each of the lines passing through two of them is a -bisector. Received: October 16, 1995 / Revised: October 16, 1996     

Minimal extensions of Π01 classes

A minimal extension of a Π⁰₁ class P is a Π⁰₁ class Q such that P ? Q, Q – P is infinite, and for any Π⁰₁ class R, if P ? R ? Q, then either R – P is finite or Q – R is finite; Q is a nontrivial minimal extension of P if in addition P and Q′ have the same Cantor‐Bendixson derivative. We show that for any class P which has a single limit point A, and that point of degree ≤ 0 , P admits a nontrivial minimal extension. We also show that as long as P is infinite, then P does not admit any decidable nontrivial minimal extension Q. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Minimal systems of arbitrary large mean topological dimension

Let G be a countable amenable group and P a polyhedron. The mean topological dimension mdim(X,G) of a subshift X ⊂ P ^G is a real number satisfying 0 ≤ mdim(X,G) ≤ dim(P), where dim(P) denotes the usual topological dimension of P. We give a construction of minimal subshifts X ⊂ P ^G with mean topological dimension arbitrarily close to dim(P).     

Sufficiency and completeness for classes of probability distributions generated by a single probability distribution

Let (Ω,A, P₀) denote a probability space andA some sub-σ-algebra ofA. Moreover,P _{P 0} stands for the set consisting of all probability distributionsP _{P 0} of the typeP _{P 0}(A) = ∫E _{P 0} (P _{A |B)dP,A ∈A, whereP is a probability distribution onA satisfyingP |B ≪P 0} |B. It is shown thatB is sufficient and (even totally) complete forP _{P 0}. This results is illustrated by examples. Finally, it is shown thatP _{P 0} ∈P _{P 0} is an extremal point ofP _{P 0} if and only ifP |B is {0, 1}-valued. Dedicated to the memory of Professor K. Behnen     

On Minimum-Weight k-Edge Connected Steiner Networks on Metric Spaces

For a given set of points P in a metric space, let w _k(P) denote the weight of minimum-weight k-edge connected Steiner network on P divided by the weight of minimum-weight k-edge connected spanning network on P, and let r _k=inf{w _k(P) |P}. We show in this paper that for any P, , for even k≥2 and , for odd k≥3. In particular, we prove that for any P in the Euclidean plane, w ₄(P) and w ₅(P) are greater than or equal to , and ; For any P in the rectilinear plane , for odd k≥5. In addition, we prove that there exists an O(|P|³)-time approximation algorithm for constructing a minimum-weight k-edge connected Steiner network which has approximation ratio of for even k and for odd k. Received: August 21, 1997 Revised: February 5, 1998     

Inequalities for the number of linear extensions

Lete(P) denote the number of linear extensions of a partial orderP. Interpreting the diagram ofP as a network, ande(P) as the value of a flow, we prove some upper and lower bounds fore(P). One of the consequences is the following. If the incomparability graph ofP can be covered by the incomparability graphs of ordersP ₁,P ₂,...,P _k thene(P) e(P ₁)e(P ₂)...e(P _k ).     

There Are Not Too Many Magic Configurations

A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for every line l determined by P, the sum of the weights of all points of P on l equals 1. We prove a conjecture of Murty from 1971 and show that if a set of n points P is a magic configuration, then P is in general position, or P contains n−1 collinear points, or P is a special configuration of 7 points. The research by Rom Pinchasi was supported by a Grant from the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

COMPARATIVE PROBABILITY ON THE C* ALGEBRA OF COMPACT OPERATORS

Abstract

Let A be a von Neumann algebra on a Hilbert space H and let P(A) denote the projections of A. A comparative probability (CP) on A (or more correctly on P(A)) is a preorder ? on P(A) satisfying:

0 ? P ? P ε P(A) with Q ≠ 0 for some Q ε P(A).

If P, Q ε P(A) then either P ? Q or Q ? P.

If P, Q and R are all in P(A) and P⊥R, Q⊥R, then P ? Q ? P + R ? Q + R.

Let τ be any of the usual locally convex topologies on A. We say ? is τ continuous if the interval topology induced on P(A) by ? is weaker than the τ topology on P(A). If μ an additive (completely additive) measure on P(A) then μ induces a uniformly (weakly) continuous CP ?μ on P(A) given by P ?_μ Q if μ(P) ? μ(Q). We show that if A is the C* algebra C(H) of compact operators on an infinite dimensional Hilbert space H, the converse is true under an extra boundedness condition on the CP which is automatically satisfied whenever the identity is present in A = P(C(H)).     

Path factors in cubic graphs

Let ? be a set of connected graphs. An ?‐factor of a graph is its spanning subgraph such that each component is isomorphic to one of the members in ?. Let P_k denote the path of order k. Akiyama and Kano have conjectured that every 3‐connected cubic graph of order divisible by 3 has a {P₃}‐factor. Recently, Kaneko gave a necessary and sufficient condition for a graph to have a {P₃, P₄, P₅}‐factor. As a corollary, he proved that every cubic graph has a {P₃, P₄, P₅}‐factor. In this paper, we prove that every 2‐connected cubic graph of order at least six has a {P_k ∣ k ≥ , 6}‐factor, and hence has a {P₃, P₄}‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 188–193, 2002; DOI 10.1002/jgt.10022     

Lattice polytopes,Hecke operators,and the Ehrhart polynomial

Let P be a simple lattice polytope. We define an action of the Hecke operators on E(P), the Ehrhart polynomial of P, and describe their effect on the coefficients of E(P). We also describe how the Brion–Vergne formula for E(P) transforms under the Hecke operators for nonsingular lattice polytopes P.      

The Reflexive Dimension of a Lattice Polytope

The reflexive dimension refldim(P) of a lattice polytope P is the minimal integer d so that P is the face of some d-dimensional reflexive polytope. We show that refldim(P) is finite for every P, and give bounds for refldim(kP) in terms of refldim(P) and k. Received July 2, 2004     

Path factors of bipartite graphs

A path on n vertices is denoted by P_n. For any graph H, the number of isolated vertices of H is denoted by i(H). Let G be a graph. A spanning subgraph F of G is called a {P₃, P₄, P₅}-factor of G if every component of F is one of P₃, P₄, and P₅. In this paper, we prove that a bipartite graph G has a {P₃, P₄, P₅}-factor if and only if i(G ? S ? M) ≦ 2|S| + |M| for all S ? V(G) and independent M ? E(G).     

Zur S-Darstellbarkeit endlicher lokal-affiner Kreisräume

An incidence structure (P, N, I) consisting of a set P of points, a set N of circles and an incidence relation I is called a locally affine circular space R, if the following holds: For any point PP the points and the circles of the internal structure R _P =(P _P , N _P , I _P ) with P _P =P{P}, N _P ={kN|PIk} and I _p =I(P _P ×N _P ) are respectively the points and the lines of an affine space.The purpose of this paper is at first to find conditions for representing a finite locally affine circular space R as a substrcture of a finite projective space B. In our representation (called S-representation) the points of R correspond to the elements of a spread L in B and the circles to certain lines of B not contained in elements of L. It is then shown that a finite inversive plane M of order q admits an S-representation if and only if q is even. As consequences we get characterizations of miquelian inversive planes of even order.     

Sublattices of the Lattices of Strong P-Congruences on P-Inversive Semigroups

In this paper, we describe strong P-congruences and sublattice-structure of the strong P-congruence lattice C_P(S) of a P-inversive semigroup S(P). It is proved that the set of all strong P-congruences C_P(S) on S(P) is a complete lattice. A close link is discovered between the class of P-inversive semigroups and the well-known class of regular ⋆-semigroups. Further, we introduce concepts of strong normal partition/equivalence, C-trace/kernel and discuss some sublattices of C_P(S). It is proved that the set of strong P-congruences, which have C-traces (C-kernels) equal to a given strong normal equivalence of P (C-kernel), is a complete sublattice of C_P(S). It is also proved that the sublattices determined by C-trace-equaling relation θ and C-kernel-equaling relation κ, respectively, are complete sublattices of C_P(S) and the greatest elements of these sublattices are given.     

What is the furthest graph from a hereditary property?

For a graph property P, the edit distance of a graph G from P, denoted E_P(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G to turn it into a graph satisfying P. What is the furthest graph on n vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge‐modification problems, in which one wishes to find or approximate the value of E_P(G) given an input graph G. A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density that depends on P essentially achieves the maximal distance from P, that is: ed(n,P) = E_P(G(n,p(P))) + o(n²) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Polygon containment under translation

The polygon containment problem is the problem of deciding whether a polygon P can be translated to fit inside another polygon P'. We present algorithms for two cases of the polygon containment problem: when both P and P' are rectilinearly convex, and when P is convex and P' is arbitrary. In both cases the algorithms run in time O(n²logn), where n is the sum of the number of bounding edges of the two polygons. Applications to an inspection problem and a stock-cutting problem are discussed, as is the containment problem when both P and P' are nonconvex.     

Automorphisms and isotone self-maps of ordered sets with top and bottom

For an ordered setP letP ^P denote the set of all isotone self-maps on P, that is, all mapsf fromP toP such thatxy impliesf(x)f(y), and let Aut (P) the set of all automorphisms onP, that is, all bijective isotone self-maps inP ^P . We establish an inequality relating ¦P ^P ¦ and ¦Aut(P)¦ in terms of the irreducibles ofP. As a straightforward corollary, we show that Rival and Rutkowski's automorphism conjecture is true for lattices. It is also true for ordered sets with top and bottom whose covering graphs are planar.Supported in part by NSERC (Grant no. A2507).Supported under an NSERC International Research Fellowship.     

Maximum andk-th maximal spanning trees of a weighted graph

LetA be a maximum spanning tree andP be an arbitrary spanning tree of a connected weighted graphG. Then we prove that there exists a bijectionψ fromA/P intoP/A such that for any edgea∈A/P, (P/ψ(a)) ∪a is a spanning tree ofG whose weight is greater than or equal to that ofP. We apply this theorem to some problems concerning spanning trees of a weighted graph.