Generalized bi-circular projections

Recall that a projection P on a complex Banach space X is a generalized bi-circular projection if P+λ(I−P) is a (surjective) isometry for some λ such that |λ|=1 and λ≠1. It is easy to see that every hermitian projection is generalized bi-circular. A generalized bi-circular projection is said to be nontrivial if it is not hermitian. Botelho and Jamison showed that a projection P on C([0,1]) is a nontrivial generalized bi-circular projection if and only if P−(I−P) is a surjective isometry. In this article, we prove that if P is a projection such that P+λ(I−P) is a (surjective) isometry for some λ, then either P is hermitian or λ is an nth unit root of unity. We also show that for any nth unit root λ of unity, there are a complex Banach space X and a nontrivial generalized bi-circular projection P on X such that P+λ(I−P) is an isometry.     

Cellularity in polyhedra

A compact subset X of a polyhedron P is cellular in P if there is a pseudoisotropy of P shrinking precisely X to a point. A proper surjection between polyhedra f:P→Q is cellular if each point inverse of f is cellular in P. It is shown that if f:P→Q is a cellular map and either P or Q is a generalized n-manifold, n≠4, then f is approximable by homeomorphisms. Also, if P or Q is an n-manifold with boundary, n≠4, 5, then a cellular map f:P→Q is approximable by homeomorphisms. A cellularity criterion for a special class of cell-like sets in polyhedra is established.     

Retractions onto series-parallel posets

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets P. We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P, we describe posets admitting a retraction onto P.     

On semigroups generated by differential operators on Lie groups

Let dR be the differential of a strongly continuous representation of a Lie group G on a Hilbert space H. Let P be the left-invariant second-order differential operator on G with positive semidefinite main part P₂ and with first-order part P₁. If Im(P₁) is in some sense subordinate to P₂ then dR(P) is a pregenerator of a strongly continuous semigroup of operators in H. If the whole P₁ is in some sense subordinate to P₂ then that semigroup is holomorphic or, even more, dR(P) is a pregenerator of a cosine operator function.     

The complex of non-crossing diagonals of a polygon

Given a convex n-gon P in R² with vertices in general position, it is well known that the simplicial complex θ(P) with vertex set given by diagonals in P and facets given by triangulations of P is the boundary complex of a polytope of dimension n−3. We prove that for any non-convex polygonal region P with n vertices and h+1 boundary components, θ(P) is a ball of dimension n+3h−4. We also provide a new proof that θ(P) is a sphere when P is convex with vertices in general position.     

H.O. Foulkes (1907–1977)

Two general kinds of subsets of a partially ordered set P are always retracts of P: (1) every maximal chain of P is a retract; (2) in P, every isometric, spanning subset of length one with no crowns is a retract. It follows that in a partially ordered set P with the fixed point property, every maximal chain of P is complete and every isometric, spanning fence of P is finite.     

Automorphisms of lexicographic products

The automorphism group Γ(P) of a partially ordered set P consists of all permutations on P that preserve order (and have order preserving inverses). In this paper we raise, and partially answer, the question: How is the automorphism group of the lexicographic product (P × Q) of two orders (P and Q) related to the automorphism groups of the factors, P and Q?We show that the wreath product Γ(Q) wr ΓP) is always contained in Γ(P × Q). We find necessary and sufficient conditions for Γ(P × Q) to equal Γ(Q) wr Γ(P), and when P and Q are finite, we find a complete characterization of Γ(P × Q) in terms of Γ(P), Γ(Q) and properties of P and Q.     

Quadrangulations on 3-Colored Point Sets with Steiner Points and Their Winding Numbers

Let P be a point set on the plane, and consider whether P is quadrangulatable, that is, whether there exists a 2-connected plane graph G with each edge a straight segment such that V(G) = P, that the outer cycle of G coincides with the convex hull Conv(P) of P, and that each finite face of G is quadrilateral. It is easy to see that it is possible if and only if an even number of points of P lie on Conv(P). Hence we give a k-coloring to P, and consider the same problem, avoiding edges joining two vertices of P with the same color. In this case, we always assume that the number of points of P lying on Conv(P) is even and that any two consecutive points on Conv(P) have distinct colors. However, for every k ≥ 2, there is a k-colored non-quadrangulatable point set P. So we introduce Steiner points, which can be put in any position of the interior of Conv(P) and each of which may be colored by any of the k colors. When k = 2, Alvarez et al. proved that if a point set P on the plane consists of \({\frac{n}{2}}\) red and \({\frac{n}{2}}\) blue points in general position, then adding Steiner points Q with \({|Q| \leq \lfloor \frac{n-2}{6} \rfloor + \lfloor \frac{n}{4} \rfloor +1}\) , P ∪ Q is quadrangulatable, but there exists a non-quadrangulatable 3-colored point set for which no matter how many Steiner points are added. In this paper, we define the winding number for a 3-colored point set P, and prove that a 3-colored point set P in general position with a finite set Q of Steiner points added is quadrangulatable if and only if the winding number of P is zero. When P ∪ Q is quadrangulatable, we prove \({|Q| \leq \frac{7n+34m-48}{18}}\) , where |P| = n and the number of points of P in Conv(P) is 2m.     

On the field of values of oblique projections

We highlight some properties of the field of values (or numerical range) W(P) of an oblique projector P on a Hilbert space, i.e., of an operator satisfying P²=P. If P is neither null nor the identity, we present a direct proof showing that W(P)=W(I-P), i.e., the field of values of an oblique projection coincides with that of its complementary projection. We also show that W(P) is an elliptical disk (i.e., the set of points circumscribed by an ellipse) with foci at 0 and 1 and eccentricity 1/‖P‖. These two results combined provide a new proof of the identity ‖P‖=‖I-P‖. We discuss the influence of the minimal canonical angle between the range and the null space of P, on the shape of W(P). In the finite dimensional case, we show a relation between the eigenvalues of matrices related to these complementary projections and present a second proof to the fact that W(P) is an elliptical disk.     

Hamiltonicity in (0–1)-polyhedra

The graph G(P) of a polyhedron P has a node corresponding to each vertex of P and two nodes are adjacent in G(P) if and only if the corresponding vertices of P are adjacent on P. We show that if P ? $\text{R}$ⁿ is a polyhedron, all of whose vertices have (0–1)-valued coordinates, then (i) if G(P) is bipartite, the G(P) is a hypercube; (ii) if G(P) is nonbipartite, then G(P) is hamilton connected. It is shown that if P ? $\text{R}$ⁿ has (0–1)-valued vertices and is of dimension d (≤n) then there exists a polyhedron P′ ? $\text{R}$^d having (0–1)-valued vertices such that $\text{G(P) ? G(P′)}$. Some combinatorial consequences of these results are also discussed.     

Strongly ergodic Markov chains and rates of convergence using spectral conditions

For finite Markov chains the eigenvalues of P can be used to characterize the chain and also determine the geometric rate at which Pⁿ converges to Q in case P is ergodic. For infinite Markov chains the spectrum of P plays the analogous role. It follows from Theorem 3.1 that 6Pⁿ?Q6?Cβⁿ if and only if P is strongly ergodic. The best possible rate for β is the spectral radius of P?Q which in this case is the same as sup{|λ|: λ ? σ (P), λ ≠;1}. The question of when this best rate equals δ(P) is considered for both discrete and continous time chains. Two characterizations of strong ergodicity are given using spectral properties of P? Q (Theorem 3.5) and spectral properties of a submatrix of P (Theorem 3.16).     

A class of extension properties that are not simply generated

Let $\text{P}$ be a closed-hereditary topological property preserved by products. Call a space $\text{P}$-regular if it is homeomorphic to a subspace of a product of spaces with $\text{P}$. Suppose that each $\text{P}$-regular space possesses a $\text{P}$-regular compactification. It is well-known that each $\text{P}$-regular space X is densely embedded in a unique space γ_scPX with $\text{P}$ such that if f: X → Y is continuous and Y has $\text{P}$, then f extends continuously to γ_scPX. Call $\text{P}$-pseudocompact if γ_scPX is compact.Associated with $\text{P}$ is another topological property $\text{P}$^#, possessing all the properties hypothesized for $\text{P}$ above, defined as follows: a $\text{P}$-regular space X has $\text{P}$^# if each $\text{P}$-pseudocompact closed subspace of X is compact. It is known that the $\text{P}$-pseudocompact spaces coincide with the $\text{P}$^#-pseudocompact spaces, and that $\text{P}$^# is the largest closed-hereditary, productive property for which this is the case. In this paper we prove that if $\text{P}$ is not the property of being compact and $\text{P}$-regular, then $\text{P}$^# is not simply generated; in other words, there does not exist a space E such that the spaces with $\text{P}$^# are precisely those spaces homeomorphic to closed subspaces of powers of E.     

Imprimitive distance-regular graphs and projective planes

We investigate a class of (imprimitive) covering graphs Γ of complete bipartite graphs K_k,k and show that they are in one-to-one correspondence with triples (P, l, P), where P is a projective plane of order k and (l, P) is a distinguished flag of P. If Γ is distance-transitive, then P ? l is a self-dual rank three translation plane and may be coordinatised by a semifield.     

Projections of polytopes and the generalized baues conjecture

Associated with every projection π:P→π(P) of a polytopeP is a partially ordered set of all “locally coherent strings”: the families of proper faces ofP that project to valid subdivisions of π(P), partially ordered by the natural inclusion relation. The “Generalized Baues Conjecture” posed by Billeraet al. [4] asked whether this partially ordered set always has the homotopy type of a sphere of dimension dim(P—dim(π(P))?1. We show that this is true in the cases when dim(π(P))=1 (see[4]) and when dim(P)—dim(π(P))≤2, but fails in general. For an explicit counterexample we produce a nondegenerate projection of a five-dimensional, simplicial, 2-neighborly polytopeP with 10 vertices and 42 facets to a hexagon π(P)??². The construction of the counterexample is motivated by a geometric analysis of the relation between the fibers in an arbitrary projection of polytopes.     

On the family of linear extensions of a partial order

Given a partial order P defined on a finite set X, a binary relation ?_P may be defined on X by setting x ?_Py for elements x and y in X just when more linear extensions L of P on X have xLy than yLx. A linear extension L of P on X is a linear order on X with P ? L. There exist partial orders P such that ?_P includes cycles. Thus, in a voting situation in which voters are unanimous in their preferences on the pairs in P and express all possible linearly ordered preferences on X which are consistent with P, with no two voters having the same preference order, strict simple majorities as given by ?_P can cycle.     

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.     

A note on 2-nilpotence of finite groups

Ballester-Bolinches and Guo showed that a finite group G is 2-nilpotent if G satisfies: (1) a Sylow 2-subgroup P of G is quaternion-free and (2) Ω₁(P ∩  G′)?≤?Z(P) and N _G (P) is 2-nilpotent. In this paper, it is obtained that G is a non-2-nilpotent group of order 16q for an odd prime q satisfying (1) a Sylow 2-subgroup P of G is not quaternion-free and (2) Ω₁(P?∩?G′)?≤?Z(P) and N _G (P) is 2-nilpotent if and only if q?=?3 and G???GL ₂(3).     

Minkowski Length of 3D Lattice Polytopes

We study the Minkowski length L(P) of a lattice polytope P, which is defined to be the largest number of non-trivial primitive segments whose Minkowski sum lies in P. The Minkowski length represents the largest possible number of factors in a factorization of polynomials with exponent vectors in P, and shows up in lower bounds for the minimum distance of toric codes. In this paper we give a polytime algorithm for computing L(P) where P is a 3D lattice polytope. We next study 3D lattice polytopes of Minkowski length 1. In particular, we show that if Q, a subpolytope of P, is the Minkowski sum of L=L(P) lattice polytopes Q _i , each of Minkowski length 1, then the total number of interior lattice points of the polytopes Q ₁,??,Q _L is at most 4. Both results extend previously known results for lattice polygons. Our methods differ substantially from those used in the two-dimensional case.     

A linear algorithm for a core of a tree

A core of a graph G is a path P in G that is central with respect to the property of minimizing d(P) = Σ_υ?V(G)d(υ, P), where d(υ, P) is the distance from vertex υ to path P. We present a linear algorithm for finding a core of a tree. Since the core of a graph is not necessarily unique, we also output a list of all the vertices which are in some core.