The spectrum of partitions of a Boolean algebra

The main notion dealt with in this article is

Two theorems on finite unions of regressive immune sets

It is proved that the set of all natural numbers cannot be represented as the union of a finite number of regressive immune sets. This answers a question of Appel and McLaughlin. Incidentally, we obtain the following two results: 1. If A₁, ..., A_n are regressive immune sets, then there exists a general recursive function f such that D_f(0), ..., D_f(n), ... is a sequence of pairwise disjoint sets and $$\forall ^x (|D_{f(x)} |) \leqslant n + 1\& D_{f(x)} \cap \overline {A_1 \cup ... \cup A_n } \ne \emptyset )$$ .2. If A₁, ..., A_n are regressive and B is an infinite subset of \(\bigcup\limits_{t = 1}^n {A_1 } \) , then there exists an i that A_i?_eB.     

Atomlessr-maximal sets

We focus on % MathType!End!2!1!(A), the filter of supersets ofA in the structure of the computably enumerable sets under the inclusion relation, whereA is an atomlessr-maximal set. We answer a long-standing question by showing that there are infinitely many pairwise non-isomorphic filters of this type. Research partially supported NSF Grants DMS-96-3465 (Cholak) and DMS-95-00983 (Nies). The authors would like to thank Mike Stob for his help and interest.     

Baer subgeometry partitions

For any odd integern 3 and prime powerq, it is known thatPG(n–1, q²) can be partitioned into pairwise disjoint subgeometries isomorphic toPG(n–1, q) by taking point orbits under an appropriate subgroup of a Singer cycle ofPG(n–1, q²). In this paper, we construct Baer subgeometry partitions of these spaces which do not arise in the classical manner. We further illustrate some of the connections between Baer subgeometry partitions and several other areas of combinatorial interest, most notably projective sets and flagtransitive translation planes.     

Bounds for arrays of dots with distinct slopes or lengths

Ann×m sonar sequence is a subset of then×m grid with exactly one point in each column, such that the vectors determined by them are all distinct. We show that for fixedn the maximalm for which a sonar sequence exists satisfiesn–Cn ^11/20<m<n+4n ^2/3 for alln andm>n+c logn log logn for infinitely manyn.Another problem concerns the maximal numberD of points that can be selected from then×m grid so that all the vectors have slopes. We proven ^1/2Dn ^4/5 Supported by Hungarian National Foundation for Scientific Research, Grant No. 1901Research conducted by Herbert Taylor was sponsored in part by the Office of Naval Research under ONR Contract No. N00014-90-J-1341.     

On the connected components of the space of line transversals to a family of convex sets

Let ℒ be the space of line transversals to a finite family of pairwise disjoint compact convex sets in ℝ³. We prove that each connected component of ℒ can itself be represented as the space of transversals to some finite family of pairwise disjoint compact convex sets. The research of J. E. Goodman was supported in part by NSF Grant DMS91-22065 and by NSA Grant MDA904-92-H-3069. R. Pollack's research was supported in part by NSF Grant CCR91-22103 and by NSA Grant MDA904-92-H-3075. The research of R. Wenger was supported in part by NSA Grant MDA904-93-H-3026 and by the NSF Regional Geometry Institute (Smith College, July 1993) Grant DMS90-13220.     

Unbounded Lebesgue constants on compact groups

LetG be a compact group with dual object . A decomposition of into pairwise disjoint finite sets provides a way of defining partial sums of Fourier series onG. We employ a theorem of Olevskii to present a condition on such a decomposition which, if satisfied, guarantees that the corresponding Lebesgue constants are unbounded. We apply this to certain summation methods on tori and compact connected semisimple Lie groups.     

The Surgical Separation of Sets

Given a pair of finite disjoint setsA andB inR ⁿ, a fundamental problem with many important applications isto efficiently determine a hyperplaneH(w,) which separates these sets when they are separable, or nearly separates themwhen they are not. We seek a hyperplane which minimizes a natural errormeasure in the latter case, and so will surgically separate the sets. Whenthe sets are separable in a strong sense, we show that the problem is aconvex program with a unique solution, which has been investigated byothers. Using the KKT conditions, we improve on an existing algorithm. Whenthe sets are not separable, the problem is nonconvex, generally with properlocal solutions, and we solve an equivalent problem by Branch and Bound.Numerical results are presented.     

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.     

Finitely generated pseudosimple algebras

We prove that there exist finitely generated algebras, which are pseudosimple but not simple. This problem goes back to Henkin, Monk, Tarski [71]. In fact, for any limit ordinal i, there exists a pseudosimple algebra, which has no proper subalgebra and whose congruence lattice is ⁱ+1. (Here ⁱ denotes ordinal power).Presented by George Grätzer.Research supported by Hungarian National Foundation for Scientific Research grant No. 1810.     

When Is a Sum of Partial Reflections Equal to a Scalar Operator?

We describe the set of values of the parameter for which there exists a Hilbert space H and n partial reflections A ₁,...,A _n (self-adjoint operators such that A _k ³ =A_k or, which is the same, self-adjoint operators whose spectra belong to the set {-1,0,1}) whose sum is equal to the scalar operator I _H .     

Query complexity,or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?

By thequery-time complexity of a relativized algorithm we mean the total length of oracle queries made; thequery-space complexity is the maximum length of the queries made. With respect to these cost measures one can define polynomially time- or space-bounded deterministic, nondeterministic, alternating, etc. Turing machines and the corresponding complexity classes. It turns out that all known relativized separation results operate essentially with this cost measure. Therefore, if certain classes do not separate in the query complexity model, this can be taken as an indication that their relativized separation in the classical cost model will require entirely new principles.A notable unresolved question in relativized complexity theory is the separation of NP^A co NP^A fromP ^A under random oraclesA. We conjecture that the analogues of these classes actually coincide in the query complexity model, thus indicating an answer to the question in the title. As a first step in the direction of establishing the conjecture, we prove the following result, where polynomial bounds refer to query complexity.If two polynomially query-time-bounded nondeterministic oracle Turing machines accept precisely complementary (oracle dependent) languages L^A and {0, 1}^*L^A under every oracle A then there exists a deterministic polynomially query-time-bounded oracle Turing machine that accept L^A. The proof involves a sort of greedy strategy to selecting deterministically, from the large set of prospective queries of the two nondeterministic machines, a small subset that suffices to perform an accepting computation in one of the nondeterministic machines. We describe additional algorithmic strategies that may resolve the same problem when the condition holds for a (1–) fraction of the oracles A, a step that would bring us to a non-uniform version of the conjecture. Thereby we reduce the question to a combinatorial problem on certain pairs of sets of partial functions on finite sets.     

Homomorphism-Homogeneous Partially Ordered Sets

A structure is called homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this paper we characterize homomorphism-homogeneous partially ordered sets (where a homomorphism between partially ordered sets A and B is a mapping f : A →B satisfying ). We show that there are five types of homomorphism-homogeneous partially ordered sets: partially ordered sets whose connected components are chains; trees; dual trees; partially ordered sets which split into a tree and a dual tree; and X ₅-dense locally bounded partially ordered sets. Supported by the Ministry od Science and Environmental Protection of the Republic of Serbia, Grant No. 144017.     

Upper bounds on geometric permutations for convex sets

LetA be a family ofn pairwise disjoint compact convex sets inR ^d. Let . We show that the directed lines inR ^d, d 3, can be partitioned into sets such that any two directed lines in the same set which intersect anyAA generate the same ordering onA. The directed lines inR ² can be partitioned into 12n such sets. This bounds the number of geometric permutations onA by 1/2 _d ford3 and by 6n ford=2.     

Optimally scaled matrices,necessary and sufficient conditions

Summary We shall in this paper consider the problem of determination a row or column scaling of a matrixA, which minimizes the condition number ofA. This problem was studied by several authors. For the cases of the maximum norm and of the sum norm the scale problem was completely solved by Bauer [1] and Sluis [5]. The condition ofA subordinate to the pair of euclidean norms is the ratio /, where and are the maximal and minimal eigenvalue of (A ^H A)^1/2 respectively. The euclidean case was considered by Forsythe and Strauss [3]. Shapiro [6] proposed some approaches to a numerical solution in this case. The main result of this paper is the presentation of necessary and sufficient conditions for optimal scaling in terms of maximizing and minimizing vectors. A uniqueness proof for the solution is offered provided some normality assumption is satisfied.     

Extendability of Classes of Maps and New Properties of Upper Sets

We continue to study upper sets ${\widetilde{A}=\{(x,r)\in A\times R_+ :\exists y\in A\setminus\{x\}, r=|x-y|\}}We continue to study upper sets [(A)\tilde]={(x,r) ? A×R₊ :$y ? A\{x}, r=|x-y|}{\widetilde{A}=\{(x,r)\in A\times R_+ :\exists y\in A\setminus\{x\}, r=|x-y|\}} equipped by hyperbolic metric. We define analogous of quasiconvexity, simply connectedness and nearlipschitz functions. We give a new definition of quasisymmetry as nearlipschitz characteristic on [(A)\tilde]{\widetilde{A}}. In the final part in terms of upper sets we give the following extension property of A ì R²{A\subset R^2}. For 0 ￡ e ￡ d{0\le\varepsilon\le \delta}, each (1+e){(1+\varepsilon)}-bilipschitz map f : A → R ² has an extension to a (1+Ce){(1+C\varepsilon)}-bilipschitz map F : R ² → R ².     

On lightly and countably compact spaces in ZF

Abstract

Given a topological space X = (X, T ), we show in the Zermelo-Fraenkel set theory ZF that:

1. Every locally finite family of open sets of X is finite iff every pairwise disjoint, locally finite family of open sets is finite.

2. Every locally finite family of subsets of X is finite iff every pairwise disjoint, locally finite family of subsets of X is finite iff every locally finite family of closed subsets of X is finite.

3. The statement “every locally finite family of closed sets of X is finite” implies the proposition “every locally finite family of open sets of X is finite”. The converse holds true in case X is T₄ and the countable axiom of choice holds true.

   We also show:

4. It is relatively consistent with ZF the existence of a non countably compact T₁ space such that every pairwise disjoint locally finite family of closed subsets is finite but some locally finite family of subsets is infinite.

5. It is relatively consistent with ZF the existence of a countably compact T₄ space including an infinite pairwise disjoint locally finite family of open (resp. closed) sets.

     

On the exact rate of convergence of frequencies of digits in self-similar sets

We study the exact rate of convergence of frequencies of digits of “normal” points of a self-similar set. Our results have applications to metric number theory. One particular application gives the following surprising result: there is an uncountable family of pairwise disjoint and exceptionally big subsets of ?^d that do not obey the law of the iterated logarithm. More precisely, we prove that there is an uncountable family of pairwise disjoint and exceptionally big sets of points x in ?^d—namely, sets with full Hausdorff dimension—for which the rate of convergence of frequencies of digits in the N-adic expansion of x is either significantly faster or significantly slower than the typical rate of convergence predicted by the law of the iterated logarithm.     

Some geometric applications of Dilworth’s theorem

A geometric graph is a graph drawn in the plane such that its edges are closed line segments and no three vertices are collinear. We settle an old question of Avital, Hanani, Erdős, Kupitz, and Perles by showing that every geometric graph withn vertices andm>k ⁴ n edges containsk+1 pairwise disjoint edges. We also prove that, given a set of pointsV and a set of axis-parallel rectangles in the plane, then either there arek+1 rectangles such that no point ofV belongs to more than one of them, or we can find an at most 2·10⁵ k ⁸ element subset ofV meeting all rectangles. This improves a result of Ding, Seymour, and Winkler. Both proofs are based on Dilworth’s theorem on partially ordered sets. The research by János Pach was supported by Hungarian National Foundation for Scientific Research Grant OTKA-4269 and NSF Grant CCR-91-22103.     

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.