On the multiplicity of parts in a random partition

Let λ be a partition of an integer n chosen uniformly at random among all such partitions. Let s(λ) be a part size chosen uniformly at random from the set of all part sizes that occur in λ. We prove that, for every fixed m≥1, the probability that s(λ) has multiplicity m in λ approaches 1/(m(m+1)) as n→∞. Thus, for example, the limiting probability that a random part size in a random partition is unrepeated is 1/2. In addition, (a) for the average number of different part sizes, we refine an asymptotic estimate given by Wilf, (b) we derive an asymptotic estimate of the average number of parts of given multiplicity m, and (c) we show that the expected multiplicity of a randomly chosen part size of a random partition of n is asymptotic to (log n)/2. The proofs of the main result and of (c) use a conditioning device of Fristedt. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 185–197, 1999     

On a class of order pick strategies in paternosters

We study the travel time needed to pick n items in a paternoster, operating under the m-step strategy. This means that the paternoster chooses the shortest route among the ones that change direction at most once, and after collecting at most m items. For random pick positions, we find the distribution and moments of the travel time, provided n>2m. It appears that, already for m=2, the m-step strategy is very close to optimal, and better than the nearest item heuristic.     

The structure and distances in Yule recursive trees

Based on uniform recursive trees, we introduce random trees with the factor of time, which are named Yule recursive trees. The structure and the distance between the vertices in Yule recursive trees are investigated in this paper. For arbitrary time t > 0, we first give the probability that a Yule recursive tree Y_t is isomorphic to a given rooted tree γ; and then prove that the asymptotic distribution of ζ_t,m, the number of the branches of size m, is the Poisson distribution with parameter λ = 1/m. Finally, two types of distance between vertices in Yule recursive trees are studied, and some limit theorems for them are established.© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On a class of extremal problems in statistics

Let m denote the infimum of the Integral of a function q w r t all probability measures with given marginals. The determination of m is of interest for a series of stochastic problems. In the present paper we prove a duality theorem for the determination of m and give some examples for its application. We consider especially the problem of extremal variance of sums of random variables and prove a theorem for the existence of random variables with given marginal distributions, such that their sum has variance zero.     

Sturm Sequences and Random Eigenvalue Distributions

This paper proposes that the study of Sturm sequences is invaluable in the numerical computation and theoretical derivation of eigenvalue distributions of random matrix ensembles. We first explore the use of Sturm sequences to efficiently compute histograms of eigenvalues for symmetric tridiagonal matrices and apply these ideas to random matrix ensembles such as the β-Hermite ensemble. Using our techniques, we reduce the time to compute a histogram of the eigenvalues of such a matrix from O(n ²+m) to O(mn) time where n is the dimension of the matrix and m is the number of bins (with arbitrary bin centers and widths) desired in the histogram (m is usually much smaller than n). Second, we derive analytic formulas in terms of iterated multivariate integrals for the eigenvalue distribution and the largest eigenvalue distribution for arbitrary symmetric tridiagonal random matrix models. As an example of the utility of this approach, we give a derivation of both distributions for the β-Hermite random matrix ensemble (for general β). Third, we explore the relationship between the Sturm sequence of a random matrix and its shooting eigenvectors. We show using Sturm sequences that assuming the eigenvector contains no zeros, the number of sign changes in a shooting eigenvector of parameter λ is equal to the number of eigenvalues greater than λ. Finally, we use the techniques presented in the first section to experimentally demonstrate a O(log n) growth relationship between the variance of histogram bin values and the order of the β-Hermite matrix ensemble. This research was supported by NSF Grant DMS–0411962.     

On some applications of a discrete-time model of failure and repair

Research on a discrete-time model of failure and repair studied by Rocha-Martinez and Shaked (1995) is continued in this paper. Among various related results, we prove that if for one point x∈]0,1[ the probability generating function of a non-negative integer valued random variable S satisfies Φ_S(x)⩽x^m for some integer m⩾0, then E(S)⩾m. We use these results to show that for any M (the ‘input’ lifetime of a unit in the model) the R_m's (the allowed number of repairs on the unit at time m, m⩾0) can be chosen such that M_u (the ‘output’ lifetime of the unit through the model) is in hazard rate ordering (therefore in stochastic ordering) arbitrarily large and such that E(R_m) is a minimum in some sense. As a first application, we see how a low-quality item (car, computer, washing machine, etc.) might fulfil strict durability regulations under an appropriate imperfect repair strategy (and be able to compete against the existing leading brand in the market) in such a way that the mean number of repairs be a minimum in some sense. As a second application we show how it can be easily proven that if M is of class: NBU, NWE, DMRL, IMRL, NBUE or NWUE, then M_u is not necessarily of the same class. © 1998 John Wiley & Sons, Ltd.     

Constructions of nets via OAs of strength 3 with a prescribed property

The idea of (t, m, s)‐nets was proposed by Niederreiter in 1987. Such nets are highly uniform point distributions in s‐dimensional unit cubes and useful in numerical analysis. It is by now well known that (t, m, s)‐nets can be equivalently described in terms of ordered orthogonal arrays (OOAs). In this article, we describe an equivalence between an OOA and an orthogonal array (OA) with all its derived orthogonal subarrays being resolvable. We then present a number of constructions for OAs where all their derived orthogonal subarrays are resolvable. These results are finally combined to give new series of (t, m, s)‐nets. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:144‐155, 2011     

Randomness-optimal oblivious sampling

We present the first efficient oblivious sampler that uses an optimal number of random bits, up to an arbitrary constant factor bigger than 1. Specifically, for any α>0, it uses (1+α)(m+log γ⁻¹) random bits to output d=poly(ϵ⁻¹, log γ⁻¹, m) sample points z₁,…,z_d∈{0, 1}^m such that for any function f: {0, 1}^m→[0, 1], Pr [|(1/d)∑_i=1^df(z_i)− E f|≤ϵ]≥1−γ. Our proof is based on an improved extractor construction. An extractor is a procedure which takes as input the output of a defective random source and a small number of truly random bits, and outputs a nearly random string. We present the first optimal extractor, up to constant factors, for defective random sources with constant entropy rate. We give applications to constructive leader election and reducing randomness in interactive proofs. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 345–367 (1997)     

SIR epidemics on random graphs with a fixed degree sequence

Let Δ > 1 be a fixed positive integer. For \begin{align*}{\textbf{ {z}}} \in \mathbb{R}_+^\Delta\end{align*} let G_z be chosen uniformly at random from the collection of graphs on ∥z∥₁n vertices that have z_in vertices of degree i for i = 1,…,Δ. We determine the likely evolution in continuous time of the SIR model for the spread of an infectious disease on G_z, starting from a single infected node. Either the disease halts after infecting only a small number of nodes, or an epidemic spreads to infect a linear number of nodes. Conditioning on the event that more than a small number of nodes are infected, the epidemic is likely to follow a trajectory given by the solution of an associated system of ordinary differential equations. These results also give the likely number of nodes infected during the course of the epidemic and the likely length in time of the epidemic. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Competing first passage percolation on random graphs with finite variance degrees

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ₁ (λ₂) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ₁ = λ₂, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ₁ ≠ λ₂, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.     

Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation

PS_N is a fast forward permutation if for each m the computational complexity of evaluating P^m(x) is small independently of m and x. Naor and Reingold constructed fast forward pseudorandom cycluses and involutions. By studying the evolution of permutation graphs, we prove that the number of queries needed to distinguish a random cyclus from a random permutation in S_N is Θ(N) if one does not use queries of the form P^m(x), but is only Θ(1) if one is allowed to make such queries. We construct fast forward permutations which are indistinguishable from random permutations even when queries of the form P^m(x) are allowed. This is done by introducing an efficient method to sample the cycle structure of a random permutation, which in turn solves an open problem of Naor and Reingold.     

On the solution‐space geometry of random constraint satisfaction problems

For various random constraint satisfaction problems there is a significant gap between the largest constraint density for which solutions exist and the largest density for which any polynomial time algorithm is known to find solutions. Examples of this phenomenon include random k‐SAT, random graph coloring, and a number of other random constraint satisfaction problems. To understand this gap, we study the structure of the solution space of random k‐SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number of connected components and give quantitative bounds for the diameter, volume, and number.© 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 251–268, 2011     

Sampling contingency tables

We give polynomial time algorithms for random sampling from a set of contingency tables, which is the set of m×n matrices with given row and column sums, provided the row and column sums are sufficiently large with respect to m, n. We use this to approximately count the number of such matrices. These problems are of interest in Statistics and Combinatorics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10 , 487–506, 1997     

Partially 2-colored permutations and the Boros–Moll polynomials

We find a combinatorial setting for the coefficients of the Boros–Moll polynomials P _m (a) in terms of partially 2-colored permutations. Using this model, we give a combinatorial proof of a recurrence relation on the coefficients of P _m (a). This approach enables us to give a combinatorial interpretation of the log-concavity of P _m (a) which was conjectured by Moll and confirmed by Kauers and Paule.     

Continuation of blowup solutions of nonlinear heat equations in several space dimensions

The possible continuation of solutions of the nonlinear heat equation in R^N × R₊ u_t = Δu^m + u^p with m > 0, p > 1, after the blowup time is studied and the different continuation modes are discussed in terms of the exponents m and p. Thus, for m + p ≤ 2 we find a phenomenon of nontrivial continuation where the region {x : u(x, t) = ∞} is bounded and propagates with finite speed. This we call incomplete blowup. For N ≥ 3 and p > m(N + 2)/(N − 2) we find solutions that blow up at finite t = T and then become bounded again for t > T. Otherwise, we find that blowup is complete for a wide class of initial data. In the analysis of the behavior for large p, a list of critical exponents appears whose role is described. We also discuss a number of related problems and equations. We apply the same technique of analysis to the problem of continuation after the onset of extinction, for example, for the equation u_t = Δu^m − u^p, m > 0. We find that no continuation exists if p + m ≤ 0 (complete extinction), and there exists a nontrivial continuation if p + m > 0 (incomplete extinction). © 1997 John Wiley & Sons, Inc.     

Nash equilibria of Cauchy-random zero-sum and coordination matrix games

We consider zero-sum games (A,  − A) and coordination games (A,A), where A is an m-by-n matrix with entries chosen independently with respect to the Cauchy distribution. In each case, we give an exact formula for the expected number of Nash equilibria with a given support size and payoffs in a given range, and also asymptotic simplications for matrices of a fixed shape and increasing size. We carefully compare our results with recent results of McLennan and Berg on Gaussian random bimatrix games (A,B), and describe how the three situations together shed light on random bimatrix games in general.     

A graphon approach to limiting spectral distributions of Wigner‐type matrices

We present a new approach, based on graphon theory, to finding the limiting spectral distributions of general Wigner‐type matrices. This approach determines the moments of the limiting measures and the equations of their Stieltjes transforms explicitly with weaker assumptions on the convergence of variance profiles than previous results. As applications, we give a new proof of the semicircle law for generalized Wigner matrices and determine the limiting spectral distributions for three sparse inhomogeneous random graph models with sparsity ω(1/n): inhomogeneous random graphs with roughly equal expected degrees, W‐random graphs and stochastic block models with a growing number of blocks. Furthermore, we show our theorems can be applied to random Gram matrices with a variance profile for which we can find the limiting spectral distributions under weaker assumptions than previous results.     

Invariance of Milnor numbers and topology of complex polynomials

We give a global version of Lê-Ramanujam μ-constant theorem for polynomials. Let , , be a family of polynomials of n complex variables with isolated singularities, whose coefficients are polynomials in t. We consider the case where some numerical invariants are constant (the affine Milnor number μ(t), the Milnor number at infinity λ(t), the number of critical values, the number of affine critical values, the number of critical values at infinity). Let n=2, we also suppose the degree of the is a constant, then the polynomials and are topologically equivalent. For we suppose that critical values at infinity depend continuously on t, then we prove that the geometric monodromy representations of the are all equivalent. Received: January 14, 2002     

The number of maximum matchings in a tree

We determine upper and lower bounds for the number of maximum matchings (i.e., matchings of maximum cardinality) m(T) of a tree T of given order. While the trees that attain the lower bound are easily characterised, the trees with the largest number of maximum matchings show a very subtle structure. We give a complete characterisation of these trees and derive that the number of maximum matchings in a tree of order n is at most O(1.391664ⁿ) (the precise constant being an algebraic number of degree 14). As a corollary, we improve on a recent result by Górska and Skupień on the number of maximal matchings (maximal with respect to set inclusion).     

On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.