Patterns in random permutations avoiding the pattern 321

We consider a random permutation drawn from the set of 321 ‐avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by n^{m + ?} where m is the length of σ and ? is the number of blocks in it. The limit is not normal, and can be expressed as a functional of a Brownian excursion.     

Pattern‐avoiding permutations and Brownian excursion part I: Shapes and fluctuations

Permutations that avoid given patterns are among the most classical objects in combinatorics and have strong connections to many fields of mathematics, computer science and biology. In this paper we study the scaling limits of a random permutation avoiding a pattern of length 3 and their relations to Brownian excursion. Exploring this connection to Brownian excursion allows us to strengthen the recent results of Madras and Pehlivan [25] and Miner and Pak [29] as well as to understand many of the interesting phenomena that had previously gone unexplained. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 394–419, 2017     

Explicit Bounds for the Return Probability of Simple Random Walks

We give an exact computation of the second order term in the asymptotic expansion of the return probability, P_2n^d(0,0), of a simple random walk on the d-dimensional cubic lattice. We also give an explicit bound on the remainder. In particular, we show that P_2n^d(0,0) < 2 (d/4n)^d/2 where n M=M(d) is explicitly given.     

Hitting time of a half-line by two-dimensional random walk

We consider the probability that a two-dimensional random walk starting from the origin never returns to the half-line {(x₁,x₂)|x₁0,x₂=0} before time n. It is proved that for aperiodic random walk with mean zero and finite 2+(>2)-th absolute moment, this probability times n^1/4 converges to some positive constant c^* as . We show that c^* is expressed by using the characteristic function of the increment of the random walk. For the simple random walk, this expression gives Mathematics Subject Classification (2000):60G50, 60E10     

The writhe of permutations and random framed knots

We introduce and study the writhe of a permutation, a circular variant of the well‐known inversion number. This simple permutation statistics has several interpretations, which lead to some interesting properties. For a permutation sampled uniformly at random, we study the asymptotics of the writhe, and obtain a non‐Gaussian limit distribution. This work is motivated by the study of random knots. A model for random framed knots is described, which refines the Petaluma model, studied with Hass, Linial, and Nowik (Discrete Comput Geom, 2016). The distribution of the framing in this model is equivalent to the writhe of random permutations. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 121–142, 2017     

On k‐connectivity for a geometric random graph

For n points uniformly randomly distributed on the unit cube in d dimensions, with d≥2, let ρ_n (respectively, σ_n) denote the minimum r at which the graph, obtained by adding an edge between each pair of points distant at most r apart, is k‐connected (respectively, has minimum degree k). Then P[ρ_n=σ_n]→1 as n→∞. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 145–164, 1999     

A recursive construction of t‐wise uniform permutations

We present a recursive construction of a (2t + 1)‐wise uniform set of permutations on 2n objects using a combinatorial design, a t‐wise uniform set of permutations on n objects and a (2t + 1)‐wise uniform set of permutations on n objects. Using the complete design in this procedure gives a t‐wise uniform set of permutations on n objects whose size is at most t²ⁿ, the first non‐trivial construction of an infinite family of t‐wise uniform sets for . If a non‐trivial design with suitable parameters is found, it will imply a corresponding improvement in the construction. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 531–540, 2015     

Generalized loop‐erased random walks and approximate reachability

In this paper we extend the loop‐erased random walk (LERW) to the directed hypergraph setting. We then generalize Wilson's algorithm for uniform sampling of spanning trees to directed hypergraphs. In several special cases, this algorithm perfectly samples spanning hypertrees in expected polynomial time. Our main application is to the reachability problem, also known as the directed all‐terminal network reliability problem. This classical problem is known to be # P‐complete, hence is most likely intractable (Ball and Provan, SIAM J Comput 12 (1983) 777–788). We show that in the case of bi‐directed graphs, a conjectured polynomial bound for the expected running time of the generalized Wilson algorithm implies a FPRAS for approximating reachability. Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 201‐223, 2014     

Probabilistic and combinatorial aspects of the card‐cyclic to random insertion shuffle

Consider a permutation σ ∈ S_n as a deck of cards numbered from 1 to n and laid out in a row, where σ_j denotes the number of the card that is in the j‐th position from the left. We study some probabilistic and combinatorial aspects of the shuffle on S_n defined by removing and then randomly reinserting each of the n cards once, with the removal and reinsertion being performed according to the original left to right order of the cards. The novelty here in this nonstandard shuffle is that every card is removed and reinserted exactly once. The bias that remains turns out to be quite strong and possesses some surprising features. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 362–390, 2015     

Finding blocks and other patterns in a random coloring of ℤ

Let ξ = (ξ_k)_k∈? be i.i.d. with P(ξ_k = 0) = P(ξ_k = 1) = 1/2, and let S: = (S_k) be a symmetric random walk with holding on ?, independent of ξ. We consider the scenery ξ observed along the random walk path S, namely, the process (χ_k := ξ). With high probability, we reconstruct the color and the length of blockⁿ, a block in ξ of length ≥ n close to the origin, given only the observations (χ_k). We find stopping times that stop the random walker with high probability at particular places of the scenery, namely on blockⁿ and in the interval [?3ⁿ,3ⁿ]. Moreover, we reconstruct with high probability a piece of ξ of length of the order 3 around blockⁿ, given only 3 observations collected by the random walker starting on the boundary of blockⁿ. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The asphericity of random 2‐dimensional complexes

We study random 2‐dimensional complexes in the Linial–Meshulam model and prove that for the probability parameter satisfying a random 2‐complex Y contains several pairwise disjoint tetrahedra such that the 2‐complex Z obtained by removing any face from each of these tetrahedra is aspherical. Moreover, we prove that the obtained complex Z satisfies the Whitehead conjecture, i.e. any subcomplex is aspherical. This implies that Y is homotopy equivalent to a wedge where Z is a 2‐dimensional aspherical simplicial complex. We also show that under the assumptions where c > 3 and , the complex Z is genuinely 2‐dimensional and in particular, it has sizable 2‐dimensional homology; it follows that in the indicated range of the probability parameter p the cohomological dimension of the fundamental group of a random 2‐complex equals 2. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 261–273, 2015     

Asymptotic enumeration of sparse 2‐connected graphs

We determine an asymptotic formula for the number of labelled 2‐connected (simple) graphs on n vertices and m edges, provided that m ‐ n →∞ and m = O(nlog n) as n →∞. This is the entire range of m not covered by previous results. The proof involves determining properties of the core and kernel of random graphs with minimum degree at least 2. The case of 2‐edge‐connectedness is treated similarly. We also obtain formulae for the number of 2‐connected graphs with given degree sequence for most (“typical”) sequences. Our main result solves a problem of Wright from 1983. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Near‐automorphisms of paths

The total relative displacement of a permutation f of vertices of a connected graph G is , where the sum is taken over all unordered pairs of distinct vertices of G. Let π(G) denote the smallest positive value of δ_f(G) among the n! permutations f. Aitken [J Combin Theory Series A 87 (1999), 1–21] proved that π(P_n) = 2n ? 4 for the n‐path P_n, which was conjectured by Chartrand et al. [Proceedings of the 1996 Eighth Quadrennial International Conference on Graph Theory, Combinatorics Algorithms, and Applications I, New Issues Press, Kalamazoo, 1999, pp. 181–192]. This article gives a short proof of the result. © 2011 Wiley Periodicals, Inc. J Graph Theory 68:323‐325, 2011     

Hamiltonicity of random graphs produced by 2‐processes

Suppose that a random graph begins with n isolated vertices and evolves by edges being added at random, conditional upon all vertex degrees being at most 2. The final graph is usually 2‐regular, but is not uniformly distributed. Some properties of this final graph are already known, but the asymptotic probability of being a Hamilton cycle was not known. We answer this question along with some related questions about cycles arising in the process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Moments of an exponential functional of random walks and permutations with given descent sets

The exponential functional of simple, symmetric random walks with negative drift is an infinite polynomial Y = 1 + ξ₁ + ξ₁ξ₂ + ξ₁ξ₂ξ₃ + ⋯ of independent and identically distributed non-negative random variables. It has moments that are rational functions of the variables μ _k = E(ξ ^k ) < 1 with universal coefficients. It turns out that such a coefficient is equal to the number of permutations with descent set defined by the multiindex of the coefficient. A recursion enumerates all numbers of permutations with given descent sets in the form of a Pascal-type triangle. This revised version was published online in August 2006 with corrections to the Cover Date.     

The range of once‐reinforced random walk in one dimension

We study once‐reinforced random walk on . For this model, we derive limit results on all moments of its range using Tauberian theory.     

Asymptotics of the transition probabilities of the simple random walk on self-similar graphs

It is shown explicitly how self-similar graphs can be obtained as `blow-up' constructions of finite cell graphs . This yields a larger family of graphs than the graphs obtained by discretising continuous self-similar fractals.

For a class of symmetrically self-similar graphs we study the simple random walk on a cell graph , starting at a vertex of the boundary of . It is proved that the expected number of returns to before hitting another vertex in the boundary coincides with the resistance scaling factor.

Using techniques from complex rational iteration and singularity analysis for Green functions, we compute the asymptotic behaviour of the -step transition probabilities of the simple random walk on the whole graph. The results of Grabner and Woess for the Sierpinski graph are generalised to the class of symmetrically self-similar graphs, and at the same time the error term of the asymptotic expression is improved. Finally, we present a criterion for the occurrence of oscillating phenomena of the -step transition probabilities.

     

Geometry of the uniform infinite half‐planar quadrangulation

We give a new construction of the uniform infinite half‐planar quadrangulation with a general boundary (or UIHPQ), analogous to the construction of the UIPQ presented by Chassaing and Durhuus, which allows us to perform a detailed study of its geometry. We show that the process of distances to the root vertex read along the boundary contour of the UIHPQ evolves as a particularly simple Markov chain and converges to a pair of independent Bessel processes of dimension 5 in the scaling limit. We study the “pencil” of infinite geodesics issued from the root vertex as reported by Curien, Ménard, and Miermont and prove that it induces a decomposition of the UIHPQ into 3 independent submaps. We are also able to prove that balls of large radius around the root are on average 7/9 times as large as those in the UIPQ, both in the UIHPQ and in the UIHPQ with a simple boundary; this fact we use in a companion paper to study self‐avoiding walks on large quadrangulations.     

Quasi‐random hypergraphs revisited

The quasi‐random theory for graphs mainly focuses on a large equivalent class of graph properties each of which can be used as a certificate for randomness. For k ‐graphs (i.e., k ‐uniform hypergraphs), an analogous quasi‐random class contains various equivalent graph properties including the k ‐discrepancy property (bounding the number of edges in the generalized induced subgraph determined by any given (k ‐ 1) ‐graph on the same vertex set) as well as the k ‐deviation property (bounding the occurrences of “octahedron”, a generalization of 4 ‐cycle). In a 1990 paper (Chung, Random Struct Algorithms 1 (1990) 363‐382), a weaker notion of l ‐discrepancy properties for k ‐graphs was introduced for forming a nested chain of quasi‐random classes, but the proof for showing the equivalence of l ‐discrepancy and l ‐deviation, for 2 ≤ l < k, contains an error. An additional parameter is needed in the definition of discrepancy, because of the rich and complex structure in hypergraphs. In this note, we introduce the notion of (l,s) ‐discrepancy for k ‐graphs and prove that the equivalence of the (k,s) ‐discrepancy and the s ‐deviation for 1 ≤ s ≤ k. We remark that this refined notion of discrepancy seems to point to a lattice structure in relating various quasi‐random classes for hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011