Search Results

Documents authored by Burghart, Fabian

Document
DOI: 10.4230/LIPIcs.AofA.2026.7
Ancestries and Descendants in a Random DAG

Authors: Fabian Burghart

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
We consider a random recursive DAG G_n on the vertex set [n] where every vertex i ≥ 2 has out-degree d, with the targets chosen uniformly at random among the earlier i-1 vertices. For this model, we propose a novel way to investigate the descendants of n (which have recently been studied in a paper by Janson) through what we call ancestry processes. The ancestor process a_i(n) of a vertex i is defined as the number of ancestors of i in G_n, and is closely related to the evolutions of multi-draw Pólya urns. Results on the descendants can then be obtained via asymptotic results on functionals of the ancestry processes, generally leading to technical integral expressions. We employ this method to make progress on two open problems posed by Janson, as well as to provide an alternative proof of a first-moment result contained in his work. We further prove limit theorems for the ancestor processes a_i(n) depending on i.
Cite as

Fabian Burghart. Ancestries and Descendants in a Random DAG. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{burghart:LIPIcs.AofA.2026.7,
  author =	{Burghart, Fabian},
  title =	{{Ancestries and Descendants in a Random DAG}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.7},
  URN =		{urn:nbn:de:0030-drops-262785},
  doi =		{10.4230/LIPIcs.AofA.2026.7},
  annote =	{Keywords: Random DAG, descendants, Markov process, Urn model, Limit theorems}
}
Document
DOI: 10.4230/LIPIcs.AofA.2026.16
On Cycles in Multiset Permutations, Parking Functions, and Related Structures

Authors: Calum Buchanan, Fabian Burghart, Stephan Wagner, and Mei Yin

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
In this paper we study cycles in multiset permutations and parking functions. As combinatorial objects, multiset permutations are essential building blocks for mappings and permutations, while parking functions lie between mappings and permutations. We take both algebraic and analytic views in our investigation and present exact as well as asymptotic results. We point to a surprising correspondence between two statistics on multiset permutations, terminal closers and cyclic points, shedding light on the combinatorial structure.
Cite as

Calum Buchanan, Fabian Burghart, Stephan Wagner, and Mei Yin. On Cycles in Multiset Permutations, Parking Functions, and Related Structures. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{buchanan_et_al:LIPIcs.AofA.2026.16,
  author =	{Buchanan, Calum and Burghart, Fabian and Wagner, Stephan and Yin, Mei},
  title =	{{On Cycles in Multiset Permutations, Parking Functions, and Related Structures}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.16},
  URN =		{urn:nbn:de:0030-drops-262874},
  doi =		{10.4230/LIPIcs.AofA.2026.16},
  annote =	{Keywords: parking function, multiset permutation, cycle type, cyclic point, terminal closer, equivalence of ensembles}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.10
A Bijection for the Evolution of B-Trees

Authors: Fabian Burghart and Stephan Wagner

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
A B-tree is a type of search tree where every node (except possibly for the root) contains between m and 2m keys for some positive integer m, and all leaves have the same distance to the root. We study sequences of B-trees that can arise from successively inserting keys, and in particular present a bijection between such sequences (which we call histories) and a special type of increasing trees. We describe the set of permutations for the keys that belong to a given history, and also show how to use this bijection to analyse statistics associated with B-trees.
Cite as

Fabian Burghart and Stephan Wagner. A Bijection for the Evolution of B-Trees. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{burghart_et_al:LIPIcs.AofA.2024.10,
  author =	{Burghart, Fabian and Wagner, Stephan},
  title =	{{A Bijection for the Evolution of B-Trees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.10},
  URN =		{urn:nbn:de:0030-drops-204451},
  doi =		{10.4230/LIPIcs.AofA.2024.10},
  annote =	{Keywords: B-trees, histories, increasing trees, bijection, asymptotic enumeration, tree statistics}
}
Document
DOI: 10.4230/LIPIcs.AofA.2022.4
A Modification of the Random Cutting Model

Authors: Fabian Burghart

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
We propose a modification to the random destruction of graphs: Given a finite network with a distinguished set of sources and targets, remove (cut) vertices at random, discarding components that do not contain a source node. We investigate the number of cuts required until all targets are removed, and the size of the remaining graph. This model interpolates between the random cutting model going back to Meir and Moon [Meir and Moon, 1970] and site percolation. We prove several general results, including that the size of the remaining graph is a tight family of random variables for compatible sequences of expander-type graphs, and determine limiting distributions complete binary trees.
Cite as

Fabian Burghart. A Modification of the Random Cutting Model. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{burghart:LIPIcs.AofA.2022.4,
  author =	{Burghart, Fabian},
  title =	{{A Modification of the Random Cutting Model}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.4},
  URN =		{urn:nbn:de:0030-drops-160903},
  doi =		{10.4230/LIPIcs.AofA.2022.4},
  annote =	{Keywords: Random cutting model, Random separation of graphs, Percolation}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact