Counting and Sampling Git Graphs

Source abstract

Version Control Systems, like Git and Mercurial, represent the history of a project as a Directed Acyclic Graph, capturing divergences and merges throughout development. A widely adopted workflow, the feature branch workflow, imposes a particularly simple structure: a single main branch and features branches evolving in parallel without interfering with one another. This work presents an enumerative study of these Git graphs. We first establish a bijection between Git graphs and a simpler combinatorial class, which we term cyclariums, and derive their exact count at size n, namely $\sum\_{k=2}^n \sum\_{f = 1}^{k-1} {k \brack f} { n - k - 1 \choose k - f - 1}$. Using a saddle-point method, we further show that this number is asymptotically equivalent to $$\frac{e^{1/8}}{2} \left(\frac{n}{2e}\right)^{\frac n 2} \exp\left(\frac 1 2 \ln\frac n 2 \sqrt{\frac n 2} + \sqrt{2 n} + \frac{(\ln\frac n 2)^2}{32} \right) \left(\frac n 2\right)^{-3/8}.$$ Additionally, we analyze the limit laws of key parameters. Finally, we address random generation by designing both a uniform sampler and a Boltzmann sampler for these graphs.