Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated just now
PreprintCC BY 4.0HAL

Counting and Sampling Git Graphs

  • Julien Courtiel
  • Martin Pépin
Open at sourcePDFDOICite

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 ∑k=2n ∑f = 1k−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 e1/8/2 (n/2e)n/2 exp(1/2 lnn/2 √(n/2) + √(2 n) + (lnn/2)2/32 ) (n/2)−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.

Related

  1. A Counting and Sampling Lovász Local Lemma
    Hongyang Liu, Chunyang Wang, Yitong Yin +2
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  2. A general counting and sampling Lovász local lemma
    Vishesh Jain, Clayton Mizgerd, Huy Tuan Pham
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Counting cographs in locally dense graphs
    Hyunwoo Lee
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Counting Minimal Vertex Cutsets and a Gap at 1 for Site Percolation on Vertex-Transitive Graphs
    Joel Bassil
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  5. Counting almost independent sets in regular graphs
    Gaia Carenini
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{courtiel2026counting,
  title = {{Counting and Sampling Git Graphs}},
  author = {Julien Courtiel and Martin Pépin},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.37208},
  eprint = {2610.37208},
  archivePrefix = {arXiv},
  url = {https://hal.science/hal-05840557v1},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Counting and Sampling Git Graphs
AU  - Julien Courtiel
AU  - Martin Pépin
PY  - 2026
DA  - 2026/10/27
PB  - HAL
DO  - 10.48550/arxiv.2610.37208
UR  - https://hal.science/hal-05840557v1
AB  - 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 ∑_k=2^n ∑_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 e^1/8/2 (n/2e)^n/2 exp(1/2 lnn/2 √(n/2) + √(2 n) + (lnn/2)^2/32 ) (n/2)^−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.
ER  -