DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2026.29

Enumeration of Bipartite Acyclic Digraphs

Authors: Guan-Huei Duh, Philipp Sprüssel, and Stephan Wagner

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

Abstract

We consider the asymptotic enumeration of labelled acyclic digraphs (DAGs) with the additional restriction of being bipartite. The analysis leads us to a meromorphic generating function in two variables for the number of bicoloured labelled DAGs whose analysis falls within the scope of analytic combinatorics in several variables. This allows us to obtain asymptotic formulas for the total number of labelled bipartite DAGs with a given number of vertices as well as for the number of such DAGs with a given bipartition (i.e., with prescribed sizes of the two partite sets).

Cite as

Guan-Huei Duh, Philipp Sprüssel, and Stephan Wagner. Enumeration of Bipartite Acyclic Digraphs. 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. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duh_et_al:LIPIcs.AofA.2026.29,
  author =	{Duh, Guan-Huei and Spr\"{u}ssel, Philipp and Wagner, Stephan},
  title =	{{Enumeration of Bipartite Acyclic Digraphs}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{29:1--29:18},
  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.29},
  URN =		{urn:nbn:de:0030-drops-263005},
  doi =		{10.4230/LIPIcs.AofA.2026.29},
  annote =	{Keywords: bipartite acyclic digraph, asymptotic enumeration, analytic combinatorics in several variables}
}

Document

Keynote Speakers

DOI: 10.4230/LIPIcs.AofA.2018.7

Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers)

Authors: Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract

We consider k-dimensional random simplicial complexes that are generated from the binomial random (k+1)-uniform hypergraph by taking the downward-closure, where k >= 2. For each 1 <= j <= k-1, we determine when all cohomology groups with coefficients in F_2 from dimension one up to j vanish and the zero-th cohomology group is isomorphic to F_2. This property is not monotone, but nevertheless we show that it has a single sharp threshold. Moreover, we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. Furthermore, we study the asymptotic distribution of the dimension of the j-th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced in [Linial and Meshulam, Combinatorica, 2006], a result which has only been known for dimension two [Kahle and Pittel, Random Structures Algorithms, 2016].

Cite as

Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel. Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cooley_et_al:LIPIcs.AofA.2018.7,
  author =	{Cooley, Oliver and Del Giudice, Nicola and Kang, Mihyun and Spr\"{u}ssel, Philipp},
  title =	{{Vanishing of Cohomology Groups of Random Simplicial Complexes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and 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.2018.7},
  URN =		{urn:nbn:de:0030-drops-89006},
  doi =		{10.4230/LIPIcs.AofA.2018.7},
  annote =	{Keywords: Random hypergraphs, random simplicial complexes, sharp threshold, hitting time, connectedness}
}

Search Results

Documents authored by Sprüssel, Philipp

Enumeration of Bipartite Acyclic Digraphs

Abstract

Cite as

Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers)

Abstract

Cite as

Thanks for your feedback!

Could not send message