BZPEER

preprint2022arXiv

Random increasing plane trees: asymptotic enumeration of vertices by distance from leaves

We prove that for any fixed $k$ , the probability that a random vertex of a random increasing plane tree is of rank $k$ , that is, the probability that a random vertex is at distance $k$ from the leaves, converges to a constant $c_k$ as the size $n$ of the tree goes to infinity. {\color{blue} We prove that $1-\sum_{j\le k} c_k<\tfrac{3^{k+1}}{(2k+1)!}$ , so that the tail of the limiting rank distribution is super-exponentially narrow. We prove that the latter property holds uniformly for all finite $n$ as well.} More generally, we prove that the ranks of a finite uniformly random set of vertices are asymptotically independent, each with distribution $\{c_k\}$ . We compute the exact value of $c_k$ for $0\leq k\leq 3$ , demonstrating that the limiting expected fraction of vertices with rank $\le 3$ is $0.9997\dots$ . We show that with probability $1-n^{-0.99\eps}$ the highest rank of a vertex in the tree is sandwiched between $(1-\eps)\log n /\log\log n$ and $(1.5+\eps)\log n/\log\log n$, {\color{blue} and that this rank is asymptotic to $\log n/\log\log n$ with probability $1-o(1)$ .}

preprint2020arXiv

One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences

For a two-sided ( $n$ men/ $n$ women) stable matching problem) Gale and Shapley studied a proposal algorithm (men propose/women select, or the other way around), that determines a matching, not blocked by any unmatched pair. Irving used this algorithm as a first phase of his algorithm for one-sided (stable roommates) matching problem with $n$ agents. We analyze a fully extended version of Irving's proposal algorithm that runs all the way until either each agent holds a proposal or an agent gets rejected by everybody on the agent's preference list. It is shown that the terminal, directed, partnerships form a stable permutation with matched pairs remaining matched in any other stable permutation. A likely behavior of the proposal algorithm is studied under assumption that all $n$ rankings are independently uniform. It is proved that with high probability (w.h.p.) every agent has a partner, and that both the number of agents in cycles of length $\ge 3$ and the total number of stable matchings are bounded in probability. W.h.p. the total number of proposals is asymptotic to $0.5 n^{3/2}$ .

preprint2016arXiv

Birth of a giant $(k_1,k_2)$ -core in the random digraph

The $(k_1,k_2)$ -core of a digraph is the largest sub-digraph with minimum in-degree and minimum out-degree at least $k_1$ and $k_2$ respectively. For $\max\{k_1, k_2\} \geq 2$ , we establish existence of the threshold edge-density $c^*=c^*(k_1,k_2)$ , such that the random digraph $D(n,m)$ , on the vertex set $[n]$ with $m$ edges, asymptotically almost surely has a giant $(k_1,k_2)$ -core if $m/n> c^*$ , and has no $(k_1,k_2)$ -core if $m/n<c^*$ . Specifically, denoting $\text{P}(\text{Poisson}(z)\ge k)$ by $p_k(z)$ , we prove that $c^*=\min\limits_{z_1,z_2}\max\left\{\tfrac{z_1}{p_{k_1}(z_1)p_{k_2-1}(z_2)}; \tfrac{z_2}{p_{k_1-1}(z_1)p_{k_2}(z_2)}\right\}$ .

preprint2016arXiv

Counting strongly connected $(k_1,k_2)$ -directed cores

Consider the set of all digraphs on $[N]$ with $M$ edges, whose minimum in-degree and minimum out-degree are at least $k_1$ and $k_2$ respectively. For $k:=\min\{k_1,k_2\}\ge 2$ and $M/N>\max\{k_1,k_2\}$ , $M=Θ(N)$ , we show that, among those digraphs, the fraction of $k$ -strongly connected digraphs is $1-O\bigl(N^{-(k-1)})$ . Earlier with Dan Poole we identified a sharp edge-density threshold $c^*(k_1,k_2)$ for birth of a giant $(k_1,k_2)$ -core in the random digraph $D(n,m=[cn])$ . Combining the claims, for $c>c^*(k_1,k_2)$ with probability $1-O\bigl(N^{-(k-1)})$ the giant $(k_1,k_2)$ -core exists and is $k$ -strongly connected.

preprint2016arXiv

On the cycle structure of the product of random maximal cycles

The subject of this paper is the cycle structure of the random permutation $σ$ of $[N]$ , which is the product of $k$ independent random cycles of maximal length $N$ . We use the character-based Fourier transform to study the number of cycles of $σ$ and also the distribution of the elements of the subset $[\ell]$ among the cycles of $σ$ .

preprint2015arXiv

Another proof of Harer-Zagier formula

For a regular $2n$ -gon there are $(2n-1)!!$ ways to match and glue the $2n$ sides. The Harer-Zagier bivariate generating function enumerates the gluings by $n$ and the genus $g$ of the attendant surface and leads to a recurrence equation for the counts of gluings with parameters $n$ and $g$ . This formula was originally obtained by using the multidimensional Gaussian integrals. Soon after Jackson and later Zagier found alternative proofs that used the symmetric group characters. In this note we give a different, characters-based, proof. Its core is computing and marginally inverting Fourier transform of the underlying probability measure on $S_{2n}$ . Aside from Murnaghan-Nakayama rule for one-hook diagrams, the counting techniques we use are of elementary, combinatorial nature.

preprint2015arXiv

Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs

Two models of a random digraph on $n$ vertices, $D(n,\text{Prob}(\text{arc})=p)$ and $D(n,\text{number of arcs}=m)$ are studied. In 1990, Karp for $D(n,p)$ and independently T. Łuczak for $D(n,m=cn)$ proved that for $c>1$ , with probability tending to 1, there is an unique strong component of size of order $n$ . Karp showed, in fact, that the giant component has likely size asymptotic to $nθ^2$ , where $θ=θ(c)$ is the unique positive root of $1-θ=e^{-c θ}$ . In this paper we prove that, for both random digraphs, the joint distribution of the number of vertices and number of arcs in the giant strong component is asymptotically Gaussian with the same mean vector $n\boldsymbolμ(c)$ , $\boldsymbolμ(c):=(θ^2, cθ^2)$ and two distinct $2\times 2$ covariance matrices, $n\mathbf{B}(c)$ and $n[\mathbf{B}(c)+c (\boldsymbolμ'(c))^T (\boldsymbolμ'(c)))]$ . To this end, we introduce and analyze a randomized deletion process which determines the directed $(1,1)$ -core, the maximal digraph with minimum in-degree and out-degree at least 1. This $(1,1)$ -core contains all non-trivial strong components. However, we show that the likely numbers of peripheral vertices and arcs in the $(1,1)$ -core, those outside the largest strong component, are of log-polynomial order, thus dwarfed by anticipated fluctuations, on the scale of $n^{1/2}$ , of the giant component parameters. By approximating the likely realization of the deletion algorithm with a deterministic trajectory, we obtain our main result via exponential supermartingales and Fourier-based techniques.

preprint2015arXiv

On a random search tree: asymptotic enumeration of vertices by distance from leaves

A random binary search tree grown from the uniformly random permutation of $[n]$ is studied. We analyze the exact and asymptotic counts of vertices by rank, the distance from the set of leaves. The asymptotic fraction $c_k$ of vertices of a fixed rank $k\ge 0$ is shown to decay exponentially with $k$ . Notoriously hard to compute, the exact fractions $c_k$ had been determined for $k\le 3$ only. We computed $c_4$ and $c_5$ as well; both are ratios of enormous integers, denominator of $c_5$ being $274$ digits long. Prompted by the data, we proved that, in sharp contrast, the largest prime divisor of $c_k$ 's denominator is $2^{k+1}+1$ at most. We conjecture that, in fact, the prime divisors of every denominator for $k>1$ form a single interval, from $2$ to the largest prime not exceeding $2^{k+1}+1$ .

preprint2015arXiv

On a surface formed by randomly gluing together polygonal discs

Starting with a collection of $n$ oriented polygonal discs, with an even number $N$ of sides in total, we generate a random oriented surface by randomly matching the sides of discs and properly gluing them together. Encoding the surface in a random permutation $γ$ of $[N]$ , we use the Fourier transform on $S_N$ to show that $γ$ is asymptotic to the permutation distributed uniformly on the alternating group $A_N$ ( $A_N^c$ resp.) if $N-n$ and $N/2$ are of the same (opposite resp.) parity. We use this to prove a local central limit theorem for the number of vertices on the surface, whence for its Euler characteristic $χ$ . We also show that with high probability the random surface consists of a single component, and thus has a well-defined genus $g=1-χ/2$ , which is asymptotic to a Gaussian random variable, with mean $(N/2-n-\log N)/2$ and variance $(\log N)/2$ .

preprint2014arXiv

Distance between two random k-out digraphs, with and without preferential attachment

A random k-out mapping (digraph) on [n] is generated by choosing k random images of each vertex one at a time, subject to a "preferential attachment" rule: the current vertex selects an image i with probability proportional to a given parameter α= α(n) plus the number of times i has already been selected. Intuitively, the larger αgets, the closer the resulting k-out mapping is to the uniformly random k-out mapping. We prove that α= Θ(n^{1/2}) is the threshold for αgrowing "fast enough" to make the random digraph approach the uniformly random digraph in terms of the total variation distance. We also determine an exact limit for this distance for α= βn^{1/2}.

preprint2014arXiv

Formation of a giant component in the intersection graph of a random chord diagram

We study the number of chords and the number of crossings in the largest component of a random chord diagram when the chords are sparsely crossing. This is equivalent to studying the number of vertices and the number of edges in the largest component of the random intersection graph. Denoting the number of chords by n and the number of crossings by m, when m/nlog(n) tends to a limit in (0,2/π^2), we show that the chord diagram chosen uniformly at random from all the diagrams with given parameters has a component containing almost all the crossings and a positive fraction of chords. On the other hand, when m < n/14, the size of the largest component is of size O(log n). One of the key analytical ingredients is an asymptotic expression for the number of chord diagrams with parameters n and m for m <(2/π^2)n\log(n), based on the Touchard-Riordan formula and the Jacobi identity for Euler partition function.

preprint2014arXiv

The Satisfiability Threshold for k-XORSAT

We consider "unconstrained" random $k$ -XORSAT, which is a uniformly random system of $m$ linear non-homogeneous equations in $\mathbb{F}_2$ over $n$ variables, each equation containing $k \geq 3$ variables, and also consider a "constrained" model where every variable appears in at least two equations. Dubois and Mandler proved that $m/n=1$ is a sharp threshold for satisfiability of constrained 3-XORSAT, and analyzed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT. We show that $m/n=1$ remains a sharp threshold for satisfiability of constrained $k$ -XORSAT for every $k\ge 3$ , and we use standard results on the 2-core of a random $k$ -uniform hypergraph to extend this result to find the threshold for unconstrained $k$ -XORSAT. For constrained $k$ -XORSAT we narrow the phase transition window, showing that $m-n \to -\infty$ implies almost-sure satisfiability, while $m-n \to +\infty$ implies almost-sure unsatisfiability.

preprint2013arXiv

Inside the critical window for cohomology of random k-complexes

We prove sharper versions of theorems of Linial-Meshulam and Meshulam-Wallach which describe the behavior for (Z/2)-cohomology of a random k-dimensional simplicial complex within a narrow transition window. In particular, we show that within this window the (k-1)st Betti number is in the limit Poisson distributed. For k=2 we also prove that in an accompanying growth process, with high probability, first cohomology vanishes exactly at the moment when the last isolated (k-1)-simplex gets covered by a k-simplex.

preprint2013arXiv

On the connected components of a random permutation graph with a given number of edges

A permutation of [n] induces a graph on [n] such that the edges of the graph correspond to inversion pairs of the permutation. This graph is connected if and only if the corresponding permutation is indecomposable. Let s(n,m) denote a permutation chosen uniformly at random among all permutations of [n] with exactly m inversions. Let p(n,m) be the common value for the probabilities that s(n,m) is indecomposable or the corresponding graph is connected. We prove that p(n,m) is non-decreasing with m by constructing a Markov process in which s(n,m+1) is obtained from s(n,m) by increasing one of the components of the inversion sequence of s(n,m) by one. We show that, with probability approaching 1, the graph corresponding to s(n,m) becomes connected for m asymptotic to (6/(π^2))nln(n). More precisely, for m=(6n/(π^2)) [ln(n)+ lnln(n)/2+ ln(12)- ln(π)- 12/(π^2)+x_n], where |x_n|=o(lnlnln(n)), the number of components of the random graph is shown to be asymptotically 1+Poisson(e^{-x_n}). When x_n goes to negative infinity, the sizes of the largest and the smallest components, scaled by n, are asymptotic to the lengths of the largest and the smallest subintervals in a partition of [0,1] by [e^{-x_n}] randomly, and independently, scattered points.

preprint2013arXiv

The Satisfiability Threshold for $k$ -XORSAT, using an alternative proof

We consider "unconstrained" random $k$ -XORSAT, which is a uniformly random system of $m$ linear non-homogeneous equations in $\mathbb{F}_2$ over $n$ variables, each equation containing $k \ge 3$ variables, and also consider a "constrained" model where every variable appears in at least two equations. Dubois and Mandler proved that $m/n=1$ is a sharp threshold for satisfiability of constrained 3-XORSAT, and analyzed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT. We show that $m/n=1$ remains a sharp threshold for satisfiability of constrained $k$ -XORSAT for every $k \ge 3$ , and we use standard results on the 2-core of a random $k$ -uniform hypergraph to extend this result to find the threshold for unconstrained $k$ -XORSAT. For constrained $k$ -XORSAT we narrow the phase transition window, showing that $n-m \to \infty$ implies almost-sure satisfiability, while $m-n \to \infty$ implies almost-sure unsatisfiability.

preprint2011arXiv

On a sparse random graph with minimum degree {three}: Likely Posa's sets are large

We consider the likely size of the endpoint sets produced by Posa rotations, when applied to a longest path in a random graph with $cn,\,c\geq 2.7$ edges that is conditioned to have minimum degree at least three.

preprint2011arXiv

The genus of a random chord diagram is asymptotically normal

Let $G_n$ be the genus of a two-dimensional surface obtained by gluing, uniformly at random, the sides of an $n$ -gon. Recently Linial and Nowik proved, via an enumerational formula due to Harer and Zagier, that the expected value of $G_n$ is asymptotic to $(n - \ln n)/2$ for $n\to\infty$ . We prove a local limit theorem for the distribution of $G_n$ , which implies that $G_n$ is asymptotically Gaussian, with mean $(n-\ln n)/2$ and variance $(\ln n)/4$ .

preprint2010arXiv

Counting strongly-connected, sparsely edged directed graphs

A sharp asymptotic formula for the number of strongly connected digraphs on $n$ labelled vertices with $m$ arcs, under a condition $m-n\to\infty$ , $m=O(n)$ , is obtained; this solves a problem posed by Wright back in $1977$ . Our 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 via counting two-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.

preprint2010arXiv

How frequently is a system of 2-linear Boolean equations solvable?

We consider a random system of equations $x_i+x_j=b_{(i,j)} (\text{mod }2)$ , $(x_u\in \{0,1\},\, b_{(u,v)}=b_{(v,u)}\in\{0,1\})$ , with the pairs $(i,j)$ from $E$ , a symmetric subset of $[n]\times [n]$ . $E$ is chosen uniformly at random among all such subsets of a given cardinality $m$ ; alternatively $(i,j)\in E$ with a given probability $p$ , independently of all other pairs. Also, given $E$ , $\pr\{b_{e}=0\}=\pr\{b_e=1\}$ for each $e\in E$ , independently of all other $b_{e^\prime}$ . It is well known that, as $m$ passes through $n/2$ ( $p$ passes through $1/n$ , resp.), the underlying random graph $G(n,\#\text{edges}=m)$ , ($G(n,\pr(\text{edge})=p)$, resp.) undergoes a rapid transition, from essentially a forest of many small trees to a graph with one large, multicyclic, component in a sea of small tree components. We should expect then that the solvability probability decreases precipitously in the vicinity of $m\sim n/2$ ( $p\sim 1/n$ ), and indeed this probability is of order $(1-2m/n)^{1/4}$ , for $m<n/2$ ( $(1-pn)^{1/4}$ , for $p<1/n$ , resp.). We show that in a near-critical phase $m=(n/2)(1+\la n^{-1/3})$ ($p=(1+\la n^{-1/3})/n$, resp.), $\la=o(n^{1/12})$, the system is solvable with probability asymptotic to $c(\la)n^{-1/12}$, for some explicit function $c(\la)>0$. Mike Molloy noticed that the Boolean system with $b_e\equiv 1$ is solvable iff the underlying graph is $2$ -colorable, and asked whether this connection might be used to determine an order of probability of $2$ -colorability in the near-critical case. We answer Mike's question affirmatively and show that probability of $2$ -colorability is $\lesssim 2^{-1/4}e^{1/8}c(λ)n^{-1/12}$ , and asymptotic to $2^{-1/4}e^{1/8}c(\la)n^{-1/12}$ at a critical phase $\la=O(1)$, and for $\la\to -\infty$. (Submitted to Electronic Journal of Combinatorics on September 7, 2009.)

preprint2010arXiv

Tight Markov chains and random compositions

For an ergodic Markov chain $\{X(t)\}$ on $\Bbb N$ , with a stationary distribution $π$ , let $T_n>0$ denote a hitting time for $[n]^c$ , and let $X_n=X(T_n)$ . Around 2005 Guy Louchard popularized a conjecture that, for $n\to \infty$ , $T_n$ is almost Geometric( $p$ ), $p=π([n]^c)$ , $X_n$ is almost stationarily distributed on $[n]^c$ , and that $X_n$ and $T_n$ are almost independent, if $p(n):=\sup_ip(i,[n]^c)\to 0$ exponentially fast. For the chains with $p(n) \to 0$ however slowly, and with $\sup_{i,j}\,\|p(i,\cdot)-p(j,\cdot)\|_{TV}<1$ , we show that Louchard's conjecture is indeed true even for the hits of an arbitrary $S_n\subset\Bbb N$ with $π(S_n)\to 0$ . More precisely, a sequence of $k$ consecutive hit locations paired with the time elapsed since a previous hit (for the first hit, since the starting moment) is approximated, within a total variation distance of order $k\,\sup_ip(i,S_n)$ , by a $k$ -long sequence of independent copies of $(\ell_n,t_n)$ , where $\ell_n= \text{Geometric}\,(π(S_n))$ , $t_n$ is distributed stationarily on $S_n$ , and $\ell_n$ is independent of $t_n$ . The two conditions are easily met by the Markov chains that arose in Louchard's studies as likely sharp approximations of two random compositions of a large integer $ν$ , a column-convex animal (cca) composition and a Carlitz (C) composition. We show that this approximation is indeed very sharp for most of the parts of the random compositions. Combining the two approximations in a tandem, we are able to determine the limiting distributions of $μ=o(\lnν)$ and $μ=o(ν^{1/2})$ largest parts of the random cca composition and the random C-composition, respectively. (Submitted to Annals of Probability in August, 2009.)

Boris Pittel

Research overview

Is this your work?

20 publications

Random increasing plane trees: asymptotic enumeration of vertices by distance from leaves

One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences

Birth of a giant $(k_1,k_2)$ -core in the random digraph

Counting strongly connected $(k_1,k_2)$ -directed cores

On the cycle structure of the product of random maximal cycles

Another proof of Harer-Zagier formula

Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs

On a random search tree: asymptotic enumeration of vertices by distance from leaves

On a surface formed by randomly gluing together polygonal discs

Distance between two random k-out digraphs, with and without preferential attachment

Formation of a giant component in the intersection graph of a random chord diagram

The Satisfiability Threshold for k-XORSAT

Inside the critical window for cohomology of random k-complexes

On the connected components of a random permutation graph with a given number of edges

The Satisfiability Threshold for $k$ -XORSAT, using an alternative proof

On a sparse random graph with minimum degree {three}: Likely Posa's sets are large

The genus of a random chord diagram is asymptotically normal

Counting strongly-connected, sparsely edged directed graphs

How frequently is a system of 2-linear Boolean equations solvable?

Tight Markov chains and random compositions

See the researcher in context

Building this map preview

Boris Pittel

Research overview

Is this your work?

20 publications

Random increasing plane trees: asymptotic enumeration of vertices by distance from leaves

One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences

Birth of a giant (k1,k2)(k_1,k_2)(k1​,k2​)-core in the random digraph

Counting strongly connected (k1,k2)(k_1,k_2)(k1​,k2​)-directed cores

On the cycle structure of the product of random maximal cycles

Another proof of Harer-Zagier formula

Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs

On a random search tree: asymptotic enumeration of vertices by distance from leaves

On a surface formed by randomly gluing together polygonal discs

Distance between two random k-out digraphs, with and without preferential attachment

Formation of a giant component in the intersection graph of a random chord diagram

The Satisfiability Threshold for k-XORSAT

Inside the critical window for cohomology of random k-complexes

On the connected components of a random permutation graph with a given number of edges

The Satisfiability Threshold for kkk-XORSAT, using an alternative proof

On a sparse random graph with minimum degree {three}: Likely Posa's sets are large

The genus of a random chord diagram is asymptotically normal

Counting strongly-connected, sparsely edged directed graphs

How frequently is a system of 2-linear Boolean equations solvable?

Tight Markov chains and random compositions

See the researcher in context

Building this map preview

Birth of a giant $(k_1,k_2)$ -core in the random digraph

Counting strongly connected $(k_1,k_2)$ -directed cores

The Satisfiability Threshold for $k$ -XORSAT, using an alternative proof