My research
Research interest
I am interested in probability and combinatorics, including randomized algorithms, random graphs and random tree, in particular:
I also like programming and using computer to experiment, prove, and teach mathematics.
Occasionally I play with special functions.
Publications
You can find all my research papers on Zotero (most up-to-date), Google Scholar (slightly delayed), and arXiv.
Here are some of my open source software projects on GitHub.
Preprints
G. Berzunza, X. S. Cai, and C. Holmgren, “The fluctuations of the giant cluster for percolation on random split trees,” arXiv:1902.08109 [math], May 2021 [Online]. [link].
X. S. Cai, P. Caputo, G. Perarnau, and M. Quattropani, “Rankings in directed configuration models with heavy tailed in-degrees,” arXiv:2104.08389 [cs, math], Apr. 2021. link.
X. S. Cai and G. Perarnau, “The diameter of the directed configuration model,” arXiv:2003.04965 [cs, math], Mar. 2020. [link]
X. S. Cai and G. Perarnau, “Minimum stationary values of sparse random directed graphs,” arXiv:2010.07246 [cs, math], Oct. 2020. [link]
Journal articles
X. S. Cai and G. Perarnau, “The giant component of the directed configuration model revisited,” ALEA Lat. Am. J. Probab. Math. Stat., vol. 18, no. 2, pp. 1517–1528, 2021, doi: 10/gk49g2. [pdf]
X. S. Cai and J. L. López, “A note on the asymptotic expansion of the Lerch’s transcendent,” Integral Transforms and Special Functions, vol. 30, no. 10, pp. 844–855, Oct. 2019, doi: 10/ggcq7k. [pdf]
X. S. Cai, C. Holmgren, S. Janson, T. Johansson, and F. Skerman, “Inversions in split trees and conditional Galton-Watson trees,” Combinatorics, Probability and Computing, vol. 28, no. 3, pp. 335–364, May 2019, doi: 10/ggmxmh. [pdf]
X. S. Cai, C. Holmgren, L. Devroye, and F. Skerman, “k-cut on paths and some trees,” Electron. J. Probab., vol. 24, 2019, doi: 10/ggcq7j. [pdf]
X. S. Cai and C. Holmgren, “Cutting resilient networks – complete binary trees,” The Electronic Journal of Combinatorics, vol. 26, no. 4, p. P4.43, Dec. 2019, doi: 10/ggmnn3. [pdf]
G. Berzunza, X. S. Cai, and C. Holmgren, “The k-cut model in deterministic and random trees,” The Electronic Journal of Combinatorics, Jul. 2019. [link]
X. S. Cai and S. Janson, “Non-Fringe Subtrees in Conditioned Galton–Watson Trees,” The Electronic Journal of Combinatorics, p. P3.40-P3.40, Sep. 2018, doi: 10/ggh2rb. [pdf]
X. S. Cai and L. Devroye, “The graph structure of a deterministic automaton chosen at random,” Random Structures & Algorithms, vol. 51, no. 3, pp. 428–458, 2017, doi: 10/gbtqgb. [pdf]
X. S. Cai and L. Devroye, “A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees,” ALEA Lat. Am. J. Probab. Math. Stat., vol. 14, no. 1, pp. 579–611, 2017, doi: 10/ggh2rh. [pdf]
X. S. Cai, G. Perarnau, B. Reed, and A. B. Watts, “Acyclic edge colourings of graphs with large girth,” Random Structures & Algorithms, vol. 50, no. 4, pp. 511–533, 2017, doi: 10/ggmxmg. [pdf]
X. S. Cai and L. Devroye, “The analysis of Kademlia for random IDs,” Internet Mathematics, vol. 11, no. 6, pp. 572–587, Nov. 2015, doi: 10/ggmxmk. [pdf]
Conference papers
G. Berzunza, X. S. Cai, and C. Holmgren, “The k-Cut Model in Conditioned Galton-Watson Trees,” in 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), Dagstuhl, Germany, 2020, vol. 159, p. 5:1-5:10, doi: 10/ggzvz6. [pdf]
X. S. Cai, L. Devroye, C. Holmgren, and F. Skerman, “k-cuts on a path,” in Algorithms and Complexity, 2019, pp. 112–123, doi: 10/ggmxmj. [pdf]
X. S. Cai, C. Holmgren, S. Janson, T. Johansson, and F. Skerman, “Inversions in split trees and conditional Galton-Watson trees,” in 29th international conference on probabilistic, combinatorial and asymptotic methods for the analysis of algorithms (AofA 2018), Dagstuhl, Germany, 2018, vol. 110, p. 15:1-15:12, doi: 10/ggmnn6. [pdf]
X. S. Cai and L. Devroye, “A probabilistic analysis of Kademlia networks,” in Algorithms and Computation, 2013, pp. 711–721, doi: 10/ggmxmf. [pdf]
Theses
X. S. Cai, “A study of large fringe and non-fringe subtrees in conditional galton-watson trees,” PhD Thesis, 2016. [link] [pdf]
X. S. Cai, “A probabilistic analysis of Kademlia networks,” Master thesis, 2013. [link] [pdf]
My colleagues and friends
At Uppsala
Elsewhere
My talks
Rankings in directed configuration models with heavy tailed in-degrees. Analysis of Algorithms 2021 [slides]
Cutting resilient networks. [slides]
Inversions in split trees and conditional Galton–Watson trees. Analysis of Algorithms 2018, STAR Workshop on Random Graphs 2018. [slides]
A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees. Sweden Probabilistic Midwinter Meeting 2017, Meeting of the Catalan, Spanish, Swedish Math Societies, RS&A 2017. [slides]
The graph structure of a deterministic automaton chosen at random. RSA 2015. CanaDAM 2015. [slides]
Conferences and workshops
The conferences and workshops which I have attended or plan to attend.