On triangle-free 3-connected matroids

We present a method to construct any triangle-free 3-connected matroid starting from a matroid belonging to one of four infinite families and subsequently performing a sequence of small operations on it. This result extends to matroids a theorem proved by Kriesell for graphs.     

Externally definable sets and dependent pairs

We prove that externally definable sets in first order NIP theories have honest definitions, giving a new proof of Shelah’s expansion theorem. Also we discuss a weak notion of stable embeddedness true in this context. Those results are then used to prove a general theorem on dependent pairs, which in particular answers a question of Baldwin and Benedikt on naming an indiscernible sequence.     

A Weighted König Lemma for Symbolic Dynamics

The König Lemma for infinite trees in Graph Theory says that in an infinite rooted tree with all vertices of finite degree, there is an infinite path starting from the root. In this weighted version we shall show that there is an infinite path with weights greater than a certain average. We shall apply our result to infinite compositions of affine mappings in Rⁿ.     

On different geometric formulations of Lagrangian formalism

We consider two geometric formulations of Lagrangian formalism on fibred manifolds: Krupka's theory of finite order variational sequences, and Vinogradov's infinite order variational sequence associated with the -spectral sequence. On one hand, we show that the direct limit of Krupka's variational bicomplex is a new infinite order variational bicomplex which yields a new infinite order variational sequence. On the other hand, by means of Vinogradov's -spectral sequence, we provide a new finite order variational sequence whose direct limit turns out to be the Vinogradov's infinite order variational sequence. Finally, we provide an equivalence of the two finite order and infinite order variational sequences modulo the space of Euler-Lagrange morphisms.     

A law of the iterated logarithm for Markov chains on ℕ0 associated with orthogonal polynomials

We derive laws of the iterated logarithm for Markov chains on the nonnegative integers whose transition probabilities are associated with a sequence of orthogonal polynomials. These laws can be applied to a large class of birth and death random walks and random walks on polynomial hypergroups. In particular, the results of our paper lead immediately to a law of the iterated logarithm for the growth of the distance of isotropic random walks on infinite distance-transitive graphs as well as on certain finitely generated semigroups from their starting points.     

A Birman exact sequence for Aut(Fn)

The Birman exact sequence describes the effect on the mapping class group of a surface with boundary of gluing discs to the boundary components. We construct an analogous exact sequence for the automorphism group of a free group. For the mapping class group, the kernel of the Birman exact sequence is a surface braid group. We prove that in the context of the automorphism group of a free group, the natural kernel is finitely generated. However, it is not finitely presentable; indeed, we prove that its second rational homology group has infinite rank by constructing an explicit infinite collection of linearly independent abelian cycles. We also determine the abelianization of our kernel and build a simple infinite presentation for it. The keys to many of our proofs are several new generalizations of the Johnson homomorphisms.     

On an iterated construction of irreducible polynomials over finite fields of even characteristic by Kyuregyan

We deal with the construction of sequences of irreducible polynomials with coefficients in finite fields of even characteristic. We rely upon a transformation used by Kyuregyan in 2002, which generalizes the Q-transform employed previously by Varshamov and Garakov (1969) as well as by Meyn (1990) for the synthesis of irreducible polynomials. While in the iterative procedure described by Kyuregyan the coefficients of the initial polynomial of the sequence have to satisfy certain hypotheses, in the present paper these conditions are removed. We construct infinite sequences of irreducible polynomials of nondecreasing degree starting from any irreducible polynomial.     

Factorizations of infinite sequences in semigroups

It follows from the Ramsey theorem that every infinite sequence of elements of a finite semigroup has an infinite factorization of the form x, e, e, e, ..., where e is an idempotent of the semigroup. We describe all semigroups with this property and with its analog for two-sided infinite sequences.     

On nonrepetitive sequences

We prove the following results: (1) There exists an infinite binary sequence having no identical adjacent blocks of length 3 or greater. (2) Every binary sequence of length greater than 18 has identical adjacent blocks of length 2 or greater. (3) Every infinite binary sequence has arbitrarily long adjacent blocks that are permutations of each other.     

Un teorema di esistenza per campi di orientori e applicazioni al problema libero del Calcolo delle Variazioni in dimensione infinita

Summary We prove a compactness theorem for a sequence of functions which take values in an infinite dimensional Hilbert space and which satisfy a differential inclusion, related to a map Q. Then we give sufficient conditions for the existence of an optimal solution of a free Lagrange problem, always in the infinite dimensional case, applying the theorem previously proved to a minimizing sequence.

---

---

Entrata in Redazione il 19 maggio 1978.     

Multiplicative structures in additively large sets

Previous research extending over a few decades has established that multiplicatively large sets (in any of several interpretations) must have substantial additive structure. We investigate here the question of how much multiplicative structure can be found in additively large sets. For example, we show that any translate of a set of finite sums from an infinite sequence must contain all of the initial products from another infinite sequence. And, as a corollary of a result of Renling Jin, we show that if A and B have positive upper Banach density, then A+B contains all of the initial products from an infinite sequence. We also show that if a set has a complement which is not additively piecewise syndetic, then any translate of that set is both additively and multiplicatively large in several senses.We investigate whether a subset of N with bounded gaps—a syndetic set—must contain arbitrarily long geometric progressions. We believe that we establish that this is a significant open question.     

Examples of entropy generating sequence

We introduce the notion of entropy generating sequence for infinite words and define its dimension when it exists. We construct an entropy generating sequence for each symbolic example constructed by Cassaigne such that the dimension of the sequence is the same as its topological entropy dimension. Hence the complexity can be measured via the dimension of an entropy generating sequence. Moreover, we construct a weakly mixing example with subexponential growth rate.     

Conditions for the discovery of solution horizons

We present necessary and sufficient conditions for discrete infinite horizon optimization problems with unique solutions to be solvable. These problems can be equivalently viewed as the task of finding a shortest path in an infinite directed network. We provide general forward algorithms with stopping rules for their solution. The key condition required is that of weak reachability, which roughly requires that for any sequence of nodes or states, it must be possible from optimal states to reach states close in cost to states along this sequence. Moreover the costs to reach these states must converge to zero. Applications are considered in optimal search, undiscounted Markov decision processes, and deterministic infinite horizon optimization.This work was supported in part by NSF Grant ECS-8700836 to The University of Michigan.     

有关常数项级数的几个典型例题

通过实例考察常数项级数收敛和发散时一般项的一些特点,并讨论级数不满足比值判别法、根值判别法或莱布尼茨定理的条件时的收敛性问题.     

On Better-Quasi-Ordering Countable Series-Parallel Orders

We prove that any infinite sequence of countable series-parallel orders contains an increasing (with respect to embedding) infinite subsequence. This result generalizes Laver's and Corominas' theorems concerning better-quasi-order of the classes of countable chains and trees.

     

On Sums of Overlapping Products of Independent Bernoulli Random Variables

We find the exact distribution of an arbitrary remainder of an infinite sum of overlapping products of a sequence of independent Bernoulli random variables.     

Parker Vectors for Infinite Groups

We take the first step towards establishing a theory of Parker vectors for infinite permutation groups, with an emphasis towards oligomorphic groups. We show that, on the one hand, many results for finite groups extend naturally to the infinite case (Parker’s Lemma, multiplicative properties, etc.), while on the other, in the infinite case some genuinely new phenomena arise. We also note that calculating Parker vectors of oligomorphic groups is akin to counting circulant combinatorial objects, mirroring in a sense the combinatorial meaning of the orbit-counting sequence of an oligomorphic group. Finally we explicitly find the Parker vectors for some groups, one of which being the automorphism group of the Rado graph.     

Convex infinite horizon programs

We establish conditions under which a sequence of finite horizon convex programs monotonically increases in value to the value of the infinite program; a subsequence of optimal solutions converges to the optimal solution of the infinite problem. If the conditions we impose fail, then (roughtly) the optimal value of the infinite horizon problem is an improper convex function. Under more restrictive conditions we establish the necessary and sufficient conditions for optimality. This constructive procedure gives us a way to solve the infinite (long range) problem by solving a finite (short range) problem. It appears to work well in practice.     

A variation of sweedler's complex and the group of galois objects of an infinite hopf algebra

Let H be a cocommutative faithfully flat Hopf algebra over a commutative ring R. We give a four term exact sequence describing the group of H-Galois objects. This generalizes an exact sequence due to Early and Kreimer and Yokogawa. We have to introduce the Picard group of a coalgebra, and a new type of Sweedler cohomology. Using methods of Villamayor and Zelinsky and Hattori, we can extend the four term exact sequence to a sequence of infinite length.     

Dynamique des homéomorphismes du plan au voisinage d'un point fixe

We study the dynamics of a homeomorphism of a surface near a fixed point. We compute the sequence of the Lefschetz indices of the iterates of the map. We deduce the existence of an infinite number of periodic orbits for some conservative homeomorphisms of surfaces.