Permuting in place: analysis of two stopping rules

Permuting in place has been first analyzed by Knuth. It uses the cycle structure of the permutation. The elements of an array to be permuted are only moved when one sees a cycle leader (smallest element in its cycle). So the essential part of such an algorithm is to test an element i about whether it is a cycle leader.Recently, Keller [Inform. Process. Lett. 81 (2002) 119–125] introduced two stopping rules: “If the last cycle leader has been detected, all elements have been moved, and no further tests are necessary” (heuristic 1), respectively “If only r elements have not been moved, then proceeding along a cycle is only useful for r steps” (heuristic 2).We analyze the average costs of these modifications applied to the standard algorithm of Knuth; they are (n+2)H_n−5n/2−1/2nlogn and respectively ((2n+1)/4)H_(n+1)/2+(1/2)H_2(n+1)/2−(1/2)((n+1)/2−n/2)−(n+1)/2(n/2)logn, as opposed to (n+1)H_n−2nnlogn in the classical case.     

Weakly stable constant mean curvature hypersurfaces

Let M^n be an n-dimensional complete noncompact oriented weakly stable constant mean curvature hypersurface in an （n ＋ 1）-dimensional Riemannian manifold N^n＋1 whose （n - 1）th Ricci curvature satisfying Ric^N（n-1） （n - 1）c. Denote by H and φ the mean curvature and the trace-free second fundamental form of M respectively. If ｜φ｜^2 - （n- 2）√n（n- 1）｜H｜｜φ｜＋ n（2n - 1）（H^2＋ c） 〉 0, then M does not admit nonconstant bounded harmonic functions with finite Dirichlet integral. In particular, if N has bounded geometry and c ＋ H^2 〉 0, then M must have only one end.     

On-line coloringk-colorable graphs

We show that for anyk, there exists an on-line algorithm that will color anyk-colorable graph onn vertices withO(n ^1−1/k! ) colors. This improves the previous best upper bound ofO(nlog^(2k−3) n/log^(2k−4) n) due to Lovász, Saks, and Trotter. In the special casesk=3 andk=4 we obtain on-line algorithms that useO(n ^2/3log^1/3 n) andO(n ^5/6log^1/6 n) colors, respectively.     

Maximum Antichains in Random Subsets of a Finite Set

We consider the random poset (n, p) which is generated by first selecting each subset of [n]={1, …, n} with probability p and then ordering the selected subsets by inclusion. We give asymptotic estimates of the size of the maximum antichain for arbitrary p=p(n). In particular, we prove that if pn/log n→∞, an analogue of Sperner's theorem holds: almost surely the maximum antichain is (to first order) no larger than the antichain which is obtained by selecting all elements of (n, p) with cardinality n/2. This is almost surely not the case if pn=∞.     

LARGEST EIGENVALUE OF A UNICYCLIC MIXED GRAPH

The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ1 (U)=n or λ1 (U)∈ (n ,n 1] are characterized.     

Some divisibilities amongst the terms of linear recurrences

Let (u_n)n≥0 be a non-degenerate linear recurrence sequence of integers. We show that the set of positive integersn such that either ω)(n) orΩ(n) dividesu _n is of asymptotic density zero, where ω(n) and Ω(n) are the numbers of prime and prime power divisors ofn, respectively. The same also holds for the set of positive integersn such that τ(n)u _n , where τ(n) is the number of the positive integer divisors of n, provided thatu _n satisfies some mild technical conditions.     

Localization of small zeros of sine and cosine Fourier transforms of a finite positive nondecreasing function

Let a function f be integrable, positive, and nondecreasing in the interval (0, 1). Then by Polya’s theorem all zeros of the corresponding cosine and sine Fourier transforms are real and simple; in this case positive zeros lie in the intervals (π(n−1/2), π(n+1/2)), (πn, π(n+1)), n ∈ ℕ, respectively. In the case of sine transforms it is required that f cannot be a stepped function with rational discontinuity points. In this paper, zeros of the function with small numbers are included into intervals being proper subsets of the corresponding Polya intervals. A localization of small zeros of the Mittag-Leffler function E _1/2(−z ²; μ), μ ∈ (1, 2) ∪ (2, 3) is obtained as a corollary.     

On the average oscillation of a stack

Evaluating a binary tree in postorder we assume that in one unit of time zero or two nodes are removed from the top of the stack and one node is stored in the stack. The oscillation of the stack can be described by a functionf wheref(t) is the number of nodes in the stack aftert units of time. In this paper we shall first derive several new enumeration results concerning planted plane trees. In the second part we shall prove, that the average number of maxima (MAX-turns) and minima (MIN-turns) of the functionf isn/2 andn/2—1, respectively, provided that all binary trees withn leaves are equally likely. Finally, we shall compute for largen and fixedj the average increase (decrease) of the length of the stack between thej-th MIN-turn and (j+1)-th MAX-turn (between thej-th MAX-turn and thej-th MIN-turn). This result implies that the average oscillation of the stack can be described by the functionf(j)=4√j/π−(−1) ^j +O(1/√j) for largen and fixed turn-numberj.     

The spectrum of path factorization of bipartite multigraphs

LetλK_(m,n)be a bipartite multigraph with two partite sets having m and n vertices, respectively.A P_v-factorization ofλK_(m,n)is a set of edge-disjoint P_v-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).When v is an even number,Ushio,Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P_v-factorization ofλK_(m,n).When v is an odd number,we have proposed a conjecture.Very recently,we have proved that the conjecture is true when v=4k-1.In this paper we shall show that the conjecture is true when v = 4k 1,and then the conjecture is true.That is,we will prove that the necessary and sufficient conditions for the existence of a P_(4k 1)-factorization ofλK_(m,n)are(1)2km≤(2k 1)n,(2)2kn≤(2k 1)m,(3)m n≡0(mod 4k 1),(4)λ(4k 1)mn/[4k(m n)]is an integer.     

Dirac-type conditions for hamiltonian paths and cycles in 3-uniform hypergraphs

A hamiltonian path (cycle) in an n-vertex 3-uniform hypergraph is a (cyclic) ordering of the vertices in which every three consecutive vertices form an edge. For large n, we prove an analog of the celebrated Dirac theorem for graphs: there exists n₀ such that every n-vertex 3-uniform hypergraph H, n?n₀, in which each pair of vertices belongs to at least n/2−1 (⌊n/2⌋) edges, contains a hamiltonian path (cycle, respectively). Both results are easily seen to be optimal.     

N-Widths and Average Widths of Besov Classes in Sobolev Spaces

In this paper, we consider the n-widths and average widths of Besov classes in the usual Sobolev spaces. The weak asymptotic results concerning the Kolmogorov n-widths, the linear n-widths, the Gel＇fand n-widths, in the Sobolev spaces on T^d, and the infinite-dimensional widths and the average widths in the Sobolev spaces on Ra are obtained, respectively.     

The Height of Increasing Trees

Increasing trees have been introduced by Bergeron, Flajolet, and Salvy [1]. This kind of notion covers several well-know classes of random trees like binary search trees, recursive trees, and plane oriented (or heap ordered) trees. We consider the height of increasing trees and prove for several classes of trees (including the above mentioned ones) that the height satisfies EH _n ~ γlogn (for some constant γ > 0) and Var H _n =  O(1) as n → ∞. The methods used are based on generating functions. This research was supported by the Austrian Science Foundation FWF, project S9604, that is part of the Austrian National Research Network "Analytic Combinatorics and Probabilistic Number Theory".     

Singularity of orbital measures in SU(n)

We show that the minimalk such that μ^κ ∈L ¹(SU(n)) for all central, continuous measures μ on SU(n) isk=n. We do this by exhibiting an elementg∈SU(n) for which the (n−1)-fold product of its conjugacy class has zero Haar measure. This ensures that if μ _g is the corresponding orbital measure supported on the conjugacy class, then μ _g ^n-1 is singular toL ¹. This research is supported in part by NSERC. The hospitality of the University of Waterloo is gratefully acknowledged.     

The chromatic number of the product of two 4-chromatic graphs is 4

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. This research was supported by NSERC grant A7213     

Lattices of Order-Convex Sets of Forests

We give a characterization of the class Co(F)\mathbf{Co}(\mathcal{F}) [Co(F_n)\mathrm{\mathbf{Co}}(\mathcal{F}_n), n < ω, respectively] of lattices isomorphic to convexity lattices of posets which are forests [forests of length at most n, respectively], as well as of the class Co(L)\mathbf{Co}(\mathcal{L}) of lattices isomorphic to convexity lattices of linearly ordered posets. This characterization yields that the class of finite members from Co(F)\mathbf{Co}(\mathcal{F}) [from Co(F_n)\mathbf{Co}(\mathcal{F}_n), n < ω, or from Co(L)\mathbf{Co}(\mathcal{L})] is finitely axiomatizable within the class of finite lattices.     

Restricted Fault Diameter of Hypercube Networks

This paper studies restricted fault diameter of the n-dimensional hypercube networks Qn (n ≥ 2).It is shown that for arbitrary two vertices x and y with the distance d in Qn and any set F with at most 2n-3 vertices in Qn - {x, y}, if F contains neither of neighbor-sets of x and y in Qn, then the distance between x andy in Qn - F is given by D(Qn-F;x,y){=1 , for=1;≤d 4 , for 2≤d≤n-2,n≥4;≤n 1, for d=n-1,n≥3; =n, for d=n. Furthermore, the upper bounds are tight. As an immediately consequence, Qn can tolerate up to 2n-3 vertices failures and remain diameter 4 if n = 3 and n 2 if n ≥ 4 provided that for each vertex x in Qn, all the neighbors of x do not fail at the same time. This improves Esfahanian‘s result.     

Factorization for non-nevanlinna classes of analytic functions

A generalization of the Blaschke product is constructed. This product enables one to factor out the zeros of the members of certain non-Nevanlinna classes of functions analytic in the unit disc, so that the remaining (non-vanishing) functions still belong to the same class. This is done for the classesA ⁻ⁿ (0<n<∞) andB ⁻ⁿ (0<n<2) defined as follows:f ∈A ⁻ⁿ iff |f(z)|≦C _f (1−|z|)⁻ⁿ ,f ∈B ⁻ⁿ iff |f(z)|≦exp {C _f (1−|z|)⁻ⁿ }, whereC _f depends onf.     

On the projection and macphail constants ofl n p spaces

We prove that the projection and Macphail constants ofl _n ^p (1≦p≦2) are asymptotically equivalent ton ^1/2 andn ^−1/2 respectively. We also obtain some relations linking certain parameters of general finite dimensional real Banach spaces. This note is a part of the author’s Ph.D. Thesis prepared at the Hebrew University of Jerusalem, under the supervision of Prof. J. Lindenstrauss, to whom the author wishes to express his thanks and appreciation.     

On weighted positivity and the Wiener regularity of a boundary point for the fractional Laplacian

A sufficient condition for the Wiener regularity of a boundary point with respect to the operator (− Δ)^μ inR ⁿ ,n≥1, is obtained, for μ∈(0,1/2n)/(1,1/2n−1). This extends some results for the polyharmonic operator obtained by Maz'ya and Maz'ya-Donchev. As in the polyharmonic case, the proof is based on a weighted positivity property of (− Δ)^μ, where the weight is a fundamental solution of this operator. It is shown that this property holds for μ as above while there is an interval [A _n , 1/2n−A _n ], whereA _n →1, asn→∞, with μ-values for which the property does not hold. This interval is non-empty forn≥8.     

On Continuity of the Pearson Statistic and Sample Quantiles

Convergence with probability one (in probability) of sequences of the sample quantiles and the Pearson statistic that are formed by columns of N× n arrays of random variables and bivariate random vectors respectively is established, n→ ∞. Two applications for the continuity of the Pearson statistics, when sampling is only possible along a sequence converging to an inaccessible targeting value, are presented