A ramsey theorem for trees,with an application to Banach spaces

LetS be the binary tree of all sequences of 0’s and 1’s. A chain ofS is any infinite linearly ordered subset. Letℋ be an analytic set of chains, we show that there exists a binary subtreeS’ ofS such that either all chains ofS’ lie inℋ or no chain ofS’ lies inℋ. As an application, we prove the following result on Banach spaces: If (x _s) _sɛs is a bounded sequence of elements in a Banach spaceE, there exists a subtreeS’ ofS such that for any chainβ ofS’ the sequence (x _s ) _{s ∈β} is either a weak Cauchy sequence or equivalent to the usuall ¹ basis.     

Bin packing can be solved within 1 + ε in linear time

For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large. The work of this author was supported by NSF Grant MCS 70-04997.     

On the commutant of certain multiplication operators on spaces of analytic functions

Let ℬ be a Banach space of analytic functions defined on the open unit disk. We characterize the commutant ofM _Z ² (the operator of multiplication by the square of independent variable defined on ℬ) and show that for an operatorS in the commutantM _Z ² ifSM _Z ^2k+1−M _Z ^2k+1 S is compact for some nonnegative integerk, thenS=M _ϕ whereϕ is a multiplier of ℬ. Letn be a positive integer andS be an operator in the commutant ofM _Z ⁿ defined on a functional Hilbert spaces of analytic functions. We show that under certain conditionsS has the formM _ϕ. Research supported by the Shiraz University Grant 78-SC-1188-657.     

On a problem of Erdős concerning property B

A family ℱ of sets has propertyB if there exists a setS such thatS∩F≠0 andS⊄F for everyF∈ℱ. ℱ has propertyB(s) if there exists a setS such that 0<|F∩S|<s for everyF∈ℱ. Denote bym(n) (respectivelym(n, s)) the size of a smallest family ofn-element sets not having propertyB (respectivelyB(s)). P. Erdős has asked whetherm(n, s)≧m (s) for alln≧s. We show that, in general, this inequality does not hold.     

On the peripheral spectrum of positive operators

We prove that ifE is a Banach lattice andS, T ∈ ℒ (E) are such that 0≦s≦T,r(s)=r(T) andr(T) is a Riesz point ofσ(T) thenr(S) is a Riesz point ofσ(S). We prove also some results on compact positive perturbations of positive irreducible operators and lattice homomorphisms.     

An embedding theorem for finite planar spaces

LetS be a finite planar space such that any two distinct planes intersect in a line. We show thatk≤n ²+1 for anyk-cap ofS, wheren is the order ofS. Moreover, if a (n ²+1)-cap exists inS, a necessary and sufficient condition is provided forS to be embeddable in a 3-dimensional projective space. Work supported by the National Research Project “Strutture geometriche, Combinatoria e loro applicazioni” of the italian M.U.R.S.T.     

Conjecture of Li and Praeger concerning the isomorphisms of Cayley graphs of A5

LetG be a finite group, andS a subset ofG \ |1| withS =S ⁻¹. We useX = Cay(G,S) to denote the Cayley graph ofG with respect toS. We callS a Cl-subset ofG, if for any isomorphism Cay(G,S) ≈ Cay(G,T) there is an α∈ Aut(G) such thatS ^α =T. Assume that m is a positive integer.G is called anm-Cl-group if every subsetS ofG withS =S ⁻¹ and | S | ≤m is Cl. In this paper we prove that the alternating groupA ₅ is a 4-Cl-group, which was a conjecture posed by Li and Praeger.     

Projecting the one-dimensional Sierpinski gasket

LetS⊂ℝ² be the Cantor set consisting of points (x,y) which have an expansion in negative powers of 3 using digits {(0,0), (1,0), (0,1)}. We show that the projection ofS in any irrational direction has Lebesgue measure 0. The projection in a rational directionp/q has Hausdorff dimension less than 1 unlessp+q ≡ 0 mod 3, in which case the projection has nonempty interior and measure 1/q. We compute bounds on the dimension of the projection for certain sequences of rational directions, and exhibit a residual set of directions for which the projection has dimension 1. This work was partially completed while the author was at the Institut Fourier, Grenoble, France.     

Levels of quaternion algebras

The level of a ring R with 1 ≠ 0 is the smallest positive integer s such that −1 can be written as a sum of s squares in R, provided −1 is a sum of squares at all. D. W. Lewis showed that any value of type 2 ⁿ or 2 ⁿ + 1 can be realized as level of a quaternion algebra, and he asked whether there exist quaternion algebras whose levels are not of that form. Using function fields of quadratic forms, we construct such examples. Received: 23 March 2007, Revised: 30 October 2007     

ON STABLE LINE SEGMENTS IN ALL TRIANGULATIONS OF A PLANAR POINT SET

Abstract. Let S be a set of finite plauar points. A llne segment L(p, q) with p, q E Sis called a stable line segment of S, if there is no Line segment with two endpoints in S intersecting L(p, q). In this paper, some geometric properties of the set of all stable line segments     

Distance and fractional isomorphism in Steiner triple systems

In [8], Quattrochi and Rinaldi introduced the idea ofn ⁻¹-isomorphism between Steiner systems. In this paper we study this concept in the context of Steiner triple systems. The main result is that for any positive integerN, there existsv ₀(N) such that for all admissiblev≥v ₀(N) and for each STS(v) (sayS), there exists an STS(v) (sayS′) such that for somen>N, S is strictlyn ⁻¹-isomorphic toS′. We also prove that for all admissiblev≥13, there exist two STS(v)s which are strictly 2⁻¹-isomorphic. Define the distance between two Steiner triple systemsS andS′ of the same order to be the minimum volume of a tradeT which transformsS into a system isomorphic toS′. We determine the distance between any two Steiner triple systems of order 15 and, further, give a complete classification of strictly 2⁻¹-isomorphic and 3⁻¹-isomorphic pairs of STS(15)s.     

New examples of Lagrangian rigidity

Letn=4 or 8. We prove that any Lagrangian embedding ofS ^{n − 1} ×S ¹ into ℂ ⁿ has a trivial linking class. We deduce that every embedding ofS ³ ×S ⁴ into ℂ⁴ is isotopic to a Lagrangian embedding. This is false ifn = 8.     

The solution to a conjecture of Tits on the subgroup generated by the squares of the generators of an Artin group

Let A be an Artin group with standard generating set {σ _s :s∈S}. Tits conjectured that the only relations in A amongst the squares of the generators are consequences of the obvious ones, namely that σ _s ² and σ _t ² commute whenever σ _s and σ _t commute, for s,t∈S. In this paper we prove Tits’ conjecture for all Artin groups. In fact, given a number m _s ≥2 for each s∈S, we show that the elements {T _s =σ _s ^ms :s∈S} generate a subgroup that has a finite presentation in which the only defining relations are that T _s and T _t commute if σ _s and σ _t commute. Oblatum 21-III-2000 & 1-XII-2000?Published online: 5 March 2001     

A completion problem for finite affine planes

A partial affine plane (PAP) of ordern is ann ²-setS of points together with a collection ofn-subsets ofS called lines such that any two lines meet in at most one point. We obtain conditions under which a PAP with nearlyn ²+n lines can be completed to an affine plane by adding lines. In particular, we make use of Bruck’s completion condition for nets to show that certain PAP’s with at leastn ²+n−√n can be completed and that forn≠3 any PAP withn ²+n−2 lines can be completed.     

Point sets with uniformity properties and orthogonal hypercubes

The theory of (t, m, s)-nets is useful in the study of sets of points in the unit cube with small discrepancy. It is known that the existence of a (0, 2,s)-net in baseb is equivalent to the existence ofs–2 mutually orthogonal latin squares of orderb. In this paper we generalize this equivalence by showing that fort0 the existence of a (t, t+2,s)-net in baseb is equivalent to the existence ofs mutually orthogonal hypercubes of dimensiont+2 and orderb. Using the theory of hypercubes we obtain upper bounds ons for the existence of such nets. Forb a prime power these bounds are best possible. We also state several open problems.This author would like to thank the Mathematics Department of the University of Tasmania for its hospitality during his sabbatical when this paper was written. The same author would also like to thank the NSA for partial support under grant agreement # MDA904-87-H-2023.This author's research was supported by a grant from the Commonwealth of Australia through the Australian Research Council.     

On a stochastic game with one-chance recovery

Summary Bernoulli trials with success ratep are considered. Peter, who is a gambler of success ratep, gets 1 unit if the first trial results in success and loses the same unit otherwise. For thekth trial (k≧2), he gets or loses 1 according as success or failure unless his previous gainS _k−1 is negative. WhenS _k−1 is minus, Peter gets or loses −S _k−1 . Then Peter's gainS _n inn trials is the sum of “dependent” random variables. Therefore, Peter has always the chancep of recovering his minus gain instantaneously. The probability function ofS _n is given and the expected gain is compared with the ordinary (non-symmetric) random walk situation. It will be concluded that Peter should not play the game with one-chance recovery because whenp is less than 1/2, he must be afraid of suffering a bigger risk than the usual case. The Institute of Statistical Mathematics     

Convex decompositions in the plane and continuous pair colorings of the irrationals

We address the structure of nonconvex closed subsets of the Euclidean plane. A closed subsetS⊆ℝ² which is not presentable as a countable union of convex sets satisfies the following dichotomy:

p-Congruences onp-regular semigroups

A pair (S, P) of a regular semigroupsS and a subsetP ofE _s whereE _s is the set of all idempotent elements ofS is called aP-regular semigroupS(P) if it satisfies the following:

On Λ(p)-subsets of squares

This paper is a follow up of [B₁]. It is shown that the sequence of squares {n ²|n=1, 2, ...} contains Λ(p)-subsets of “maximal density”, for any givenp>4. The proof is based on the probabilistic method developed in [B₁] and a precise estimate of the Λ(p)-constant for the sequence of squares itself. Analogues of this phenomenon are obtained for other arithmetic sets, such as the sequence ofkth powers {n ^k |n=1, 2, ...} or the sequence of prime numbers. Sections 2 and 3 of the paper are of independent interest to orthogonal system theory.     

P.I.G-rings and the contractability of primes

LetR=F{x ₁, …, x_k} be a prime affine p.i. ring andS a multiplicative closed set in the center ofR, Z(R). The structure ofG-rings of the formR _s is completely determined. In particular it is proved thatZ(R _s)—the normalization ofZ(R _s) —is a prüfer ring, 1≦k.d(R _s)≦p.i.d(R _s) and the inequalities can be strict. We also obtain a related result concerning the contractability ofq, a prime ideal ofZ(R) fromR. More precisely, letQ be a prime ideal ofR maximal to satisfyQϒZ(R)=q. Then k.dZ(R)/q=k.dR/Q, h(q)=h(Q) andh(q)+k.dZ(R)/q=k.dz(R). The last condition is a necessary butnot sufficient condition for contractability ofq fromR.