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.     

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.     

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).     

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 .     

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.     

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)     

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.     

Heavy-traffic limits for nearly deterministic queues: stationary distributions

We establish heavy-traffic limits for stationary waiting times and other performance measures in G _n /G _n /1 queues, where G _n indicates that an original point process is modified by cyclic thinning of order n, i.e., the thinned process contains every nth point from the original point process. The classical example is the Erlang E _n /E _n /1 queue, where cyclic thinning of order n is applied to both the interarrival times and the service times, starting from a “base” M/M/1 model. The models G _n /D/1 and D/G _n /1 are special cases of G _n /G _n /1. Since waiting times before starting service in the G/D/n queue are equivalent to waiting times in an associated G _n /D/1 model, where the interarrival times are the sum of n consecutive interarrival times in the original model, the G/D/n model is a special case as well. As n→∞, the G _n /G _n /1 models approach the deterministic D/D/1 model. We obtain revealing limits by letting ρ _n ↑1 as n→∞, where ρ _n is the traffic intensity in model n.     

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.     

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.     

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

We study the solutions of Toeplitz systemsA _n x=b by the preconditioned conjugate gradient method. Then ×n matrixA _n is of the forma ₀ I+H _n wherea ₀ is a real number,I is the identity matrix andH _n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC _n and the skew-circulant matrixS _n whereA _n =1/2(C _n +S _n ). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC ^–1 _n A_n andS ^–1 _n A _n . For Toeplitz matricesA _n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC _n andS _n and prove that the singular values ofC ^–1 _n A _n andS ^–1 _n A _n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.     

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.     

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     

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     

Bijections for ternary trees and non-crossing trees

The number N_n of non-crossing trees of size n satisfies N_n+1=T_n where T_n enumerates ternary trees of size n. We construct a new bijection to establish that fact. Since , it follows that 3(3n−1)(3n−2)T_n−1=2n(2n+1)T_n. We construct two bijections “explaining” this recursion; one of them easily extends to the case of t-ary trees.