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.     

The lower bound of the number of non-overlapping triangles

András Bezdek proved that if a convexn-gon andn points are given, then the points and the sides of the polygon can be renumbered so that at least [n/3] triangles spanned by theith point and theith side (i=1,2,…n) are mutually non-overlapping. In this paper, we show that at least [n/2] mutually non-overlapping triangles can be constructed. This lower bound is best possible.     

The double centralizer theorem for division algebras

AssumeV is a finite-dimensional vector space over a division ringD having centerF. It is shown that ifT∈ End _D (V) is algebraic overF then the double centralizerC(C(T)) ofT is the setF[T] of all polynomials inT with coefficients fromF. Consequently, eachn×n matrix ring overD is an algebraicF-algebra if and only ifC(C(T))=F[T] for allT and all finite-dimensionalV.     

Modification of a Finsler space by a normalized semi-parallel vector field

LetF _n be a Finsler space with metric functionF(x, y). M. Matsumoto [6] has defined a modified Finsler spaceF _n ^* whose metric functionF ^*(x, y) is given byF ^*2 = = F² + (X_i(x)yⁱ)², whereX _i are the components of a covariant vector which is a function of coordintae only. Since a concurrent vector is a function of coordinate only, Matsumoto and Eguchi [9] have studied various properties of the modified Finsler spaceF _n ^* under the assumption thatX _i are the components of a concurrent vector field inF _n. In this paper we shall introduce the concept of semi-parallel vector field inF _n and study the properties of modified Finsler spaceF _n ^* .     

On the respective terms of the derived and the polycentral series of a free lie algabra and an ideal

Let F be a free Lie algebra of rank> 1 and S be an ideal of F. Denote by F_m and F_{n l},…,n_k the terms of the lower central and the polycentral series of F. The aim of this paper is to provide a sufficient condition for the quotient algebra F_{n l},…,n_k/S_{n l},…,n_k to be infinitely generated. The case F_m/S_m was studied in [6] for free groups and in [ 2 ] for free Lie algebras. In this paper the following main theorem is proved : If F = F2 = S, k > 1 and n_i > 1 for i=l,…, k, then F_{n l}…,n_k/S_{n l} is infinitely generated.     

A RECOGNITION PROBLEM IN CONVERTING LINEAR PROGRAMMING TO NETWORK FLOW MODELS

The main goal of this paper is to study the following combinatorial problem.given a finite set E={e1,e2,…em} and a subset familly σ={S1,S2,…,Sn}of E,does there exist a tree T with the edge set E such that each induced subgraph T[Si] of Si is precisely a path (1≤i≤k)?     

A set intersection theorem and applications

Using Scarf's algorithm for “computing” a fixed point of a continuous mapping, the following is proved: LetM ₁ ? M _n be closed sets inR ⁿ which cover the standard simplexS, so thatM _i coversS _i , the face ofS opposite vertexi. We say a point inS iscompletely labeled if it belongs to everyM _i andk-almost-completely labeled if it belongs to all butM _k . Then there exists a closed setT ofk-almost-completely labeled points which connects vertexk with some completely labeled point. This result is used to prove Browder's theorem (a parametric fixed-point theorem) inR ⁿ . It is also used to generate “algorithms” for the nonlinear complementarity problem which are analogous to the Lemke—Howson algorithm and the Cottle—Dantzig algorithm, respectively, for the linear complementarity problem.     

Separating convex sets in the plane

Given a setA inR ² and a collectionS of plane sets, we say that a lineL separatesA fromS ifA is contained in one of the closed half-planes defined byL, while every set inS is contained in the complementary closed half-plane.We prove that, for any collectionF ofn disjoint disks inR ², there is a lineL that separates a disk inF from a subcollection ofF with at least (n–7)/4 disks. We produce configurationsH _n andG _n , withn and 2n disks, respectively, such that no pair of disks inH _n can be simultaneously separated from any set with more than one disk ofH _n , and no disk inG _n can be separated from any subset ofG _n with more thann disks.We also present a setJ _m with 3m line segments inR ², such that no segment inJ _m can be separated from a subset ofJ _m with more thanm+1 elements. This disproves a conjecture by N. Alonet al. Finally we show that ifF is a set ofn disjoint line segments in the plane such that they can be extended to be disjoint semilines, then there is a lineL that separates one of the segments from at least n/3+1 elements ofF.     

Sequentially equidistant points in metric spaces

A sequence (z ₀,z ₁,z ₂,, ...,z _n, z _n+1) of points fromp=z ₀ toq=z _n+1 in a metric spaceX is said to besequentially equidistant ifd(z _i−1,z _i)=d(z _i,z _i+1) for 1≦i≦n. If there is path inX fromp toq (or if a certain weaker condition holds), then such a sequence exists, with all points distinct, for every choice ofn, while ifX is compact and connected, then such a sequence exists at least forn=2. An example is given of a dense connected subspaceS ofR ^m ,m≧2, and an uncountable dense subsetE disjoint fromS for which there is no sequentially equidistant sequence of distinct points (n ≧ 2) inS ∪E between any two points ofE. Techniques of dimension theory are utilized in the construction of these examples, as well as in the proofs of some of the positive results. Supported in part by NSF Grant DMS-8701666.     

Eppstein's bound on intersecting triangles revisited

Let S be a set of n points in the plane, and let T be a set of m triangles with vertices in S. Then there exists a point in the plane contained in Ω(m³/(n⁶log²n)) triangles of T. Eppstein [D. Eppstein, Improved bounds for intersecting triangles and halving planes, J. Combin. Theory Ser. A 62 (1993) 176-182] gave a proof of this claim, but there is a problem with his proof. Here we provide a correct proof by slightly modifying Eppstein's argument.     

Some mutually disjoint steiner systems

A t-design λ; t-d-n is a system of subsets of size d (called blocks) from an n-set S, such that each t-subset from S is contained in precisely λ blocks. A Steiner system S(l, m, n) is a t-design with parameters 1; l-m-n. Two Steiner systems (or t-designs) are disjoint if they share no blocks. A search has been conducted which resulted in discovering 9 mutually disjoint S(5, 8, 24)'s, 24 mutually disjoint S(4, 7, 23)'s, 60 mutually disjoint S(3, 6, 22)'s, and 197 mutually disjoint S(2, 5, 21)'s. Taking unions of several mutually disjoint Steiner systems will then produce t-designs (with varying λ's) on 21, 22, 23, and 24 points.     

Constrained best approximation in Hilbert space III. Applications ton-convex functions

This paper continues the study of best approximation in a Hilbert spaceX from a subsetK which is the intersection of a closed convex coneC and a closed linear variety, with special emphasis on application to then-convex functions. A subtle separation theorem is utilized to significantly extend the results in [4] and to obtain new results even for the “classical” cone of nonnegative functions. It was shown in [4] that finding best approximations inK to anyf inX can be reduced to the (generally much simpler) problem of finding best approximations to a certain perturbation off from either the coneC or a certain subconeC _F. We will show how to determine this subconeC _F, give the precise condition characterizing whenC _F=C, and apply and strengthen these general results in the practically important case whenC is the cone ofn-convex functions inL ₂ (a,b),     

Intersecting sperner families and their convex hulls

Let ℱ be a family of subsets of a finite set ofn elements. The vector (f ₀, ...,f _n ) is called the profile of ℱ wheref _i denotes the number ofi-element subsets in ℱ. Take the set of profiles of all families ℱ satisfyingF ₁⊄F ₂ andF ₁∩F ₂≠0 for allF ₁,F ₂teℱ. It is proved that the extreme points of this set inR ⁿ⁺¹ have at most two non-zero components. Dedicated to Paul Erdős on his seventieth birthday     

Classification of some metric automorphisms defined by Standish

Let F be a finite set with a probability distribution {P_i: i?F} and (Ω $\text{F}$, P) denote the product space of countably many copies of (F, P). A permutation (bijection) φ of the integers induces an invertible measure preserving transformation T_φ on (Ω $\text{F}$, P) given by the equation (T_φw)_i = w_φ(j). Such metric automorphisms we call S-automorphisms.We show in this paper that S-automorphisms are ergodic if and only they are Bernoulli shifts and two ergodic S-automorphisms are isomorphic if and only if their associated permutations are conjugate.We also show that S-automorphisms have discrete spectrum if and only if they have zero entropy and every S-automorphism is either a Bernoulli shift, has discrete spectrum, or is a product of a Bernoulli shift and an automorphism with discrete spectrum.S-automorphism with discrete spectrum are those whose associated permutations contain only cycles of finite length. These automorphisms are studied according to the number of such finite cycles. Those whose permutations have infinitely many finite cycles with unbounded lengths are shown to be antiperiodic and those whose permutations have infinitely many finite cycles of bounded length are periodic with almost no fixed points. An example is given of two automorphisms of this latter type which are isomorphic but whose permutations are not conjugate.A complete isomorphism invariant is given for S-automorphisms whose associated permutations consist of finitely many finite cycles. Using this invariant we show that if φ is either a product of k disjoint cycles of prime power p^α, or a single cycle of length pq where p and q are primes, or a product of k disjoint cycles of prime lengths p₁ < p₂ < ··· < p_kand if ψ is a permutation such that T_ψand T_φ are isomorphic then ψ is conjugate to φ.     

Idempotence preserving maps on spaces of triangular matrices

SupposeF is an arbitrary field. Let |F| be the number of the elements ofF. LetT _n (F) be the space of allnxn upper-triangular matrices overF. A map Ψ: T _N (F) → T _N (F) is said to preserve idempotence ifA - λ B is idempotent if and only if Ψ(A) - λΨ(B) is idempotent for anyA, B ∈ T _n (F) and λ ∈ F. It is shown that: when the characteristic ofF is not 2, |F|>3 and n ≥ 3, Ψ:T _n (F) → T _n (F) is a map preserving idempotence if and only if there exists an invertible matrixP τ T _n (F) such that either ?(A) = PAP ^?1 for everyA ∈ T _n (F) or Ψ(A) = PJA ^t JP ^?1 for everyA ∈ T _n (F), whereJ = ∑ _n=1 ⁿ E _i,n+1?i and E_ij is the matrix with 1 in the (i,j)th entry and 0 elsewhere.     

Imbedded operators with finite Blaschke product symbol

LetF=(f _ij )be ann×n matrix ofH ^∞entries, and define $$S_F = (T_{2 \otimes ln}^* \oplus T_{2 \otimes ln}^* )\left| {_{Graph T_F^* } } \right..$$ This type of operator plays an important role in Cowen-Douglas theory. We call it the imbedded operator with symbolF. In the paper [L], we have already shown thatS _F is a compact pertubation ofT _z? ^* I _n by BDF Theorem. In this paper, we begin to investigate the compact part ofS _F . We give a practical method to calculate this compact part whenn=1 andF is any finite Blaschke product.     

Transitive points via Furstenberg family

Let (X,T) be a topological dynamical system and F be a Furstenberg family (a collection of subsets of Z₊ with hereditary upward property). A point x∈X is called an F-transitive one if {n∈Z₊:Tnx∈U}∈F for every non-empty open subset U of X; the system (X,T) is called F-point transitive if there exists some F-transitive point. In this paper, we aim to classify transitive systems by F-point transitivity. Among other things, it is shown that (X,T) is a weakly mixing E-system (resp. weakly mixing M-system, HY-system) if and only if it is {D-sets}-point transitive (resp. {central sets}-point transitive, {weakly thick sets}-point transitive).It is shown that every weakly mixing system is Fip-point transitive, while we construct an Fip-point transitive system which is not weakly mixing. As applications, we show that every transitive system with dense small periodic sets is disjoint from every totally minimal system and a system is Δ^?(Fwt)-transitive if and only if it is weakly disjoint from every P-system.     

Farthest points in weakly compact sets

LetS be a weakly compact subset of a Banach spaceB. We show that of all points inB which have farthest points inS contains a denseG ₅ ofB. Also, we give a necessary and sufficient condition for bounded closed convex sets to be the closed convex hull of their farthest points in reflexive Banach spaces.     

Unions of orthogonally convex or orthogonally starshaped polygons

LetT be a simply connected orthogonal polygon having the property that for every three points ofT, at least two of these points see each other via staircases inT. ThenT is a union of three orthogonally convex polygons. The number three is best possible.ForT a simply connected orthogonal polygon,T is a union of two orthogonally convex polygons if and only if for every sequencev ₁,...,v _n,v _n+1 =v ₁ inT, n odd, at least one consecutive pairv _i ,v _i+1 sees each other via staircase paths inT, 1 i n. An analogous result says thatT is a union of two orthogonal polygons which are starshaped via staircase paths if and only if for every odd sequence inT, at least one consecutive pair sees a common point via staircases inT.Supported in part by NSF grants DMS-8908717 and DMS-9207019.     

A multipoint method of third order

LetF be a mapping of the Banach spaceX into itself. A convergence theorem for the iterative solution ofF(x)=0 is proved for the multipoint algorithmx _n+1=x _n ?ø(x _n ), where $$\phi (x) = F\prime_x^{ - 1} \left[ {F(x) + F\lgroup {x - F\prime_x^{ - 1} F(x)} \rgroup} \right]$$ andF′x is the Frechet derivative ofF. The theorem guarantees that, under appropriate conditions onF, the multipoint sequence {x _n } generated by ø converges cubically to a zero ofF. The algorithm is applied to the nonlinear Chandrasekhar integral equation $$\frac{1}{2}\omega _0 x(t)\int_0^1 {\frac{{tx(s)}}{{s + t}}ds - x(t) + 1 = 0}$$ where ω₀>0. A discretization of the equations of iteration is discussed, and some numerical results are given.