Expanders,rank and graphs of groups

LetG be a finitely presented group, and let {G _i } be a collection of finite index normal subgroups that is closed under intersections. Then, we prove that at least one of the following must hold: 1.G _i is an amalgamated free product or HNN extension, for infinitely manyi; 2. the Cayley graphs ofG/G _i (with respect to a fixed finite set of generators forG) form an expanding family; 3. inf_i(d(G _i )−1)/[G:G _i ]=0, whered(G _i ) is the rank ofG _i . The proof involves an analysis of the geometry and topology of finite Cayley graphs. Several applications of this result are given.     

Essentially finite algorithms for minimizing a class of convex piecewise polynomial functions

We consider minimax problems of the type min _t[a,b] max _i p _t (t), where thep _i (t) are real polynomials which are convex on an interval [a, b]. Here, the function max _i p _i (t) is a convex piecewise polynomial function. The main result is an algorithm yielding the minimum and the minimizing point, which is efficient with respect to the necessary number of computed polynomial zeros. The algorithms presented here are applicable to decision problems with convex loss. While primarily of theoretical interest, they are implementable for quadratic loss functions with finitely many states of nature. An example of this case is given. The algorithms are finite when polynomial zeros need not be approximated.The author is indebted to T. E. S. Raghavan for many stimulating discussions.     

A Remarkable Endofunction Involving Compositions

We define a state as an arbitrary composition of a non-negative integer n on m circularly labeled positions around a disk. A move is defined as the following endofunction: for each i, 1 ≤ i ≤ m; the value at position i (a non-negative integer s_i) is distributed clockwise, one unit at a time, to itself and the following (s_i ? 1) positions. The structures of states keep changing in irregular ways as we perform a series of moves. Definitions and necessary and sufficient conditions for cyclic states, root states, and leaf states are given in this paper. We provide the sharp upper bounds for the length of a path from a given nontrivial state to its nearest leaf state and for the length of a path from a given nontrivial state to its farthest leaf state in T (n, m). Surprisingly, it turns out that regardless of the initial state, one is sure to reach a cyclic state, which has only the values [n/m] and [(n + m ? 1)/m] at all positions, in at most m ? 1 moves.     

A proof of snevily’s conjecture

We prove Snevily’s conjecture, which states that for any positive integer k and any two k-element subsets {a ₁, …, a _k } and {b ₁, …, b _k } of a finite abelian group of odd order there exists a permutation π ∈ S _k such that all sums a _i + b _π(i) (i ∈ [1, k]) are pairwise distinct.     

On superstable groups with residual properties

Given a pseudovariety 𝒞, it is proved that a residually-𝒞 superstable group G has a finite series G ₀ ⊴ G ₁ ⊴ · · · ⊴ G _n = G such that G ₀ is solvable and each factor G _{i +1}/G _i is in 𝒞 (0 ≤ i ≤ n – 1). In particular, a residually finite superstable group is solvable-by-finite, and if it is ω -stable, then it is nilpotent-by-finite. Given a finitely generated group G, we show that if G is ω -stable and satisfies some residual properties (residual solvability, residual finiteness, …), then G is finite. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Zur Lösung einer Klasse von Gleichungen mit einem monotonen Potentialoperator

This paper is concerned with terminable and interminable paths and trails in infinite graphs. It is shown that

• The only connected graphs which contain no 2 – ∞ way and in which no finite path is terminable are precisely all the 1 – ∞ multiways.
• The only connected graphs which have no 2 – ∞ trail and in which no finite trail is terminable are precisely all the 1 – ∞ multiways all of whose multiplicities are odd numbers and which have infinitely many bridges.
• In addition the strucuture of those connected graphs is determined which have a 1 – ∞ trail and in which no 1 – ∞ trail but every finite trail is terminable.

In this paper the terminology and notation of a previous paper of the writer [1] and of F. HARARY 's book [6] will be used. Furthermore, a graph consisting of the distinct nodes n₁,…,n_δ (where δ≧1) and of one or more (n_i, n_i+1)-edges for i = 1,…, δ – 1 will be called a multiway, and analogously for 1 – ∞ and 2 – ∞ multiways. The number of edges joining n_i and n_i+1 will be called the (n_i,+1)-multiplicity. Thus a multiway in which each multiplicity is 1 is a way. Multiplicities are allowed to be infinite.     

A Globally Convergent Algorithm for a PDE-Constrained Optimization Problem Arising in Electrical Impedance Tomography

We study the convergence properties of an algorithm for the inverse problem of electrical impedance tomography, which can be reduced to a partial differential equation (PDE) constrained optimization problem. The direct problem consists of the potential equation div(??u) = 0 in a circle, with Neumann condition describing the behavior of the electrostatic potential in a medium with conductivity given by the function ?(x, y). We suppose that at each time a current ψ _i is applied to the boundary of the circle (Neumann's data), and that it is possible to measure the corresponding potential ? _i (Dirichlet data). The inverse problem is to find ?(x, y) given a finite number of Cauchy pairs measurements (? _i , ψ _i ), i = 1,…, N. The problem is formulated as a least squares problem, and the developed algorithm solves the continuous problem using descent iterations in its corresponding finite element approximations. Wolfe's conditions are used to ensure the global convergence of the optimization algorithm for the continuous problem. Although exact data are assumed, measurement errors in data and regularization methods shall be considered in a future work.     

Finiteness properties of minimax and coatomic local cohomology modules

Let R be a noetherian ring, \mathfraka{\mathfrak{a}} an ideal of R, and M an R-module. We prove that for a finite module M, if Hⁱ_\mathfraka(M){{\rm H}^{i}_{\mathfrak{a}}(M)} is minimax for all i ≥ r ≥ 1, then Hⁱ_\mathfraka(M){{\rm H}^{i}_{\mathfrak{a}}(M)} is artinian for i ≥ r. A local–global principle for minimax local cohomology modules is shown. If Hⁱ_\mathfraka(M){{\rm H}^{i}_{\mathfrak{a}}(M)} is coatomic for i ≤ r (M finite) then Hⁱ_\mathfraka(M){{\rm H}^{i}_{\mathfrak{a}}(M)} is finite for i ≤ r. We give conditions for a module which is locally minimax to be a minimax module. A non-vanishing theorem and some vanishing theorems are proved for local cohomology modules.     

Relatively pseudocomplemented semilattices amalgamate strongly

Letk be any finite or infinite cardinal andS _ω the symmetric group of denumerable infinite degree. It is shown that fori<k ifG _i is thei-th row of a matrix whose columns are allk-termed sequences of elements ofS _ω in each of which all but a finite number of terms are equal to the identity ofS _ω thenG _i 's (withG _i ⁻¹ 's defined in an obvious way and with coordinatewise multiplication amongG _i 's andG _i ⁻¹'s) generate the Free Group onk free generatorsG _i . Analogously, Free Abelian and other types of free groups are also constructed. Presented by L. Fuchs.     

A Note on the Associated Primes of Local Cohomology Modules

In this note we give a simple proof of the following result: Let R be a commutative Noetherian ring,  an ideal of R and M a finite R-module, if H_ ⁱ (M) has finite support for all i < n, then Ass(H_ ⁿ (M)) is finite.     

Polynomial Birth–Death Distribution Approximation in the Wasserstein Distance

The polynomial birth–death distribution (abbreviated, PBD) on ℐ={0,1,2,…} or ℐ={0,1,2,…,m} for some finite m introduced in Brown and Xia (Ann. Probab. 29:1373–1403, 2001) is the equilibrium distribution of the birth–death process with birth rates {α _i } and death rates {β _i }, where α _i ≥0 and β _i ≥0 are polynomial functions of i∈ℐ. The family includes Poisson, negative binomial, binomial, and hypergeometric distributions. In this paper, we give probabilistic proofs of various Stein’s factors for the PBD approximation with α _i =a and β _i =i+bi(i−1) in terms of the Wasserstein distance. The paper complements the work of Brown and Xia (Ann. Probab. 29:1373–1403, 2001) and generalizes the work of Barbour and Xia (Bernoulli 12:943–954, 2006) where Poisson approximation (b=0) in the Wasserstein distance is investigated. As an application, we establish an upper bound for the Wasserstein distance between the PBD and Poisson binomial distribution and show that the PBD approximation to the Poisson binomial distribution is much more precise than the approximation by the Poisson or shifted Poisson distributions.      

Sphere orders

Ann-sphere order is a finite partially ordered set representable by containment ofn-spheres in Euclidean (n+1)-space. We present a sequence {P _i } of ordered sets such that eachP _i is ann-sphere order only forni; one consequence is that we are able to determine the dimension of a Euclidean space-time manifold from the finite suborders of its causality order.Research supported by ONR grant N00014 85-K-0769.     

Extending partial isomorphisms on finite structures

We prove the following theorem:Let A be a finite structure in a fixed finite relational language,p ₁,...,p _m partial isomorphisms of A. Then there exists a finite structure B, and automorphismsf _i of B extending thep _i 's. This theorem can be used to prove the small index property for the random structure in this language. A special case of this theorem is, if A and B are hypergraphs. In addition we prove the theorem for the case of triangle free graphs.     

Asymptotic Properties of Self-Consistent Estimators with Mixed Interval-Censored Data

Mixed interval-censored (MIC) data consist of n intervals with endpoints L _i and R _i , i = 1, ..., n. At least one of them is a singleton set and one is a finite non-singleton interval. The survival time X _i is only known to lie between L _i and R _i , i = 1, 2, ..., n. Peto (1973, Applied Statistics, 22, 86–91) and Turnbull (1976, J. Roy. Statist. Soc. Ser. B, 38, 290–295) obtained, respectively, the generalized MLE (GMLE) and the self-consistent estimator (SCE) of the distribution function of X with MIC data. In this paper, we introduce a model for MIC data and establish strong consistency, asymptotic normality and asymptotic efficiency of the SCE and GMLE with MIC data under this model with mild conditions.     

Speed of convergence in nonparametric kernel estimation of a regression function and its derivatives

Summary The objective in nonparametric regression is to infer a functiong(x) and itspth order derivativesg ^(g)(x),p≧1 fixed, on the basis of a finite collection of pairs {x _i, g(x_i)+Z _i} _i=1 ⁿ , where the noise componentsZ _i satisfy certain modest assumptions and the domain pointsx _i are selected non-randomly. This paper exhibits a new class of kernel estimatesg _n ^(p) ,p≧0 fixed. The main theoretical results of this study are the rates of convergence obtained for mean square and strong consistency ofg _n ^(p) each of them being uniform on the (0,1).     

Ein Algorithmus zur zyklisch invarianten Zerlegung eines endlich-dimensionalen Vektorraums bezüglich einer linearen Selbstabbildung

An algorithm for the decomposition of a finite dimensional vector spaceV into a direct sum of cyclic subspacesV _i (of non increasing dimension) relative to an endomorphismA ofV is given, such that the minimum polynomial ofA|V _i+1 divides the minimum polynomial ofA|V _i.     

Centralizers of Involutions in Locally Finite Groups

The present article deals with locally finite groups G having an involution φ such that C _G (φ) is an SF-group. It is shown that G possesses a normal subgroup B which is a central product of finitely many groups isomorphic to PSL(2, K _i ) or SL(2, K _i ) for some infinite locally finite fields K _i of odd characteristic, such that [G, φ]′/B and G/[G, φ] are both SF-groups.     

Coherent Functors and Covariantly Finite Subcategories

Given a locally presentable additive category A, we study a class of covariantly finite subcategories which we call definable. A definable subcategory arises from a set of coherent functors F _i on A by taking all objects X in A such that F _i X=0 for all i. We give various characterizations of definable subcategories, demonstrating that all covariantly finite subcategories which arise in practice are of this form. This is based on a filtration of the category of all coherent functors on A.     

Extensions of homogeneous polynomials on c 0(l 2 i )

We show that a 2-homogeneous polynomial on the complex Banach space c ₀ l ₂ ⁱ ) is norm attaining if and only if it is finite (i.e, depends only on finite coordinates). As the consequence, we show that there exists a unique norm-preserving extension for norm-attaining 2-homogeneous polynomials on c ₀(l ₂ ⁱ ). The second author was supported by FAPESP, Brazil, Research Grant 01/04220-8.     

Induced subgraphs and well-quasi-ordering

We study classes of finite, simple, undirected graphs that are (1) lower ideals (or hereditary) in the partial order of graphs by the induced subgraph relation ≤_i, and (2) well-quasi-ordered (WQO) by this relation. The main result shows that the class of cographs (P₄-free graphs) is WQO by ≤_i, and that this is the unique maximal lower ideal with one forbidden subgraph that is WQO. This is a consequence of the famous Kruskal theorem. Modifying our idea we can prove that P₄-reducible graphs build a WQO class. Other examples of lower ideals WQO by ≤_i are also given.