Xing Shi Cai
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Xing Shi Cai has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Cecilia Holmgren
Department of Mathematics Uppsala University Sweden
5 shared publications - Guillem Perarnau
School of Mathematics University of Birmingham Birmingham UK
4 shared publications Luc Devroye
McGill University
4 shared publications- Luc Devroye
McGill University
4 shared publications - Svante Janson
Department of Mathematics, Uppsala University, Uppsala, Sweden
4 shared publications - Fiona Skerman
Department of Mathematics Uppsala University Uppsala Sweden
3 shared publications
Latest Publications
- Open Access
The fluctuations of the giant cluster for percolation on random split trees
A split tree of cardinality $n$ is constructed by distributing $n$ "balls" in a subset of vertices of an infinite tree which encompasses many types of random trees such as $m$-ary search trees, quad trees, median-of-$(2k+1)$ trees, fringe-balanced trees, digital search trees and random simplex trees. In this work, we study Bernoulli bond percolation on arbitrary split trees of large but finite cardinality $n$. We show for appropriate percolation regimes that depend on the cardinality $n$ of the split tree that there exists a unique giant cluster, the fluctuations of the size of the giant cluster as $n \rightarrow \infty$ are described by an infinitely divisible distribution that belongs to the class of stable Cauchy laws. This work generalizes the results for the random $m$-ary recursive trees in Berzunza (2015). Our approach is based on a remarkable decomposition of the size of the giant percolation cluster as a sum of essentially independent random variables which may be useful for studying percolation on other trees with logarithmic height; for instance in this work we study also the case of regular trees.Open AccessThe fluctuations of the giant cluster for percolation on random split trees
A split tree of cardinality $n$ is constructed by distributing $n$ "balls" in a subset of vertices of an infinite tree which encompasses many types of random trees such as $m$-ary search trees, quad trees, median-of-$(2k+1)$ trees, fringe-balanced trees, digital search trees and random simplex trees. In this work, we study Bernoulli bond percolation on arbitrary split trees of large but finite cardinality $n$. We show for appropriate percolation regimes that depend on the cardinality $n$ of the split tree that there exists a unique giant cluster, the fluctuations of the size of the giant cluster as $n \rightarrow \infty$ are described by an infinitely divisible distribution that belongs to the class of stable Cauchy laws. This work generalizes the results for the random $m$-ary recursive trees in Berzunza (2015). Our approach is based on a remarkable decomposition of the size of the giant percolation cluster as a sum of essentially independent random variables which may be useful for studying percolation on other trees with logarithmic height; for instance in this work we study also the case of regular trees. - 14 January 2021
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 28 (1) , P1.25
The $k$-Cut Model in Deterministic and Random Trees
The \(k\)-cut number of rooted graphs was introduced by Cai et al. as a generalization of the classical cutting model by Meir and Moon. In this paper, we show that all moments of the \(k\)-cut number of conditioned Galton-Watson trees converge after proper rescaling, which implies convergence in distribution to the same limit law regardless of the offspring distribution of the trees. This extends the result of Janson. Using the same method, we also show that the \(k\)-cut number of various random or deterministic trees of logarithmic height converges in probability to a constant after rescaling, such as random split-trees, uniform random recursive trees, and scale-free random trees.- 14 January 2021
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 28 (1) , P1.25
The $k$-Cut Model in Deterministic and Random Trees
The \(k\)-cut number of rooted graphs was introduced by Cai et al. as a generalization of the classical cutting model by Meir and Moon. In this paper, we show that all moments of the \(k\)-cut number of conditioned Galton-Watson trees converge after proper rescaling, which implies convergence in distribution to the same limit law regardless of the offspring distribution of the trees. This extends the result of Janson. Using the same method, we also show that the \(k\)-cut number of various random or deterministic trees of logarithmic height converges in probability to a constant after rescaling, such as random split-trees, uniform random recursive trees, and scale-free random trees.- Open Access
The $k$-cut model in deterministic and random trees
The $k$-cut number of rooted graphs was introduced by Cai et al. as a generalization of the classical cutting model by Meir and Moon. In this paper, we show that all moments of the k-cut number of conditioned Galton-Watson trees converges after proper rescaling, which implies convergence in distribution to the same limit law regardless of the offspring distribution of the trees. This extends the result of Janson. Using the same method, we also show that the k-cut number of various random or deterministic trees of logarithmic height converges in probability to a constant after rescaling, such as random split-trees, uniform random recursive trees, and scale-free random trees.
Open AccessThe $k$-cut model in deterministic and random trees
The $k$-cut number of rooted graphs was introduced by Cai et al. as a generalization of the classical cutting model by Meir and Moon. In this paper, we show that all moments of the k-cut number of conditioned Galton-Watson trees converges after proper rescaling, which implies convergence in distribution to the same limit law regardless of the offspring distribution of the trees. This extends the result of Janson. Using the same method, we also show that the k-cut number of various random or deterministic trees of logarithmic height converges in probability to a constant after rescaling, such as random split-trees, uniform random recursive trees, and scale-free random trees.
- Open Access
The giant component of the directed configuration model revisited
We prove a law of large numbers for the order and size of the largest strongly connected component in the directed configuration model. Our result extends previous work by Cooper and Frieze.
Open AccessThe giant component of the directed configuration model revisited
We prove a law of large numbers for the order and size of the largest strongly connected component in the directed configuration model. Our result extends previous work by Cooper and Frieze.
- Open Access
The diameter of the directed configuration model
We show that the diameter of the directed configuration model with $n$ vertices rescaled by $\log n$ converges in probability to a constant. Our assumptions are the convergence of the in- and out-degree of a uniform random vertex in distribution, first and second moment. Our result extends previous results on the diameter of the model and applies to many other random directed graphs.Open AccessThe diameter of the directed configuration model
We show that the diameter of the directed configuration model with $n$ vertices rescaled by $\log n$ converges in probability to a constant. Our assumptions are the convergence of the in- and out-degree of a uniform random vertex in distribution, first and second moment. Our result extends previous results on the diameter of the model and applies to many other random directed graphs. - Open Access
- 11 October 2019
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 26 (4) , P4.43
Cutting Resilient Networks – Complete Binary Trees
In our previous work, we introduced the random $k$-cut number for rooted graphs. In this paper, we show that the distribution of the $k$-cut number in complete binary trees of size n, after rescaling, is asymptotically a periodic function of $\lg n − \lg \lg n$. Thus there are different limit distributions for different subsequences, where these limits are similar to weakly $1$-stable distributions. This generalizes the result for the case $k = 1$, i.e., the traditional cutting model, by Janson (2004).- 11 October 2019
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 26 (4) , P4.43
Open AccessCutting Resilient Networks – Complete Binary Trees
In our previous work, we introduced the random $k$-cut number for rooted graphs. In this paper, we show that the distribution of the $k$-cut number in complete binary trees of size n, after rescaling, is asymptotically a periodic function of $\lg n − \lg \lg n$. Thus there are different limit distributions for different subsequences, where these limits are similar to weakly $1$-stable distributions. This generalizes the result for the case $k = 1$, i.e., the traditional cutting model, by Janson (2004). - Open Access
- 10 June 2019
- Published by Taylor & Francis in Integral Transforms and Special Functions
- Vol. 30 (10) , 844-855
A note on the asymptotic expansion of the Lerch's transcendent
In Ferreira and López [Asymptotic expansions of the Hurwitz–Lerch zeta function. J Math Anal Appl. 2004;298(1):210–224], the authors derived an asymptotic expansion of the Lerch's transcendent for large , valid for , and . In this paper, we study the special case not covered in Ferreira and López [Asymptotic expansions of the Hurwitz–Lerch zeta function. J Math Anal Appl. 2004;298(1):210–224], deriving a complete asymptotic expansion of the Lerch's transcendent for z>1 and as goes to infinity. We also show that when a is a positive integer, this expansion is convergent for . As a corollary, we get a full asymptotic expansion for the sum for fixed as . Some numerical results show the accuracy of the approximation.- 10 June 2019
- Published by Taylor & Francis in Integral Transforms and Special Functions
- Vol. 30 (10) , 844-855
Open AccessA note on the asymptotic expansion of the Lerch's transcendent
In Ferreira and López [Asymptotic expansions of the Hurwitz–Lerch zeta function. J Math Anal Appl. 2004;298(1):210–224], the authors derived an asymptotic expansion of the Lerch's transcendent for large , valid for , and . In this paper, we study the special case not covered in Ferreira and López [Asymptotic expansions of the Hurwitz–Lerch zeta function. J Math Anal Appl. 2004;298(1):210–224], deriving a complete asymptotic expansion of the Lerch's transcendent for z>1 and as goes to infinity. We also show that when a is a positive integer, this expansion is convergent for . As a corollary, we get a full asymptotic expansion for the sum for fixed as . Some numerical results show the accuracy of the approximation. - 31 October 2018
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 28 (3) , 335-364
Inversions in Split Trees and Conditional Galton–Watson Trees
We study I(T), the number of inversions in a tree T with its vertices labelled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of I(T) have explicit formulas involving the k-total common ancestors of T (an extension of the total path length). Then we consider Xn, the normalized version of I(Tn), for a sequence of trees Tn. For fixed Tn's, we prove a sufficient condition for Xn to converge in distribution. As an application, we identify the limit of Xn for complete b-ary trees. For Tn being split trees [16], we show that Xn converges to the unique solution of a distributional equation. Finally, when Tn's are conditional Galton–Watson trees, we show that Xn converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that significantly strengthen and broaden previous work by Panholzer and Seitz [46].
- 31 October 2018
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 28 (3) , 335-364
Inversions in Split Trees and Conditional Galton–Watson Trees
We study I(T), the number of inversions in a tree T with its vertices labelled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of I(T) have explicit formulas involving the k-total common ancestors of T (an extension of the total path length). Then we consider Xn, the normalized version of I(Tn), for a sequence of trees Tn. For fixed Tn's, we prove a sufficient condition for Xn to converge in distribution. As an application, we identify the limit of Xn for complete b-ary trees. For Tn being split trees [16], we show that Xn converges to the unique solution of a distributional equation. Finally, when Tn's are conditional Galton–Watson trees, we show that Xn converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that significantly strengthen and broaden previous work by Panholzer and Seitz [46].
- Open Access
Inversions in split trees and conditional Galton--Watson trees
We study $I(T)$, the number of inversions in a tree $T$ with its vertices labeled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of $I(T)$ have explicit formulas involving the $k$-total common ancestors of $T$ (an extension of the total path length). Then we consider $X_n$, the normalized version of $I(T_n)$, for a sequence of trees $T_n$. For fixed $T_{n}$'s, we prove a sufficient condition for $X_n$ to converge in distribution. As an application, we identify the limit of $X_n$ for complete $b$-ary trees. For $T_n$ being split trees, we show that $X_n$ converges to the unique solution of a distributional equation. Finally, when $T_n$'s are conditional Galton--Watson trees, we show that $X_n$ converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that are stronger and much broader compared to previous work by Panholzer and Seitz.Open AccessInversions in split trees and conditional Galton--Watson trees
We study $I(T)$, the number of inversions in a tree $T$ with its vertices labeled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of $I(T)$ have explicit formulas involving the $k$-total common ancestors of $T$ (an extension of the total path length). Then we consider $X_n$, the normalized version of $I(T_n)$, for a sequence of trees $T_n$. For fixed $T_{n}$'s, we prove a sufficient condition for $X_n$ to converge in distribution. As an application, we identify the limit of $X_n$ for complete $b$-ary trees. For $T_n$ being split trees, we show that $X_n$ converges to the unique solution of a distributional equation. Finally, when $T_n$'s are conditional Galton--Watson trees, we show that $X_n$ converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that are stronger and much broader compared to previous work by Panholzer and Seitz.