Chain Lengths in Certain Random Directed Graphs

We study the random directed graph with vertex set {1, …, n} in which the directed edges (i, j) occur independently with probability c_n/n for i<j and probability zero for i ? j. Let M_n (resp., L_n) denote the length of the longest path (resp., longest path starting from vertex 1). When c_n is bounded away from 0 and ∞ as n→∞, the asymptotic behavior of M_n was analyzed in previous work of the author and J. E. Cohen. Here, all restrictions on c_n are eliminated and the asymptotic behavior of L_n is also obtained. In particular, if c_n/ln(n)→∞ while c_n/n→0, then both M_n/c_n and L_n/c_n are shown to converge in probability to the constant e.     

Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

The Arcsine Law

Let N _n denote the number of positive sums in the first n trials in a random walk (S _i) and let L _n denote the first time we obtain the maximum in S ₀,..., S _n. Then the classical equivalence principle states that N _n and L _n have the same distribution and the classical arcsine law gives necessary and sufficient condition for (1/n) L _n or (1/n) N _n to converge in law to the arcsine distribution. The objective of this note is to provide a simple and elementary proof of the arcsine law for a general class of integer valued random variables (T _n) and to provide a simple an elementary proof of the equivalence principle for a general class of integer valued random vectors (N _n, L _n).     

Chromatic factorizations of a graph

Let n₁ ? n₂ ? …? ? n_k ? 2 be integers. We say that G has an (n₁, n₂, …?, n_k-chromatic factorization if G) can be edge-factored as G₁ ⊕ G₂ ⊕ …? ⊕ G_k with χ(G_i) = nA_i, for i = 1,2,…, k. The following results are proved:

• i If (n₁ ? 1)n₂ …? n_k < χ(G) ? n₁n₂ …? n_k, then G has an (n₁, n₂, …?, n_k)-chromatic factorization.
• ii If n₁ + n₂ + …? + n_k ? (k - 1) ? n ? n₁n₂ …? n_k, then K_n has an (n₁, n₂, …?, n_k)-chromatic factorization.

     

Über nicht-holonome Übertragungen in einerL n

Ohne Zusammenfassung X _n =n-dimensionale Mannigfaltigkeit;L _n =X _n mit einer linearen (überschiebungsinvarianten) Übertragung;A _n =L _n mit symmetrischer Übertragung;E _n=euklidischeA _n;V _n =L _n mit Riemannscher Übertragung;R _n=euklidischeV _n.     

Extendible elements of the alternating groups

An element?σ?of A_n , the Alternating group of degree n, is extendible in S_n , the Symmetric group of degree n, if there exists a subgroup H of S_n but not A_n whose intersection with A_n is the cyclic group generated by σ. A simple number-theoretic criterion, in terms of the cycle-decomposition, for an element of A_n to be extendible in S_n is given here.     

Fully invariant transformations and associated groups

It is well known that the symmetric group S _ntogether with one idempotent of rank n- 1 on a finite n-element set Nserves as a set of generators for the semigroup T _nof all the total transformations on N. It is also well known that the singular part Sing _n of T _n can be generated by a set of idempotents of rank n- 1. The purpose of this paper is to begin an investigation of the way in which Sing_nand its subsemigroups can be generated by the conjugates of a subset of elements of T _n by a subgroup of S _n . We look for the smallest subset of elements of T _n that will serve and, correspondingly, for a characterization of those subgroups of S _n that will serve. Using some techniques from graph theory we prove our main result:the conjugates of a single transformation of rank n- 1 under Gsuffice to generate Sing_nif and only if Gis what we define to be a 2-block transitive subgroup of S _n .     

Adaptive policies for time-varying stochastic systems under discounted criterion

We consider a class of time-varying stochastic control systems, with Borel state and action spaces, and possibly unbounded costs. The processes evolve according to a discrete-time equation x _{n + 1}=G _n (x _n , a _n , ξ_n), n=0, 1, … , where the ξ_n are i.i.d. ℜ^k-valued random vectors whose common density is unknown, and the G _n are given functions converging, in a restricted way, to some function G _∞ as n→∞. Assuming observability of ξ_n, we construct an adaptive policy which is asymptotically discounted cost optimal for the limiting control system x _n+1=G _∞ (x _n , a _n , ξ_n).     

A-acceptability of derivatives of rational approximations to EXP(Z)

The question of A-acceptability in regard to derivatives of R_m/n, the [m/n] Padé approximation to the exponential, is examined for a range of values of m and n. It is proven that R′_{n − 1/n}, R′_n/n, R′_{n + 1/n}and R″_n/n are A-acceptable and that numerous other choices of m and n lead to non-A-acceptability. The results seem to indicate that the A-acceptability pattern of R_m/n^(k) displays an intriguing generalization of the Wanner-Hairer-Nørsett theorem on the A-acceptability of R_m/n.     

Envelopes,indicators and conservativeness

A well known theorem proved (independently) by J. Paris and H. Friedman states that B Σ_{n +1} (the fragment of Arithmetic given by the collection scheme restricted to Σ_{n +1}‐formulas) is a Π_{n +2}‐conservative extension of I Σ_n (the fragment given by the induction scheme restricted to Σ_n ‐formulas). In this paper, as a continuation of our previous work on collection schemes for Δ_{n +1}(T )‐formulas (see [4]), we study a general version of this theorem and characterize theories T such that T + B Σ_{n +1} is a Π_{n +2}‐conservative extension of T . We prove that this conservativeness property is equivalent to a model‐theoretic property relating Π_n ‐envelopes and Π_n ‐indicators for T . The analysis of Σ_{n +1}‐collection we develop here is also applied to Σ_{n +1}‐induction using Parsons' conservativeness theorem instead of Friedman‐Paris' theorem. As a corollary, our work provides new model‐theoretic proofs of two theorems of R. Kaye, J. Paris and C. Dimitracopoulos (see [8]): B Σ_{n +1} and I Σ_{n +1} are Σ_{n +3}‐conservative extensions of their parameter free versions, B Σ^–_{n +1} and I Σ^–_{n +1}. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On Overspill Principles and Axiom Schemes for Bounded Formulas

We study the theories I?_n, L?_n and overspill principles for ?_n formulas. We show that IE_n ? L?_n ? I?_n, but we do not know if I?_n L?_n. We introduce a new scheme, the growth scheme Crγ, and we prove that L?_n ? Cr?_n? I?_n. Also, we analyse the utility of bounded collection axioms for the study of the above theories. Mathematics Subject Classification: 03F30, 03H15.     

Embedding Structures

 For any quasiordered set (`quoset') or topological space S, the set Sub S of all nonempty subquosets or subspaces is quasiordered by embeddability. Given any cardinal number n, denote by p _n and q _n the smallest size of spaces S such that each poset, respectively, quoset with n points is embeddable in Sub S. For finite n, we prove the inequalities n + 1 ≤p _n ≤q _n ≤p _n + l(n) + l(l(n)), where l(n) = min{k∈ℕ∣n≤2 ^k }. For the smallest size b _n of spaces S so that Sub S contains a principal filter isomorphic to the power set ?(n), we show n + l(n) − 1 ≤b _n ≤n + l(n) + l(l(n))+2. Since p _n ≤b _n , we thus improve recent results of McCluskey and McMaster who obtained p _n ≤n ². For infinite n, we obtain the equation b _n = p _n = q _n = n. Received: April 19, 1999 Final version received: February 21, 2000     

On the convex hull of uniform random points in a simpled-polytope

Denote the expected number of facets and vertices and the expected volume of the convex hullP _n ofn random points, selected independently and uniformly from the interior of a simpled-polytope byE _n (f), E _n (v), andE _n (V), respectively. In this note we determine the sharp constants of the asymptotic expansion ofE _n (f), E _n (v), andE _n (V), asn tends to infinity. Further, some results concerning the expected shape ofP _n are given. The work of F. Affentranger was supported by the Swiss National Foundation.     

Packing graphs with odd and even trees

The Gyárfás-Lehel tree-packing conjecture asserts that any sequence T₁, T₂, …, T_n^?1 of trees with 1, 2, …, n - 1 edges packs into the complete graph K_n on n vertices. The present paper examines two conjectures that jointly imply the Gyárfás-Lehel conjecture: 1. For n even, any T₁, T₃, …, T_n^?1 pack into the half-complete graph Hn on n vertices.2. For n odd, any T₂, T₄, …, T_n^?1 pack into the half-complete graph Hn on n vertices. The H_n are uniquely defined by their degree sequences: H_n and H_n+1 are complements in K_n+1. It is shown that H_n and T_n+1 pack into H_n+2 if T_n+1 is a double star, unimodal triple star, interior-3 caterpillar, or scorpion. Hence Conjectures 1 and 2 are true for these specialized types of trees. The conjectures are also valid for all trees when n ≤ 9, so that the Gyárfás-Lehel conjecture holds for n ≤ 9.     

Convexity of the permanent for doubly stochastic matrices

Let Ω _n denote the set of all n×n doubly stochastic matrices and let J_n denote the n×n matrix all of whose entries are 1/n. Lih and Wang conjectuted that per[(1?i)J_n +iA≤(1?i)perJ_n 1i perA for all A∈Ω _n and all t∈[0,1/2], and proved their conjecture for n=3. In this paper we propose a similar conjecture asserting that for any A∈Ω _n \{J_n }, the permanent function is strietly convex on the straight line segment joining J_n and (J_n +A)/2, and prove it for the case n=3.     

A-identities for upper triangular matrices: A question of Henke and Regev

Let K be a field of characteristic 0, and let UT _n (K) be the algebra of n × n upper triangular matrices over K. We denote by P _n the vector space of all multilinear polynomials of degree n in x ₁, …, x _n in the free associative algebra K(X). Then P _n is a left S _n -module where the symmetric group S _n acts on P _n by permuting the variables. The S _n -modules P _n and KS _n are canonically isomorphic, a fact that lets us employ the representation theory in the study of algebras with polynomial identities. Denote by A _n the alternative subgroup of S _n . One may study KA _n and its isomorphic copy in P _n with the corresponding action of A _n . Henke and Regev studied A-identities. They described the A-codimensions of the Grassmann algebra and conjectured a finite generating set of the A-identities for E. In an earlier paper we answered in the affirmative their conjecture. Another problem posed by Henke and Regev concerned the minimal degree of an A-identity satisfied by the full matrix algebra M _n (K). They asked whether this minimal degree equals 2n+2. In this paper we show that this is not the case as long as n ≥ 6. Our main result consists in computing a lower bound for the minimal degree d(n) of an A-identity satisfied by the algebra UT _n (K). It turns out that, given any positive integer k, there exists n ₀ such that d(n) > 2n + k for all n > n ₀. Moreover, we compute d(n) for n ≤ 4 and for n = 6. It turns out that d(6) = 15 > 2 × 6 + 2. We have reasons to believe that for every n, d(n) = [(5n + 1)/2] holds, where as usual [x] stands for the integer part of the real number x, that is the largest integer ≤ x.     

Diophantine approximation generalized

In this paper we study the set of x ∈ [0, 1] for which the inequality |x − x _n | < z _n holds for infinitely many n = 1, 2, .... Here x _n ∈ [0, 1) and z _n s> 0, z _n → 0, are sequences. In the first part of the paper we summarize known results. In the second part, using the theory of distribution functions of sequences, we find the asymptotic density of n for which |x − x _n | < z _n , where x is a discontinuity point of some distribution function of x _n . Generally, we also prove, for an arbitrary sequence x _n , that there exists z _n such that the density of n = 1, 2, ..., x _n → x, is the same as the density of n = 1, 2, ..., |x − x _n | < z _n , for x ∈ [0, 1]. Finally we prove, using the longest gap d _n in the finite sequence x ₁, x ₂, ..., x _n , that if d _n ≤ z _n for all n, z _n → 0, and z _n is non-increasing, then |x − x _n | < z _n holds for infinitely many n and for almost all x ∈ [0, 1].     

Maximal regular subsemigroups of certain semigroups of transformations

Let T _n and P _n be the full and partial transformation semigroups on a finite set of order n respectively. The properties of the subsemigroups of T _n and P _n have been widely studied. But the maximal regular subsemigroups of T _n and P _n seem to be unknown. In this note, we determine all the maximal regular subsemigroups of all ideals of T _n and P _n . April 7, 1999