Constructive bounds and exact expectations for the random assignment problem

The random assignment problem is to choose a minimum‐cost perfect matching in a complete n×n bipartite graph, whose edge weights are chosen randomly from some distribution such as the exponential distribution with mean 1. In this case it is known that the expectation does not grow unboundedly with n, but approaches some limiting value c* between 1.51 and 2. The limit is conjectured to be π²/6, while a recent conjecture is that for finite n, the expected cost is ∑ 1/i². This paper contains two principal results. First, by defining and analyzing a constructive algorithm, we show that the limiting expectation is c*<1.94. Second, we extend the finite‐n conjecture to partial assignments on complete m×n bipartite graphs and prove it in some limited cases. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 113–144, 1999     

Phase transition for Parking blocks,Brownian excursion and coalescence

In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n < m), and ? = m ? n empty places. For a noncomputer science‐minded reader, we shall use the metaphore of n cars parking on m places: each car c_i chooses a place p_i at random, and if p_i is occupied, c_i tries successively p_i + 1, p_i + 2, until it finds an empty place. Pittel [42] proves that when ?/m goes to some positive limit β < 1, the size B of the largest block of consecutive cars satisfies 2(β ? 1 ? log β)B = 2 log m ? 3 log log m + Ξ_m, where Ξ_m converges weakly to an extreme‐value distribution. In this paper we examine at which level for n a phase transition occurs between B = o(m) and m ? B = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 76–119, 2002     

On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation

We consider the distribution of the length of the longest subsequence avoiding an arbitrary pattern, π, in a random permutation of length n. The well‐studied case of a longest increasing subsequence corresponds to π = 21. We show that there is some constant c_π such that as n →∞ the mean value of this length is asymptotic to and that the distribution of the length is tightly concentrated around its mean. We observe some apparent connections between c_π and the Stanley–Wilf limit of the class of permutations avoiding the pattern π. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Word maps and spectra of random graph lifts

We study here the spectra of random lifts of graphs. Let G be a finite connected graph, and let the infinite tree T be its universal cover space. If λ₁ and ρ are the spectral radii of G and T respectively, then, as shown by Friedman (Graphs Duke Math J 118 (2003), 19–35), in almost every n‐lift H of G, all “new” eigenvalues of H are ≤ O(λ ρ^1/2). Here we improve this bound to O(λ ρ^2/3). It is conjectured in (Friedman, Graphs Duke Math J 118 (2003) 19–35) that the statement holds with the bound ρ + o(1) which, if true, is tight by (Greenberg, PhD thesis, 1995). For G a bouquet with d/2 loops, our arguments yield a simple proof that almost every d‐regular graph has second eigenvalue O(d^2/3). For the bouquet, Friedman (2008). has famously proved the (nearly?) optimal bound of . Central to our work is a new analysis of formal words. Let w be a formal word in letters g,…,g. The word map associated with w maps the permutations σ₁,…,σ_k ∈ S_n to the permutation obtained by replacing for each i, every occurrence of g_i in w by σ_i. We investigate the random variable X that counts the fixed points in this permutation when the σ_i are selected uniformly at random. The analysis of the expectation ??(X) suggests a categorization of formal words which considerably extends the dichotomy of primitive vs. imprimitive words. A major ingredient of a our work is a second categorization of formal words with the same property. We establish some results and make a few conjectures about the relation between the two categorizations. These conjectures suggest a possible approach to (a slightly weaker version of) Friedman's conjecture. As an aside, we obtain a new conceptual and relatively simple proof of a theorem of A. Nica (Nica, Random Struct Algorithms 5 (1994), 703–730), which determines, for every fixed w, the limit distribution (as n →∞) of X. A surprising aspect of this theorem is that the answer depends only on the largest integer d so that w = u^d for some word u. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements

It is known that the joint distribution of the number of nodes of each type of an m‐ary search tree is asymptotically multivariate normal when m ≤ 26. When m ≥ 27, we show the following strong asymptotics of the random vector X_n = ^t(X, … , X), where X denotes the number of nodes containing i ? 1 keys after having introduced n ? 1 keys in the tree: There exist (nonrandom) vectors X, C, and S and random variables ρ and φ such that (X_n ? nX)/n ? ρ(C cos(τ₂log n + φ) + S sin(τ₂log n + φ)) →_n→∞ 0 almost surely and in L²; σ₂ and τ₂ denote the real and imaginary parts of one of the eigenvalues of the transition matrix, having the second greatest real part. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints

We consider a canonical Ramsey type problem. An edge‐coloring of a graph is called m‐good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a properly edge‐colored copy of G, and let g(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = K_t, we have c₁mt²/ln t ≤ f(m, K_t) ≤ c₂mt², and cmt³/ln t ≤ g(m, K_t) ≤ cmt³/ln t, where c₁, c₂, c, c are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Iteratively reweighted least squares minimization for sparse recovery

Under certain conditions (known as the restricted isometry property, or RIP) on the m × N matrix Φ (where m < N), vectors x ∈ ?^N that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from y := Φx even though Φ^?1(y) is typically an (N ? m)—dimensional hyperplane; in addition, x is then equal to the element in Φ^?1(y) of minimal ??₁‐norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining x, as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector w, the element in Φ^?1(y) with smallest ??₂(w)‐norm. If x⁽ⁿ⁾ is the solution at iteration step n, then the new weight w⁽ⁿ⁾ is defined by w := [|x|² + ε]^?1/2, i = 1, …, N, for a decreasing sequence of adaptively defined ε_n; this updated weight is then used to obtain x^{(n + 1)} and the process is repeated. We prove that when Φ satisfies the RIP conditions, the sequence x⁽ⁿ⁾ converges for all y, regardless of whether Φ^?1(y) contains a sparse vector. If there is a sparse vector in Φ^?1(y), then the limit is this sparse vector, and when x⁽ⁿ⁾ is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same algorithm with the “heavier” weight w = [|x|² + ε]^?1+τ/2, i = 1, …, N, where 0 < τ < 1, can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for τ approaching 0. © 2009 Wiley Periodicals, Inc.     

On invariant measures of extensions of Markov transition functions

By using the LITTLEWOOD matrices A_2n we generalize CLARKSON' S inequalities, or equivalently, we determine the norms ‖A_2n: l(L_P) → l(L_P)‖ completely. The result is compared with the norms ‖A_2n: l → l‖, which are calculated implicitly in PIETSCH [6].     

Z-cyclic triplewhist tournaments when the number of players involves primes of the form 8u + 5

When the number of players, v, in a whist tournament, Wh(v), is ≡ 1 (mod 4) the only instances of a Z-cyclic triplewhist tournament, TWh(v), that appear in the literature are for v = 21,29,37. In this study we present Z-cyclic TWh(v) for all v ∈ T = {v = 8u + 5: v is prime, 3 ≤ u ≤ 249}. Additionally, we establish (1) for all v ∈ T there exists a Z-cyclic TWh(vⁿ) for all n ≥ 1, and (2) if v_i ∈ T, i = 1,…,n, there exists a Z-cyclic TWh(v… v) for all ?_i ≥ 1. It is believed that these are the first instances of infinite classes of Z-cyclic TWh(v), v ≡ 1 (mod 4). © 1994 John Wiley & Sons, Inc.     

Graph minors and linkages

Bollobás and Thomason showed that every 22k‐connected graph is k‐linked. Their result used a dense graph minor. In this paper, we investigate the ties between small graph minors and linkages. In particular, we show that a 6‐connected graph with a K minor is 3‐linked. Further, we show that a 7‐connected graph with a K minor is (2,5)‐linked. Finally, we show that a graph of order n and size at least 7n?29 contains a K minor. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 75–91, 2005     

Uniform stability of spectral nonlinear Galerkin methods

This article provides a stability analysis for the backward Euler schemes of time discretization applied to the spatially discrete spectral standard and nonlinear Galerkin approximations of the nonstationary Navier‐Stokes equations with some appropriate assumption of the data (λ, u₀, f). If the backward Euler scheme with the semi‐implicit nonlinear terms is used, the spectral standard and nonlinear Galerkin methods are uniform stable under the time step constraint Δt ≤ (2/λλ₁). Moreover, if the backward Euler scheme with the explicit nonlinear terms is used, the spectral standard and nonlinear Galerkin methods are uniform stable under the time step constraints Δt = O(λ) and Δt = O(λ), respectively, where λ ≤ λ, which shows that the restriction on the time step of the spectral nonlinear Galerkin method is less than that of the spectral standard Galerkin method. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2004     

Total relative displacement of vertex permutations of K

Let α denote a permutation of the n vertices of a connected graph G. Define δ_α(G) to be the number , where the sum is over all the unordered pairs of distinct vertices of G. The number δ_α(G) is called the total relative displacement of α (in G). So, permutation α is an automorphism of G if and only if δ_α(G) = 0. Let π(G) denote the smallest positive value of δ_α(G) among the n! permutations α of the vertices of G. A permutation α for which π(G) = δ_α(G) has been called a near‐automorphism of G [ 2 ]. We determine π(K) and describe permutations α of K for which π(K) = δ_α(K). This is done by transforming the problem into the combinatorial optimization problem of maximizing the sums of the squares of the entries in certain t by t matrices with non–negative integer entries in which the sum of the entries in the ith row and the sum of the entries in the ith column each equal to n_i,1≤i≤t. We prove that for positive integers, n₁≤n₂≤…≤n_t, where t≥2 and n_t≥2, where k₀ is the smallest index for which n = n+1. As a special case, we correct the value of π(K_m,n), for all m and n at least 2, given by Chartrand, Gavlas, and VanderJagt [ 2 ]. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 85–100, 2002     

Slow emergence of the giant component in the growing m‐out graph

Let H be a random graph on n vertices, grown by adding vertices one at a time, joining each new vertex to a uniformly chosen set of m earlier vertices. If edges of H are deleted independently, each being retained with probability p, then there is a “phase transition”. There is a certain critical value p_c of p such that, with high probability, a component of order Θ(n) remains as n → ∞ if and only if p > p_c. Among other results, we obtain the exact value of p_c, which depends on m in a nontrivial way, and show that the phase transition has “infinite order”; in fact, for p = p_c + ?, the largest component has order exp(?Θ(1/ ))n with high probability. Analogous results were proved recently in by Bollobás, Janson, and Riordan [Random Structures Algorithms 26 (2005), 1–36] for a related model in which edges are present independently. The model we study is considerably more difficult to analyze, since the dependence between the edges is very important, affecting the value of p_c, so many new complications arise. In overcoming these complications we make use of the techniques developed by the authors [Internet Math 1 (2003), 1–35] to analyze a very different model. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

The determining number of a Cartesian product

A set S of vertices is a determining set for a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted Det(G), is the size of a smallest determining set. This paper begins by proving that if G=G□?□G is the prime factor decomposition of a connected graph then Det(G)=max{Det(G)}. It then provides upper and lower bounds for the determining number of a Cartesian power of a prime connected graph. Further, this paper shows that Det(Q_n)=?log₂n?+1 which matches the lower bound, and that Det(K)=?log₃(2n+1)?+1 which for all n is within one of the upper bound. The paper concludes by proving that if H is prime and connected, Det(Hⁿ)=Θ(logn). © 2009 Wiley Periodicals, Inc. J Graph Theory     

On the density of 2‐colorable 3‐graphs in which any four points span at most two edges

Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)$. We improve the previously best known lower and upper bounds of 0.25682 and 3/10?ε, respectively, by showing that This implies the following new upper bound for the Turán density of K In order to establish these results we use a combination of the properties of computer‐generated extremal 3‐graphs for small n and an argument based on “super‐saturation”. Our computer results determine the exact values of ex(n, K) for n≤19 and ex₂(n, K) for n≤17, as well as the sets of extremal 3‐graphs for those n. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 105–114, 2010     

The circular chromatic number of the Mycielskian of G

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G) + 1. Chang, Huang, and Zhu [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear] have investigated circular chromatic numbers of Mycielskians for several classes of graphs. In this article, we study circular chromatic numbers of Mycielskians for another class of graphs G. The main result is that χ_c(μ(G)) = χ(μ(G)), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As χ_c(G) = and χ(G) = , consequently, there exist graphs G such that χ_c(G) is as close to χ(G) − 1 as you want, but χ_c(μ(G)) = χ(μ(G)). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 63–71, 1999     

Normal cirulant graphs with noncyclic regular subroups

We prove that any circulant graph of order n with connection set S such that n and the order of ?(S), the subgroup of ? that fixes S set‐wise, are relatively prime, is also a Cayley graph on some noncyclic group, and shows that the converse does not hold in general. In the special case of normal circulants whose order is not divisible by 4, we classify all such graphs that are also Cayley graphs of a noncyclic group, and show that the noncyclic group must be metacyclic, generated by two cyclic groups whose orders are relatively prime. We construct an infinite family of normal circulants whose order is divisible by 4 that are also normal Cayley graphs on dihedral and noncyclic abelian groups. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Entropy Numbers in Weighted Function Spaces and Eigenvalue Distributions of Some Degenerate Pseudodifferential Operators II

This paper is the continuation of [17]. We investigate mapping and spectral properties of pseudodifferential operators of type Ψ with χ χ ? ? and 0 ≤ γ ≤ 1 in the weighted function spaces B (?ⁿ, w(x)) and F (?ⁿ, w(x)) treated in [17]. Furthermore, we study the distribution of eigenvalues and the behaviour of corresponding root spaces for degenerate pseudodifferential operators preferably of type b₂(x) b(x, D) b₁(x), where b₁(x) and b₂(x) are appropriate functions and b(x, D) ? Ψ. Finally, on the basis of the Birman-Schwinger principle, we deal with the “negative spectrum” (bound states) of related symmetric operators in L₂.     

Bounded branching process and and/or tree evaluation

We study the tail distribution of supercritical branching processes for which the number of offspring of an element is bounded. Given a supercritical branching process {Z_n} with a bounded offspring distribution, we derive a tight bound, decaying super-exponentially fast as c increases, on the probability Pr[Z_n > cE(Z_n)], and a similar bound on the probability Pr[Z_n ≤ E(Z_n)/c] under the assumption that each element generates at least two offspring. As an application, we observe that the execution of a canonical algorithm for evaluating uniform AND/OR trees in certain probabilistic models can be viewed as a two-type supercritical branching process with bounded offspring, and show that the execution time of this algorithm is likely to concentrate around its expectation, with a standard deviation of the same order as the expectation.     

Blow‐up rate estimates for a parabolic system with multiple nonlinearities

In this paper, we study the blow‐up behaviors for the solutions of parabolic systems u_t=Δu+δ₁e, v_t=Δv+µ₁u in ?×(0, T) with nonlinear boundary conditions Here δ_i?0, µ_j?0, p_i?0, q_j?0 and at least one of δ_iµ_jp_iq_j>0(i, j=1, 2). We prove that the solutions will blow up in finite time for suitable ‘large’ initial values. The exact blow‐up rates are also obtained. Copyright © 2009 John Wiley & Sons, Ltd.