8 citations · 54 across the 13 of their papers we have counts for
11 papers · 1 filter
Rankings in directed configuration models with heavy tailed in-degrees
Xing Shi Cai, Pietro Caputo, Guillem Perarnau +1
We consider the extremal values of the stationary distribution of sparse directed random graphs with given degree sequences and their relation to the extremal values of the in-degr…
Minimum stationary values of sparse random directed graphs
Xing Shi Cai, Guillem Perarnau
We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least , wi…
The giant component of the directed configuration model revisited
Xing Shi Cai, Guillem Perarnau
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 a…
The diameter of the directed configuration model
Xing Shi Cai, Guillem Perarnau
We show that the diameter of the directed configuration model with vertices rescaled by converges in probability to a constant. Our assumptions are the convergence of…
The -cut model in deterministic and random trees
Gabriel Berzunza, Xing Shi Cai, Cecilia Holmgren
The -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…
The fluctuations of the giant cluster for percolation on random split trees
Gabriel Berzunza, Xing Shi Cai, Cecilia Holmgren
A split tree of cardinality is constructed by distributing "balls" in a subset of vertices of an infinite tree which encompasses many types of random trees such as -ary…
Cutting resilient networks -- complete binary trees
Xing Shi Cai, Cecilia Holmgren
In our previous work, we introduced the random -cut number for rooted graphs. In this paper, we show that the distribution of the -cut number in complete binary trees of size…
K-cut on paths and some trees
Xing Shi Cai, Luc Devroye, Cecilia Holmgren +1
We define the (random) -cut number of a rooted graph to model the difficulty of the destruction of a resilient network. The process is as the cut model of Meir and Moon except n…
Inversions in split trees and conditional Galton--Watson trees
Xing Shi Cai, Cecilia Holmgren, Svante Janson +2
We study , the number of inversions in a tree with its vertices labeled uniformly at random, which is a generalization of inversions in permutations. We first show that t…
A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees
Xing Shi Cai, Luc Devroye
We study the conditions for families of subtrees to exist with high probability (whp) in a Galton-Walton tree of size . We first give a Poisson approximation of fringe subtree c…
The graph structure of a deterministic automaton chosen at random: full version
Xing Shi Cai, Luc Devroye
A deterministic finite automaton (DFA) of states over a -letter alphabet can be seen as a digraph with vertices which all have exactly labeled out-arcs (-out digr…