Note on the heights of random recursive trees and random m-ary search trees

A process of growing a random recursive tree T_n is studied. The sequence {T_n} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of T_n is asymptotic, with probability one, to c log n. In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ)^?1, where γe^1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m-ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union-find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc.     

Anti‐Ramsey numbers of doubly edge‐critical graphs

Given a graph H and a positive integer n, Anti‐Ramsey number AR(n, H) is the maximum number of colors in an edge‐coloring of K_n that contains no polychromatic copy of H. The anti‐Ramsey numbers were introduced in the 1970s by Erd?s, Simonovits, and Sós, who among other things, determined this function for cliques. In general, few exact values of AR(n, H) are known. Let us call a graph H doubly edge‐critical if χ(H?e)≥p+ 1 for each edge e∈E(H) and there exist two edges e₁, e₂ of H for which χ(H?e₁?e₂)=p. Here, we obtain the exact value of AR(n, H) for any doubly edge‐critical H when n?n₀(H) is sufficiently large. A main ingredient of our proof is the stability theorem of Erd?s and Simonovits for the Turán problem. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 210–218, 2009     

On the principles of limiting absorption and limit amplitude for a class of locally perturbed waveguides. Part 2: Time-dependent theory

In part 1

1 Math. meth. in the Appl. Sci, 10, 125–144 (1988).

we studied the principle of limiting absorption for local perturbations Ω of the n-dimensional domain Ω₀ = ?^n?1 × (0, π). In this second part we extend our investigations to the time-dependent theory and show that absence of admissible standing waves implies the validity of the principle of limiting amplitude for every frequency ω≥0 if n ≠ 3 and for ω ≠ 2, 3,… if n = 3, respectively. In particular, the principle of limiting amplitude holds for every ω≥0 in the case n ≠ 3 and for every ω ≠ 2, 3,… in the case n = 3 if Ω≠Ω₀ and ν · x ′ ?0 on ?Ω, where x ′ = (x₁,…, x_n?1, 0) and ν is the normal unit vector on ?Ω pointing into the complement of Ω This result stands in remarkable contrast to the fact that both principles are violated in the case of the unperturbed domain Ω₀ at the frequencies ω = 1, 2,… if n?3. The question of the asymptotic behaviour of the solution as t→∞ for n = 3 and ω = 2, 3,… will be discussed in two subsequent papers.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

Catenarian Property of Mixed Polynomial and Power Series Rings Over a Pullback

Let T be an integral domain with a maximal ideal M, ?: T → K: = T/M the natural surjection, and R the pullback ?^?1(D), where D is a proper subring of K. We give necessary and sufficient conditions for the mixed extensions R[x ₁]]…[x _n ]] to be catenarian, where each [x _i ]] is fixed as either [x _i ] or [[x _i ]]. We also give a complete answer to the question of determining the field extensions k ? K such that the contraction map Spec(K[x ₁]]…[x _n ]]) → Spec(k[x ₁]]…[x _n ]]) is a homeomorphism. As an application, we characterize the globalized pseudo-valuation domains R such that R[x ₁]]…[x _n ]] is catenarian.     

The phase transition in random horn satisfiability and its algorithmic implications

Let c > 0 be a constant, and Φ be a random Horn formula with n variables and m = c · 2ⁿ clauses, chosen uniformly at random (with repetition) from the set of all nonempty Horn clauses in the given variables. By analyzing PUR, a natural implementation of positive unit resolution, we show that lim_n→∞ Pr(Φ is satisfiable) = 1 ? F(e^?c), where F(x) = (1 ? x)(1 ? x²)(1 ? x⁴)(1 ? x⁸) …. Our method also yields as a byproduct an average‐case analysis of this algorithm. Published 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 483–506, 2002     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

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.     

Generalized cartan type k lie algebras in characteristic 0

The Lie algebra of Cartan type K which occurs as a subalgebra of the Lie algebra of derivations of the polynomial algebra F[x₀, x₁,…, x_n,x_n?1,…,x_?n], where F is a field of characteristic 0, was generalized by the first author to a class which included a subalgebra of the derivations of the Laurent polynomials F[x₀,x₁,…, x_n,x_?1,…,x_?n,X₀ ^?1x₁ ^-1,…,x_n ^?1,…,x_?1 ^?1…,x_?n ^?1]A further generalization of these algebras is the main topic of this paper. We show when these algebras are simple, determine all possible     

On the convex hull of the multiform numerical range

Let A ₁,…,A_m be nxn hermitian matrices. Definine

W(A ₁,…,A_m )={(xA₁x ^?,…xA_mx ^?):x?C ⁿ ,xx ^?=1}. We will show that every point in the convex hull of W(A ₁,…,A_m ) can be represented as a convex combination of not more than k(m,n) points in W(A ₁,…,A_m ) where k(m,n)=min{n,[√m]+δ _n ² _m+1}.     

Avoiding a giant component

Let e₁, e′₁; e₂, e′₂;…;e_i, e′_i;??? be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graph K_n (i.e. we sample with replacement). This sequence is used to form a graph by choosing at stage i, i=1,…, one edge from e_i,e′_i to be an edge in the graph, where the choice at stage i is based only on the observation of the edges that have appeared by stage i. We show that these choices can be made so that whp the size of the largest component of the graph formed at stage 0.535n is polylogarithmic in n. This resolves a question of Achlioptas. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 75–85, 2001     

On the Semigroup Algebra of Binary Relations

The semigroup of binary relations on {1,…, n} with the relative product is isomorphic to the semigroup B _n of n × n zero-one matrices with the Boolean matrix product. Over any field F, we prove that the semigroup algebra FB _n contains an ideal K _n of dimension (2 ⁿ  ? 1)², and we construct an explicit isomorphism of K _n with the matrix algebra M _{2 ⁿ ?1}(F).     

Balancing vectors and Gaussian measures of n-dimensional convex bodies

Let ‖·‖ be the Euclidean norm on R ⁿ and γ_n the (standard) Gaussian measure on R ⁿ with density (2π)^−n/2e. It is proved that there is a numerical constant c>0 with the following property: if K is an arbitrary convex body in R ⁿ with γ_n(K)≥1/2, then to each sequence u₁,…,u_m∈ R ⁿ with ‖u₁‖,…,‖u_m‖≤c there correspond signs ε₁,…,ε_m=±1 such that ∑^m_i=1ε_iu_i∈K. This improves the well-known result obtained by Spencer [Trans. Amer. Math. Soc. 289 , 679–705 (1985)] for the n-dimensional cube. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 351–360, 1998     

Depth of Initial Ideals of Normal Edge Rings

Let G be a finite graph on the vertex set [d] = {1,…, d} with the edges e ₁,…, e _n and K[t] = K[t ₁,…, t _d ] the polynomial ring in d variables over a field K. The edge ring of G is the semigroup ring K[G] which is generated by those monomials t ^e  = t _i t _j such that e = {i, j} is an edge of G. Let K[x] = K[x ₁,…, x _n ] be the polynomial ring in n variables over K, and define the surjective homomorphism π: K[x] → K[G] by setting π(x _i ) = t ^{e _i} for i = 1,…, n. The toric ideal I _G of G is the kernel of π. It will be proved that, given integers f and d with 6 ≤ f ≤ d, there exists a finite connected nonbipartite graph G on [d] together with a reverse lexicographic order <_rev on K[x] and a lexicographic order <_lex on K[x] such that (i) K[G] is normal with Krull-dim K[G] = d, (ii) depth K[x]/in_<rev (I _G ) = f and K[x]/in_<lex (I _G ) is Cohen–Macaulay, where in_<rev (I _G ) (resp., in_<lex (I _G )) is the initial ideal of I _G with respect to <_rev (resp., <_lex) and where depth K[x]/in_<rev (I _G ) is the depth of K[x]/in_<rev (I _G ).     

On the Splitting Ring of a Polynomial

Let f(Z) = Zⁿ ? a₁Z^n?1 + … + (?1)^n?1a_n?1Z + (?1)ⁿa_n be a monic polynomial with coefficients in a ring R with identity, not necessarily commutative. We study the ideal I_f of R[X₁,…, X_n] generated by σ_i(X₁,…, X_n) ? a_i, where σ₁,…, σ_n are the elementary symmetric polynomials, as well as the quotient ring R[X₁,…, X_n]/I_f.     

Disjoint skolem sequences and related disjoint structures

A Skolem sequence of order n is a sequence S = (s₁, s₂…, s²ⁿ) of 2n integers satisfying the following conditions: (1) for every k ∈ {1, 2,… n} there exist exactly two elements s_i,S_j such that S_i = S_j = k; (2) If s_i = s_j = k,i < j then j ? i = k. In this article we show the existence of disjoint Skolem, disjoint hooked Skolem, and disjoint near-Skolem sequences. Then we apply these concepts to the existence problems of disjoint cyclic Steiner and Mendelsohn triple systems and the existence of disjoint 1-covering designs. © 1993 John Wiley & Sons, Inc.     

An upper bound for the solvability probability of a random stable roommates instance

It is well-known that not all instances of the stable roommates problem admit a stable matching. Here we establish the first nontrivial upper bound on the limiting behavior of P_n, the probability that a random roommates instance of size n has a stable matching, namely, lim _n→∞ Pn? e^1/2/2 (=0.8244…). © 1994 John Wiley & Sons, Inc.     

On Marcel Riesz's Ultrahyperbolic Kernel

Let t = (t₁, …, t_n) be a point of ?ⁿ. We shall write . We put by definition R_α(u) = u^(α?n)/2/K_n(α); here α is a complex parameter, n the dimension of the space, and K_n(α) is a constant. First we evaluate □R_α(u) = R_α(u), where □ the ultrahyperbolic operator. Then we obtain the following results: R_?2k(u) = □^kδ; R₀(u) = δ; and □^kR_2k(u) = δ, k = 0, 1, …. The first result is the n-dimensional ultrahyperbolic correlative of the well-known one-dimensional formula . Equivalent formulas have been proved by Nozaki by a completely different method. The particular case µ = 1 was solved previously.     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.