Further results on the enumeration of hamilton paths in Cayley digraphs on semidirect products of cyclic groups

First, let m and n be positive integers such that n is odd and gcd(m,n)=1. Let G be the semidirect product of cyclic groups given by . Then the number of hamilton paths in Cay(G:x,y) (with initial vertex 1) is one fewer than the number of visible lattice points that lie on the closed quadrilateral whose vertices in consecutive order are (0,0), (4mn²+2n,16m²n), (n,4m), and (0,8m). Second, let m and n be positive integers such that n is odd. Let G be the semidirect product of cyclic groups given by . Then the number of hamilton paths in Cay(G:x,y) (with initial vertex 1) is (3m-1)n+m⌊(n+1)/3⌋+1.     

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     

Large induced trees in sparse random graphs

We consider the size of the largest induced tree in random graphs, random regular graphs and random regular digraphs where the average degree is constant. In all cases we show that with probability 1 − o(1), such graphs have induced trees of size order n. In particular, the first result confirms a conjecture of Erdos and Palka (Discrete Math. 46 (1983), 145–150).     

A new algorithm for digraph isomorphism

A new and efficient procedure for testing a pair of digraphs for isomorphism is developed. It is based on conducting a depth-first search on one of the digraphs followed by a systematic matching of edges using backtracking with very effective pruning. It is proved that for digraphs (ofn vertices) the expected time complexity of this procedure isO(n ^logn ). This theoretical result is verified empirically on more than 300 large random digraphs. This procedure is shown to be more efficient than any of the existing general isomorphism procedures.     

The rate of convergence for backwards products of a convergent sequence of finite Markov matrices

Recent papers have shown that Π^∞_{k = 1}P(k) = lim_m→∞ (P(m) ? P(1)) exists whenever the sequence of stochastic matrices {P(k)}^∞_{k = 1} exhibits convergence to an aperiodic matrix P with a single subchain (closed, irreducible set of states). We show how the limit matrix depends upon P(1).In addition, we prove that lim_m→∞lim_n→∞ (P(n + m) ? P(m + 1)) exists and equals the invariant probability matrix associated with P. The convergence rate is determined by the rate of convergence of {P(k)}^∞_{k = 1} towards P.Examples are given which show how these results break down in case the limiting matrix P has multiple subchains, with {P(k)}^∞_{k = 1} approaching the latter at a less than geometric rate.     

Connectivity of the uniform random intersection graph

A uniform random intersection graphG(n,m,k) is a random graph constructed as follows. Label each of n nodes by a randomly chosen set of k distinct colours taken from some finite set of possible colours of size m. Nodes are joined by an edge if and only if some colour appears in both their labels. These graphs arise in the study of the security of wireless sensor networks, in particular when modelling the network graph of the well-known key predistribution technique due to Eschenauer and Gligor.The paper determines the threshold for connectivity of the graph G(n,m,k) when n→∞ in many situations. For example, when k is a function of n such that k≥2 and m=⌊n^α⌋ for some fixed positive real number α then G(n,m,k) is almost surely connected when

lim infk²n/mlogn>1,     

Coloring graphs from random lists of size 2

Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size σ(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring φ such that φ(v)∈L(v) for all v∈V(G). In particular, we show that if g is odd and σ(n)=ω(n^1/(2g−2)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n≥g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if σ(n)=o(n^1/(2g−2)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n), exhibits a sharp threshold at σ(n)=2n.     

When are intermediate processes of the same stochastic order?

Let Z_m⁽ⁿ⁾ represent the mth largest order statistic in a random sample of size n. Here we study the process Z_[mt]⁽ⁿ⁾, t > 0, where m(n) is an intermediate sequence such that m → ∞, m/n → 0 as n → ∞.     

Nash equilibria in random games

We consider Nash equilibria in 2‐player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on m × n payoff matrices, it runs in time O(m²nloglog n + n²mloglog m) with high probability. Our result follows from showing that a 2‐player random game has a Nash equilibrium with supports of size two with high probability, at least 1 − O(1/log n). Our main tool is a polytope formulation of equilibria. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A note on a boundary value problem for linear differential difference equations of mixed type

The statistical theory of linear chain molecules often has rational functions of a few analytic functions as the form of the generating function for the partition function Z⁽ⁿ⁾ of the linear chain molecule, n units long. For applications, it is necessary to know the limiting form of Z⁽ⁿ⁾ as n → ∞. Renewal theory from probability theory is applied to determine this limiting form in important cases.     

Hamilton Cycle Rich 2-Factorization of Complete Equipartite Graphs-II

For any given two 2-factors G and H of a complete p-partite graph K(m, p), with m vertices in each partite set, we prove the existence of a 2-factorization of K(m, p), in which one 2-factor is isomorphic to G, another 2-factor is isomorphic to H and the remaining 2-factors are hamilton cycles. Further, we prove the corresponding result for K(m, p) ? I, where I is a 1-factor of K(m, p), when K(m, p) is an odd regular graph. In fact our results together with the results of McCauley and Rodger settled the problem of 2-factorization of K(m, p), when two of the 2-factors are isomorphic to the given two 2-factors and the remaining 2-factors are hamilton cycles except for (m, p)?=?(m, 2).     

Counting strongly‐connected,moderately sparse directed graphs

A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m ‐ n ? n^2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly‐connected digraphs with parameters m and n among all such digraphs with positive in/out‐degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

A random intersection digraph: Indegree and outdegree distributions

Let S(1),…,S(n),T(1),…,T(n) be random subsets of the set [m]={1,…,m}. We consider the random digraph D on the vertex set [n] defined as follows: the arc i→j is present in D whenever S(i)∩T(j)≠0?. Assuming that the pairs of sets (S(i),T(i)), 1≤i≤n, are independent and identically distributed, we study the in- and outdegree distributions of a typical vertex of D as n,m→∞.     

A note on the connectivity of 2-regular digraphs

Let D ₂(n) be the probability space of 2-regular digraphs on n vertices with the uniform measure. As n tends to infinity, the probability that the digraphs are 2-connected tends to 1. © 1993 John Wiley & Sons, Inc.     

Centroids,Representations, and Submodular Flows

The notion of centroid of a tree is generalized to apply to an arbitrary intersecting family of sets. Centroids are used to construct a compact representation for any intersecting family of sets, as well as any crossing family. The size of the representation for a family on n elements is O(n²), compared to size O(n³) for previous representations. Efficient algorithms to construct the representation are given. For example on a network of n vertices and m edges, the representation of all minimum cuts uses O(m log(n²/m)) space; it is constructed in O(nm log(n²/m)) time (this is the best-known time for finding one minimum cut). The representation is used to improve several submodular flow algorithms. For example a minimum-cost dijoin is found in time O(n²m); as a result a minimum-cost planar feedback are set is found in time O(n³). The previous best-known time bounds for these two problems are both a factor n larger.     

Dynamic point location in arrangements of hyperplanes

We present algorithms for maintaining data structures supporting fast (polylogarithmic) point-location and ray-shooting queries in arrangements of hyperplanes. This data structure allows for deletion and insertion of hyperplanes. Our algorithms use random bits in the construction of the data structure but do not make any assumptions about the update sequence or the hyperplanes in the input. The query bound for our data structure isÕ(polylog(n)), wheren is the number of hyperplanes at any given time, and theÕ notation indicates that the bound holds with high probability, where the probability is solely with respect to randomization in the data structure. By high probability we mean that the probability of error is inversely proportional to a large degree polynomial inn. The space requirement isÕ(n ^d). The cost of update isÕ(n ^d?1 logn. The expected cost of update isO(n ^d?1); the expectation is again solely with respect to randomization in the data structure. Our algorithm is extremely simple. We also give a related algorithm with optimalÕ(logn) query time, expectedO(n ^d) space requirement, and amortizedO(n ^d?1) expected cost of update. Moreover, our approach has a versatile quality which is likely to have further applications to other dynamic algorithms. Ford=2, 3 we also show how to obtain polylogarithmic update time in the CRCW PRAM model so that the processor-time product matches (within a polylogarithmic factor) the sequential update time.     

Level crossing probabilities II: Polygonal recurrence of multidimensional random walks

In part I we proved for an arbitrary one-dimensional random walk with independent increments that the probability of crossing a level at a given time n is O(n−1/2). In higher dimensions we call a random walk ‘polygonally recurrent’ if there is a bounded set, hit by infinitely many of the straight lines between two consecutive sites a.s. The above estimate implies that three-dimensional random walks with independent components are polygonally transient. Similarly a directionally reinforced random walk on Z³ in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239-252] is transient. On the other hand, we construct an example of a transient but polygonally recurrent random walk with independent components on Z².     

Degree sum conditions for oriented forests in digraphs

Let F be an oriented forest with n vertices and m arcs and D be a digraph without loops and multiple arcs. In this note we prove that D contains a subdigraph isomorphic to F if D has at least n vertices and min{d⁺(u)+d⁺(v),d⁻(u)+d⁻(v),d⁺(u)+d⁻(v)}≥2m−1 for every pair of vertices u,v∈V(D) with uv∉A(D). This is a common generalization of two results of Babu and Diwan, one on the existence of forests in graphs under a degree sum condition and the other on the existence of oriented forests in digraphs under a minimum degree condition.     

Pointwise properties of convergence in probability

If a sequence of random variables X_n converges to X in probability we know little about the pointwise behavior X_n(ω). In this note we show that if X_n converges to X quickly enough (for example, like n^?α for α > 0) then, for almost all ω, X_n(ω) converges to X(ω) outside a set of density zero.     

Nonparametric estimation of mixed partial derivatives of a multivariate density

On the basis of a random sample of size n on an m-dimensional random vector X, this note proposes a class of estimators f_n^(p) of f^(p), where f is a density of X w.r.t. a σ-finite measure dominated by the Lebesgue measure on R^m, p = (p₁,…,p_m), p_j ≥ 0, fixed integers, and for x = (x₁,…,x_m) in R^m, f^(p)(x) = ?^p₁+…+p_m f(x)/(?^p₁x₁ … ?^p_mx_m). Asymptotic unbiasedness as well as both almost sure and mean square consistencies of f_n^(p) are examined. Further, a necessary and sufficient condition for uniform asymptotic unbisedness or for uniform mean square consistency of f_n^(p) is given. Finally, applications of estimators of this note to certain statistical problems are pointed out.