Search

Staircase tableaux are combinatorial objects that were first introduced due to a connection with the asymmetric simple exclusion process (ASEP) and Askey-Wilson polynomials. Since their introduction, staircase tableaux have been the object of study in many recent papers. Relevant to this paper, Hitczenko and Janson proved that distribution of parameters on the first diagonal is asymptotically normal. In addition, they conjectured that other diagonals would be asymptotically Poisson. Since then, only the second and the third diagonal were proven to follow the conjecture. This paper builds upon those results to prove the conjecture for the kth diagonal where k is fixed. In particular, we prove that the distribution of the number of α's (β's) on the kth diagonal, k > 1, is asymptotically Poisson with parameter 1/2. In addition, we prove that symbols on the kth diagonal are asymptotically independent and thus, collectively follow the Poisson distribution with parameter 1. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 795–818, 2016

The Erdos-Pósa theorem (1965) states that in each graph G which contains at most k disjoint cycles, there is a 'blocking' set B of at most f(k) vertices such that the graph G - B is acyclic. Robertson and Seymour (1986) give an extension concerning any minor-closed class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} of graphs, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, there is a set B of at most g(k) vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763-775), we showed that, amongst all graphs on vertex set [n] = {1,...,n} which contain at most k disjoint cycles, all but an exponentially small proportion contain a blocking set of just k vertices. In the present paper we build on the previous work, and give an extension concerning any minor-closed graph class \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} with 2-connected excluded minors, as long as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} does not contain all fans (here a 'fan' is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs G on [n] which contain at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, all but an exponentially small proportion contain a set B of k vertices such that G - B is in \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}. (This is not the case when \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document} contains all fans.) For a random graph R sampled uniformly from the graphs on [n] with at most k disjoint excluded minors for \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${\mathcal A}$\end{document}, we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc.

In this paper, we consider a sequence of multibubble solutions u k of the equation (0.1) Δ 0 u k + ρ k (he uk /f M he u k d μ -1)=0 in M, where h is a C 2,β positive function in a compact Riemann surface M, and ρ k is a constant satisfying lim k→+ ∞ ρ k = 8mπ for some positive integer m ≥ 1. We prove among other things that ρ k - 8mπ = 2/m m Σ/j=1h -1 (p k,j )(Δ 0 log h(p k,j ) + 8mπ - 2K(p k,j ))λ k,j e -λk,j + O(e -λk,j ), where p k,j are centers of the bubbles of u k and λ k,j are the local maxima of u k after adding a constant. This yields a uniform bound of solutions as ρ k converges to 8mπ from below provided that Δ 0 log h(p k,j ) + 8mπ - 2K(p k,j ) > 0. It generalizes a previous result, due to Ding, Jost, Li, and Wang [18] and Nolasco and Tarantello [31], which says that any sequence of minimizers u k is uniformly bounded if ρ k 0 for any maximum point p of the sum of 2 log h and the regular part of the Green function, where K is the Gaussian curvature of M. The analytic work of this paper is the first step toward computing the topological degree of (0.1), which was initiated by Li [24].

In previous papers the authors showed that almost all d-regular graphs for d≤3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if and the limiting probability distribution at the threshold is determined when d=3. It is a corollary (in view of results elsewhere) that almost all claw-free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j=o(n2/5). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 128–147, 2001

We consider the problem of sampling independent sets of a graph with maximum degree δ. The weight of each independent set is expressed in terms of a fixed positive parameter λ≤2/(δ−2), where the weight of an independent set σ is λ|σ|. The Glauber dynamics is a simple Markov chain Monte Carlo method for sampling from this distribution. We show fast convergence (in O(n log n) time) of this dynamics. This paper gives the more interesting proof for triangle-free graphs. The proof for arbitrary graphs is given in a companion paper (E. Vigoda, Technical Report TR-99-003, International Computer Institute, Berkeley, CA, 1998). We also prove complementary hardness of approximation results, which show that it is hard to sample from this distribution when λ>c/δ for a constant c≤0. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 229–241, 1999

This paper is devoted to the study of flows associated to non-smooth vector fields. We prove the well-posedness of regular Lagrangian flows associated to vector fields $\mathbf{B}=(\mathbf{B}^1,...,\mathbf{B}^d)\in L^1(\mathbb{R}_+;L^1(\mathbb{R}^d)+L^\infty(\mathbb{R}^d))$ satisfying $ \mathbf{B}^i=\sum_{j=1}^{m}\mathbf{K}_j^i*b_j,$ $b_j\in L^1(\mathbb{R}_+,BV(\mathbb{R}^d))$ and $\operatorname{div}(\mathbf{B})\in L^1(\mathbb{R}_+;L^\infty(\mathbb{R}^d))$ for $d,m\geq 2$, where $(\mathbf{K}_j^i)_{i,j}$ are singular kernels in $\mathbb{R}^d$. Moreover, we also show that there exist an autonomous vector-field $\mathbf{B}\in L^1(\mathbb{R}^2)+L^\infty(\mathbb{R}^2)$ and singular kernels $(\mathbf{K}_j^i)_{i,j}$, singular Radon measures $\mu_{ijk}$ in $\mathbb{R}^2$ satisfying $\partial_{x_k} \mathbf{B}^i=\sum_{j=1}^{m}\mathbf{K}_j^i\star\mu_{ijk}$ in distributional sense for some $m\geq 2$ and for $k,i=1,2$ such that regular Lagrangian flows associated to vector field $\mathbf{B}$ are not unique.

Let Gn, p denote a random graph on n vertices. It is an interesting problem when small cliques arise and what distributions of the number of small cliques may occur. Matroids are natural generalization of graphs; therefore, we can try to investigate maximal flats of a small rank in random matroids. The most studied and most interesting seem to be “random projective geometries” introduced by Kelly and Oxley. Many of the theorems in our paper are based on the results published in a long paper of Barbour, Janson, Karoski, and Ruciski. However, proofs for projective geometries generally are more complicated. © 1995 Wiley Periodicals, Inc.

Orthogonal systems in $\mathrm{L}_2(\mathbb{R})$, once implemented in spectral methods, enjoy a number of important advantages if their differentiation matrix is skew-symmetric and highly structured. Such systems, where the differentiation matrix is skew-symmetric, tridiagonal and irreducible, have been recently fully characterised. In this paper we go a step further, imposing the extra requirement of fast computation: specifically, that the first $N$ coefficients {of the expansion} can be computed to high accuracy in $\mathcal{O}(N\log_2N)$ operations. We consider two settings, one approximating a function $f$ directly in $(-\infty,\infty)$ and the other approximating $[f(x)+f(-x)]/2$ and $[f(x)-f(-x)]/2$ separately in $[0,\infty)$. In each setting we prove that there is a single family, parametrised by $\alpha,\beta > -1$, of orthogonal systems with a skew-symmetric, tridiagonal, irreducible differentiation matrix and whose coefficients can be computed as Jacobi polynomial coefficients of a modified function. The four special cases where $\alpha, \beta= \pm 1/2$ are of particular interest, since coefficients can be computed using fast sine and cosine transforms. Banded, Toeplitz-plus-Hankel multiplication operators are also possible for representing variable coefficients in a spectral method. In Fourier space these orthogonal systems are related to an apparently new generalisation of the Carlitz polynomials.

In this paper, we study the existence of perfect matchings and Hamiltonian cycles in the preferential attachment model. In this model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection with $m$ random vertices selected with probabilities proportional to their current degrees. (Constant $m$ is the only parameter of the model.) We prove that if $m \ge 1{,}260$, then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamiltonian cycle asymptotically almost surely, provided that $m \ge 29{,}500$. One difficulty in the analysis comes from the fact that vertices establish connections only with vertices that are "older" (i.e. are created earlier in the process). However, the main obstacle arises from the fact that edges in the preferential attachment model are not generated independently. In view of that, we also consider a simpler setting---sometimes called uniform attachment---in which vertices are added one by one and each vertex connects to $m$ older vertices selected uniformly at random and independently of all other choices. We first investigate the existence of perfect matchings and Hamiltonian cycles in the uniform attachment model, and then extend the argument to the preferential attachment version., Comment: 29 pages

The standard additive coalescent starting with n particles is a Markov process which owns several combinatorial representations, one by Pitman as a process of coalescent forests, and one by Chassaing & Louchard as the block sizes in a parking scheme. In the coalescent forest representation, some edges are added successively between a random node and a random root. In this paper, we investigate an alternative construction by adding edges between the roots. This construction induces the same process at the level of cluster sizes, but allows one to make numerous connections with some combinatorial and probabilistic models that were not known to be connected with additive coalescent. The variety of the combinatorial objects involved here – size biased percolation, parking scheme in a tree, increasing trees, random cuts of trees – justifies our interests in this Acknowledgement : The research has been supported by ANR-14-CE25-0014 (ANR GRAAL).

Let D(n,p) be the random directed graph on n vertices where each of the n(n-1) possible arcs is present independently with probability p. A celebrated result of Frieze shows that if $p\ge(\log n+\omega(1))/n$ then D(n,p) typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in D(n,p) is typically $n!(p(1+o(1)))^{n}$. We also prove a hitting-time version of this statement, showing that in the random directed graph process, as soon as every vertex has in-/out-degrees at least 1, there are typically $n!(\log n/n(1+o(1)))^{n}$ directed Hamilton cycles.

We prove a conjecture dating back to a 1978 paper of D.R. Musser [11], namely that four random permutations in the symmetric group Sn generate a transitive subgroup with probability for some independent of n, even when an adversary is allowed to conjugate each of the four by a possibly different element of . In other words, the cycle types already guarantee generation of a transitive subgroup; by a well known argument, this implies generation of An or except for probability as . The analysis is closely related to the following random set model. A random set is generated by including each independently with probability . The sumset is formed. Then at most four independent copies of are needed before their mutual intersection is no longer infinite. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 2015

Let f be an edge ordering of Kn: a bijection . For an edge , we call f(e) the label of e. An increasing path in Kn is a simple path (visiting each vertex at most once) such that the label on each edge is greater than the label on the previous edge. We let S(f) be the number of edges in the longest increasing path. Chvatal and Komlos raised the question of estimating m(n): the minimum value of S(f) over all orderings f of Kn. The best known bounds on m(n) are , due respectively to Graham and Kleitman, and to Calderbank, Chung, and Sturtevant. Although the problem is natural, it has seen essentially no progress for three decades. In this paper, we consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, S(f) often takes its maximum possible value of n – 1 (visiting all of the vertices with an increasing Hamiltonian path). We prove that this occurs with probability at least about 1/ e. We also prove that with probability 1- o(1), there is an increasing path of length at least 0.85 n, suggesting that this Hamiltonian (or near-Hamiltonian) phenomenon may hold asymptotically almost surely. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 2015

Let (C1,C′(*)),(C2,C′(*)),…,(C m,C′(*)) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at each step must be made on-line, without backtracking, but may depend on the clauses chosen previously. We show that there exists an on-line choice algorithm in the above process which results whp in a satisfiable 2CNF formula as long as m/n ≤ (1000/999)1/4. This contrasts with the well-known fact that a random m -clause formula constructed without the choice of two clauses at each step is unsatisfiable whp whenever m/n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition to the on-line setting above, we also consider an off-line version in which all m clause-pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For the off-line setting, we show that the two-choice satisfiability threshold for k -SAT for any fixed k coincides with the standard satisfiability threshold for random 2k -SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013

In this paper, we consider a relation between two-parameter and one-parameter transition functions for Markov processes and obtain a very useful result to be regarded as relation theorem. Copyright © 2012 John Wiley & Sons, Ltd.

This paper improves upon best-known guarantees for exact reconstruction of a sparse signal f from a small universal sample of Fourier measurements. The method for reconstruction that has recently gained momentum in the sparse approximation theory is to relax this highly nonconvex problem to a convex problem and then solve it as a linear program. We show that there exists a set of frequencies Ω such that one can exactly reconstruct every r-sparse signal f of length n from its frequencies in Ω, using the convex relaxation, and Ω has size k(r, n) = O(r log(n)·log 2 (r) log(r logn)) = O(r log 4 n ). A random set Ω satisfies this with high probability. This estimate is optimal within the log log n and log 3 r factors. We also give a relatively short argument for a similar problem with k(r, n) ≈ r[12 + 8 log(n/r)] Gaussian measurements. We use methods of geometric functional analysis and probability theory in Banach spaces, which makes our arguments quite short.

In this paper we consider a Hamiltonian H on P_2(R^{2d} ), the set of probability measures with finite quadratic moments on the phase space R^{2d} = R^d × R^d , which is a metric space when endowed with the Wasserstein distance W_2. We study the initial value problem dμ_t/dt+∇·(J_dv_tμ_t ) = 0, where J_d is the canonical symplectic matrix, μ_0 is prescribed, and v_t is a tangent vector to P_2(R^{2d}) at μ_t , belonging to ∂H(μ_t ), the subdifferential of H at μ_t . Two methods for constructing solutions of the evolutive system are provided. The first one concerns only the case where μ_0 is absolutely continuous. It ensures that μ_t remains absolutely continuous and v_t = ∇H(μ_t ) is the element of minimal norm in ∂H(μt ). The second method handles any initial measure μ_0. If we further assume that H is λ-convex, proper, and lowersemicontinuous on P_2(R^{2d} ), we prove that the Hamiltonian is preserved along any solution of our evolutive system, namely H(μ_t ) = H(μ_0).

The decycling number φ(G) of a graph G is the smallest number of vertices which can be removed from G so that the resultant graph contains no cycles. In this paper, we study the decycling numbers of random regular graphs. For a random cubic graph G of order n, we prove that φ(G) = ⌈n/4 + 1/2⌉ holds asymptotically almost surely. This is the result of executing a greedy algorithm for decycling G making use of a randomly chosen Hamilton cycle. For a general random d-regular graph G of order n, where d ≥ 4, we prove that φ(G)/n can be bounded below and above asymptotically almost surely by certain constants b(d) and B(d), depending solely on d, which are determined by solving, respectively, an algebraic equation and a system of differential equations.

We present an analysis of the effect of the last-come-first-served heuristic on a linear probing hash table. We study the behavior of successful searches, assuming searches for all elements of the table are equally likely. It is known that the Robin Hood heuristic achieves minimum variance over all linear probing algorithms. We show that the last-come-first-served heuristic achieves this minimum up to lower-order terms. An accurate analysis of this algorithm is made by introducing a new transform which we call the Diagonal Poisson Transform as it resembles the Poisson Transform. We present important properties of this transform, as well as its application to solve some classes of recurrences, find inverse relations, find asymptotics, and obtain several generalizations of Abel's summation formula. We feel the introduction of this transform is the main contribution of the paper. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 221–255 (1997)

In 1962 Posa conjectured that any graph G of order n and minimum degree at least ⅔ n contains the square of a Hamiltonian cycle. In this paper we prove this conjecture for sufficiently large n. © 1996 John Wiley & Sons, Inc.

This is an addendum to the author's earlier paper “Floer Cohomology of Lagrangian Intersection and Pseudo-Holomorphic Discs, I,” Comm. Pure Appl. Math. 46, 1993, pp. 949–993. The main result of this addendum extends the definition of the Floer cohomology of Lagrangian intersection to the case where the minimal Maslov number is equal to 2. ©1996 John Wiley & Sons, Inc.

This paper is an investigation of the structural properties of random plane-oriented recursive trees and their branches. We begin by an enumeration of these trees and some general properties related to the outdegrees of nodes. Using generalized Polya urn models we study the exact and limiting distributions of the size and the number of leaves in the branches of the tree. The exact distribution for the leaves in the branches is given by formulas involving second-order Eulerian numbers. A martingale central limit theorem for a linear combination of the number of leaves and the number of internal nodes is derived. The distribution of that linear combination is a mixture of normals with a beta distribution as its mixing density. The martingale central limit theorem allows easy determination of the limit laws governing the leaves in the branches. Furthermore, the asymptotic joint distribution of the number of nodes of outdegree 0, 1 and 2 is shown to be trivariate normal. © 1993 John Wiley & Sons, Inc.