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.     

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.     

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     

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

Cluster tilting for higher Auslander algebras

The concept of cluster tilting gives a higher analogue of classical Auslander correspondence between representation-finite algebras and Auslander algebras. The n-Auslander–Reiten translation functor τn plays an important role in the study of n-cluster tilting subcategories. We study the category Mn of preinjective-like modules obtained by applying τn to injective modules repeatedly. We call a finite-dimensional algebra Λ n-complete if for an n-cluster tilting object M. Our main result asserts that the endomorphism algebra EndΛ(M) is (n+1)-complete. This gives an inductive construction of n-complete algebras. For example, any representation-finite hereditary algebra Λ(1) is 1-complete. Hence the Auslander algebra Λ(2) of Λ(1) is 2-complete. Moreover, for any n?1, we have an n-complete algebra Λ(n) which has an n-cluster tilting object M(n) such that Λ(n+1)=EndΛ(n)(M(n)). We give the presentation of Λ(n) by a quiver with relations. We apply our results to construct n-cluster tilting subcategories of derived categories of n-complete algebras.     

The graphical relaxation: A new framework for the symmetric traveling salesman polytope

A present trend in the study of theSymmetric Traveling Salesman Polytope (STSP(n)) is to use, as a relaxation of the polytope, thegraphical relaxation (GTSP(n)) rather than the traditionalmonotone relaxation which seems to have attained its limits. In this paper, we show the very close relationship between STSP(n) and GTSP(n). In particular, we prove that every non-trivial facet of STSP(n) is the intersection ofn + 1 facets of GTSP(n),n of which are defined by the degree inequalities. This fact permits us to define a standard form for the facet-defining inequalities for STSP(n), that we calltight triangular, and to devise a proof technique that can be used to show that many known facet-defining inequalities for GTSP(n) define also facets of STSP(n). In addition, we give conditions that permit to obtain facet-defining inequalities by composition of facet-defining inequalities for STSP(n) and general lifting theorems to derive facet-defining inequalities for STSP(n +k) from inequalities defining facets of STSP(n).Partially financed by P.R.C. Mathématique et Informatique.     

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n²/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n²/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n²/log n) processors in the CRCW model and in time O(log²n) with O(n²/log n log log n) processors in the EREW model.     

Fixed Points of Automorphisms of Graphs with 1 – Factorizations

We consider sets of fixed points of finite simple undirected connected graphs with 1 – factorizations. The maximum number of fixed points of complete graphs K_2n (n > 2) is n if n ≡ 0 mod 4, n — 1 if n ≡ 3 mod 4 or n ≡ 5 mod 12, n — 2 if n ≡ 2 mod 4, n — 3 if n ≡ 1 mod 4 and n ≢ 5 (mod 12). The maximum number of fixed points of 1 – factorizations of (non – complete) graphs with 2n vertices is less than or equal to n. If n is a prime number, then there are graphs with 2n vertices whose 1 – factorizations have automorphisms with n fixed points. Moreover, a result on the structure of a group of fixed – point – free automorphisms is presented.     

Some Properties of Bell Groups

For any integer n ≠ 0,1, a group G is said to be “n-Bell” if it satisfies the identity [x ⁿ ,y] = [x,y ⁿ ]. It is known that if G is an n-Bell group, then the factor group G/Z ₂(G) has finite exponent dividing 12n ⁵(n ? 1)⁵. In this article we show that this bound can be improved. Moreover, we prove that every n-Bell group is n-nilpotent; consequently, using results of Baer on finite n-nilpotent groups, we give the structure of locally finite n-Bell groups. Finally, we are concerned with locally graded n-Bell groups for special values of n.     

Largest 4-connected components of 3-connected planar triangulations

Let T_n be a 3-connected n-vertex planar triangulation chosen uniformly at random. Then the number of vertices in the largest 4-connected component of T_n is asymptotic to n/2 with probability tending to 1 as n → ∞. It follows that almost all 3-connected triangulations with n vertices have a cycle of length at least n/2 + o(n).     

Small quasimultiple affine and projective planes: Some improved bounds

We improve the known bounds on r(n): = min {λ| an (n², n, λ)-RBIBD exists} in the case where n + 1 is a prime power. In such a case r(n) is proved to be at most n + 1. If, in addition, n − 1 is the product of twin prime powers, then r(n) ${\ \le \ }{n \over 2}$. We also improve the known bounds on p(n): = min{λ| an (n² + n + 1, n + 1, λ)-BIBD exists} in the case where n² + n + 1 is a prime power. In such a case p(n) is bounded at worst by but better bounds could be obtained exploiting the multiplicative structure of GF(n² + n + 1). Finally, we present an unpublished construction by M. Greig giving a quasidouble affine plane of order n for every positive integer n such that n − 1 and n + 1 are prime powers. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 337–345, 1998     

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 .     

On digraphs without antidirected cycles

Let t(n) denote the greatest number of arcs in a diagraph of orders n which does not contain any antidrected cycles. We show that [16/5(n ? 1)] ≤ t(n) ≤ 1/2 (n ? 1) for n ≥ 5. Let t_r (n) denote the corresponding quantity for r-colorable digraphs. We show that [16/5(n ? 1)] ≤ t₅(n) ≤ t₆(n) ≤ 10/3(n ? 1) for n ≥ 5 and that t₄(n) = 3(n ? 1) for n ≥ 3.     

New series of odd non-congruent numbers

We determine all square-free odd positive integers n such that the 2-Selmer groups S _n and Ŝ _n of the elliptic curve E _n : y ² = x(x − n)(x − 2n) and its dual curve ê _n : y ² = x ³ + 6nx ² + n ² x have the smallest size: S _n = {1}, Ŝ _n = {1, 2, n, 2n}. It is well known that for such integer n, the rank of group E _n (ℚ) of the rational points on E _n is zero so that n is a non-congruent number. In this way we obtain many new series of elliptic curves E _n with rank zero and such series of integers n are non-congruent numbers. Dedicated to Professor Sheng GONG on the occasion of his 75th birthday     

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.     

An intermediate value theorem for graphs with given automorphism group

For a positive integer n and a finite group G, let the symbols e(G, n) and E(G, n) denote, respectively, the smallest and the greatest number of lines among all n-point graphs with automorphism group G. We say that the Intermediate Value Theorem (IVT) holds for G and n, if for each e satisfying e(G, n)≤e≤E(G, n), there exists an n-point graph with group G and e lines. The main result of this paper states that for every group G the IVT holds for all sufficiently large n. We also prove that the IVT holds for the identity group and all n, and exhibit examples of groups for which the IVT fails to hold for small values of n.     

Average-case results on heapsort

A new algorithm for rearranging a heap is presented and analysed in the average case. The average case upper bound for deleting the maximum element of a random heap is improved, and is shown to be less than [logn]+0.299+M(n) comparisons, *) whereM(n) is between 0 and 1. It is also shown that a heap can be constructed using 1.650n+O(logn) comparisons with this algorithm, the best result for any algorithm which does not use any extra space. The expected time to sortn elements is argued to be less thann logn+0.670n+O(logn), while simulation result points at an average case ofn log n+0.4n which will make it the fastest in-place sorting algorithm. The same technique is used to show that the average number of comparisons when deleting the maximum element of a heap using Williams' algorithm for rearrangement is 2([logn]–1.299+L(n)) whereL(n) also is between 0 and 1, and the average cost for Floyd-Williams Heapsort is at least 2nlogn–3.27n, counting only comparisons. An analysis of the number of interchanges when deleting the maximum element of a random heap, which is the same for both algorithms, is also presented.     

A phase transition phenomenon in a random directed acyclic graph

Let a random directed acyclic graph be defined as being obtained from the random graph G_{n, p} by orienting the edges according to the ordering of vertices. Let γ_n* be the size of the largest (reflexive, transitive) closure of a vertex. For p=c(log n)/n, we prove that, with high probability, γ_n* is asymptotic to n^c log n, 2n(log log n)/log n, and n(1−1/c) depending on whether c<1, c=1, or c>1. We also determine the limiting distribution of the first vertex closure in all three ranges of c. As an application, we show that the expected number of comparable pairs is asymptotic to n^1+c/c log n, ½(n(log log n)/log n)², and ½(n(1−1/c))², respectively. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 164–184, 2001     

Minimum ideal triangulations of hyperbolic 3-manifolds

Let σ(n) be the minimum number of ideal hyperbolic tetrahedra necessary to construct a finite volumen-cusped hyperbolic 3-manifold, orientable or not. Let σ_or(n) be the corresponding number when we restrict ourselves to orientable manifolds. The correct values of σ(n) and σ_or(n) and the corresponding manifolds are given forn=1,2,3,4 and 5. We then show that 2n−1≤σ(n)≤σ_or(n)≤4n−4 forn≥5 and that σ_or(n)≥2n for alln. Both authors were supported by NSF Grants DMS-8711495, DMS-8802266 and Williams College Research Funds.