A Note on Varying Cardinality in the Average Case Setting

We study how much information with varying cardinality can be better than information with fixed cardinality for approximating linear operators in the average case setting with Gaussian measure. It has been known that adaptive choice of functionals forming information is not better than nonadaptive, and that the only gain may be obtained by using varying cardinality. We prove that the lower bounds from Traub (J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, "Information-Based Complexity," Academic Press, San Diego, 1988) et al. on the efficiency of varying cardinality are sharp. In particular, we show that information whose cardinality assumes at most two different values can significantly help in approximating any linear operator with infinite dimensional domain space.     

Small Transitive Families of Subspaces

A family of subspaces of a complex separable Hilbert space is transitive if every bounded operator which leaves each of its members invariant is scalar. This article surveys some results concerning transitive families of small cardinality, and adds some new ones. The minimum cardinality of a transitive family in finite dimensions (greater than 2) is 4. In infinite dimensions a transitive pair of linear manifolds exists but the minimum cardinality of a transitive family of dense operator ranges or norm-closed subspaces is not known. However, a transitive family of dense operator ranges with 5 elements can be found, and so can a transitive family of norm-closed subspaces with 4 elements. In finite dimensions (> 1) three nest algebras (corresponding to maximal nests) can intersect in the scalar operators, but two cannot. It is not known if this is the case in infinite dimensions for maximal nests of type ω + 1. Four such nest algebras can intersect in the scalar operators. Received June 15, 2002, Accepted November 27, 2002     

Finiteness Theorems for Graphs and Posets Obtained by Compositions

We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that allows us to characterize such antichains by means of the set of elements below it.In particular we show that the following classes have infinite antichains with respect to the induced subgraph/poset relation: interval graphs and orders, N-free orders, orders with bounded decomposition width. On the other hand for orders with bounded decomposition diameter finiteness of all antichains is shown. As a consequence those classes with infinite antichains have undecidable hereditary properties whereas those with finite antichains have fast algorithms for all such properties.     

Infinitary S5-Epistemic Logic

It is known that a theory in S5-epistemic logic with several agents may have numerous models. This is because each such model specifies also what an agent knows about infinite intersections of events, while the expressive power of the logic is limited to finite conjunctions of formulas. We show that this asymmetry between syntax and semantics persists also when infinite conjunctions (up to some given cardinality) are permitted in the language. We develop a strengthened S5-axiomatic system for such infinitary logics, and prove a strong completeness theorem for them. Then we show that in every such logic there is always a theory with more than one model.     

Toeplitz minimal flows which are not uniquely ergodic

Summary We study minimal symbolic dynamical systems which are orbit closures of Toeplitz sequences. We construct 0–1 subshifts of this type for which the set of ergodic invariant measures has any given finite cardinality, is countably infinite or has cardinality of the continuum.     

Reconstruction of infinite locally finite connected graphs

Let G be an infinite locally finite connected graph. We study the reconstructibility of G in relation to the structure of its end set . We prove that an infinite locally finite connected graph G is reconstructible if there exists a finite family (Ω_i)_0i (n2) of pairwise finitely separable subsets of such that, for all x,y,x′,y′V(G) and every isomorphism f of G−{x,y} onto G−{x′,y′} there is a permutation π of {0,…,n−1} such that for 0i<n. From this theorem we deduce, as particular consequences, that G is reconstructible if it satisfies one of the following properties: (i) G contains no end-respecting subdivision of the dyadic tree and has at least two ends of maximal order; (ii) the set of thick ends or the one of thin ends of G is finite and of cardinality greater than one. We also prove that if almost all vertices of G are cutvertices, then G is reconstructible if it contains a free end or if it has at least a vertex which is not a cutvertex.     

Isols and maximal intersecting classes

In transfinite arithmetic 2ⁿ is defined as the cardinality of the family of all subsets of some set v with cardinality n. However, in the arithmetic of recursive equivalence types (RETs) 2^N is defined as the RET of the family of all finite subsets of some set v of nonnegative integers with RET N. Suppose v is a nonempty set. S is a class over v, if S consists of finite subsets of v and has v as its union. Such a class is an intersecting class (IC) over v, if every two members of S have a nonempty intersection. An IC over v is called a maximal IC (MIC), if it is not properly included in any IC over v. It is known and readily proved that every MIC over a finite set v of cardinality n ≥ 1 has cardinality 2^n-1. In order to generalize this result we introduce the notion of an ω-MIC over v. This is an effective analogue ot the notion of an MIC over v such that a class over a finite set v is an ω-MIC iff it is an MIC. We then prove that every ω-MIC over an isolated set v of RET N ≥ 1 has RET 2^N-1. This is a generalization, for while there only are χ₀ finite sets, there are ? isolated sets, where c denotes the cardinality of the continuum, namely all the finite sets and the c immune sets. MSC: 03D50.     

Polar spaces of arbitrary rank

The incidence systems which satisfy the main axiom of Buekenhout and Shult, other than those related to generalized quadrangles, now have a satisfactory classification. Here the ones of infinite rank with no lines of cardinality 2 are characterized. They are the natural analogues of those of finite rank, and the nondegenerate ones arise from polarities or pseudoquadratic forms in the usual way. The treatment quotes some fundamental theorems of Tits, who handled the finite rank case, but is otherwise self-contained. A full exposition of the relevant concepts, with a new development of some of the elementary theory, is also given.Dedicated to Professor Jacques Tits on the occasion of his sixtieth birthday     

Certain Cuntz Semigroup Properties of Certain Crossed Product C*-algebras

We show that the following properties of the C^*-algebras in a class Ω are inherited by simple unital C-algebras in the class TAΩ:(1)(m,n)-decomposable,(2) weakly(m,n)-divisible,(3) weak Riesz interpolation.As an application,let A be an infinite dimensional simple unital C-algebra such that A has one of the above-listed properties.Suppose that α:G→Aut(A) is an action of a finite group G on A which has the tracial Rokhlin property.Then the crossed product C^*-algebra C^*(G,A,α) also has the property under consideration.     

d‐homogeneous and d‐ultrahomogeneous linear spaces

A linear space S is d‐homogeneous if, whenever the linear structures induced on two subsets S₁ and S₂ of cardinality at most d are isomorphic, there is at least one automorphism of S mapping S₁ onto S₂. S is called d‐ultrahomogeneous if each isomorphism between the linear structures induced on two subsets of cardinality at most d can be extended into an automorphism of S. We have proved in [11;] (without any finiteness assumption) that every 6‐homogeneous linear space is homogeneous (that is d‐homogeneous for every positive integer d). Here we classify completely the finite nontrivial linear spaces that are d‐homogeneous for d ≥ 4 or d‐ultrahomogeneous for d ≥ 3. We also prove an existence theorem for infinite nontrivial 4‐ultrahomogeneous linear spaces. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 321–329, 2000     

Über die Gleichstetigkeit von Mengen von linearen Abbildungen und eine Klasse von topologischen linearen Räumen

In the first part of this paper we proof the following theorem: Let E and F be topological linear spaces, α an infinite cardinal number, and H a set of linear mappings from E into F such that every subset G of H with cardinality |G|≤α is equicontinuous. Then H is equicontinuous on every linear subspace of E which is the closed linear hull of a family (B_L;L∈I), |I|≤α, of precompact subsets of E. In the second part we introduce the class of all topological linear spaces E with the following property: A set H of linear mappings from E into a topological linear space is equicontinuous, if every countable subset of H is equicontinuous. We show that this class is closed with respect to forming topological products and linear final topologies.     

Efficient finite groups arising in the study of relative asphericity

We study a class of two-generator two-relator groups, denoted \(J_n(m,k)\), that arise in the study of relative asphericity as groups satisfying a transitional curvature condition. Particular instances of these groups occur in the literature as finite groups of intriguing orders. Here we find infinite families of non-elementary virtually free groups and of finite metabelian non-nilpotent groups, for which we determine the orders. All Mersenne primes arise as factors of the orders of the non-metacyclic groups in the class, as do all primes from other conjecturally infinite families of primes. We classify the finite groups up to isomorphism and show that our class overlaps and extends a class of groups \(F^{a,b,c}\) with trivalent Cayley graphs that was introduced by C. M. Campbell, H. S. M. Coxeter, and E. F. Robertson. The theory of cyclically presented groups informs our methods and we extend part of this theory (namely, on connections with polynomial resultants) to “bicyclically presented groups” that arise naturally in our analysis. As a corollary to our main results we obtain new infinite families of finite metacyclic generalized Fibonacci groups.     

Algebra involutions on the bidual of a Banach algebra

Let A be a Banach algebra with bounded approximate right identity. We show that a necessary condition for the bidual of A to admit an algebra involution (with respect to the first Arens product) is that A*A=A*, i.e. the dual of A has to be essential as a right A-module. In particular, for any infinite, non-discrete, locally compact Hausdorff group G, L¹(G)** does not admit any algebra involution with respect to either Arens product. This implies that the main result of a paper of R.S. Doran and W. Tiller concerning L¹(G)** as Banach *-algebra (see [DT]) applies only to the trivial case of finite abelian groups.Essentially, the proof of the foregoing lemma is due to H.Rindler.     

On the Metric Dimension of Infinite Graphs

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph G is the minimum cardinality of a resolving set. In this paper we undertake the metric dimension of infinite locally finite graphs, i.e., those infinite graphs such that all its vertices have finite degree. We give some necessary conditions for an infinite graph to have finite metric dimension and characterize infinite trees with finite metric dimension. We also establish some general results about the metric dimension of the Cartesian product of finite and infinite graphs, and obtain the metric dimension of the Cartesian product of several families of graphs.     

Solvable infinite-dimensional linear groups with restrictions on the nonabelian subgroups of infinite rank

Under study are the solvable nonabelian linear groups of infinite central dimension and sectional p-rank, p ≥ 0, in which all proper nonabelian subgroups of infinite sectional p-rank have finite central dimension. We describe the structure of the groups of this class.     

A characterization of groupsPSL(3, q) by their element orders for certainq

Let G be a finite group and ω(G) the set of element orders ofG. Denote byh(ω(G)) the number of isomorphism classes of finite groupsH satisfying ω(G) = ω(H). In this paper, we show that forG =PSL(3,q),h(ω( G)) = 1 whereq = 11,13,19, 23, 25 and 27 andh(ω(G) = 2 whereq = 17 and 29.     

Generic pairs of SU-rank 1 structures

For a supersimple SU-rank 1 theory T we introduce the notion of a generic elementary pair of models of T (generic T-pair). We show that the theory T^* of all generic T-pairs is complete and supersimple. In the strongly minimal case, T^* coincides with the theory of infinite dimensional pairs, which was used in (S. Buechler, Pseudoprojective strongly minimal sets are locally projective, J. Symbolic Logic 56(4) (1991) 1184–1194) to study the geometric properties of T. In our SU-rank 1 setting, we use T^* for the same purpose. In particular, we obtain a characterization of linearity for SU-rank 1 structures by giving several equivalent conditions on T^*, find a “weak” version of local modularity which is equivalent to linearity, show that linearity coincides with 1-basedness, and use the generic pairs to “recover” projective geometries over division rings from non-trivial linear SU-rank 1 structures.     

Monochrome symmetric subsets of colored groups

In (Electron. J. Combin. 10 (2003); http://www.combinatorics.org/volume-10/Abstracts/v1oi1r28.html), the first author (Yuliya Gryshko) asked three questions. Is it true that every infinite group admitting a 2-coloring without infinite monochromatic symmetric subsets is either almost cyclic (i.e., have a finite index subgroup which is cyclic infinite) or countable locally finite? Does every infinite group G include a monochromatic symmetric subset of any cardinal <|G| for any finite coloring? Does every uncountable group G such that |B(G)|< |G| where B(G)={xG:x²=1}, admit a 2-coloring without monochromatic symmetric subsets of cardinality |G|? We answer the first question positively. Assuming the generalized continuum hypothesis (GCH), we give a positive answer to the second question in the abelian case. Finally, we build a counter-example for the third question and we give a necessary and sufficient condition for an infinite group G to admit 2-coloring without monochromatic symmetric subsets of cardinality |G|. This generalizes some results of Protasov on infinite abelian groups (Mat. Zametki 59 (1996) 468–471; Dopovidi NAN Ukrain 1 (1999) 54–57).     

Countably categorical theories

A series of countably categorical theories are constructed based on the Fra?sse method. In particular, an example of a decidable countably categorical theory in a finite signature is given for which no decidable model has an infinite computable set of order indiscernibles. Such a theory is used to refute Ershov’s conjecture on the representability of models of c-simple theories over linear orders.     

Oscillatory integrals and the method of stationary phase in infinitely many dimensions,with applications to the classical limit of quantum mechanics I

We give a theory of oscillatory integrals in infinitely many dimensions which extends, for a class of phase functions, the finite dimensional theory. In particular we extend the method of stationary phase, the theory of Lagrange immersions and the corresponding asymptotic expansions to the infinite dimensional case. A particular application of the theory to the Feyman path integrals defined in previous work by the authors yields asymptotic expansions to all orders of quantum mechanical quantities in powers of Planck's constant.Work supported by the Norwegian Research Council for Science and the Humanities