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

DOI: 10.4230/LIPIcs.AofA.2018.29

Asymptotic Expansions for Sub-Critical Lagrangean Forms

Authors: Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh

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

Abstract

Asymptotic expansions for the Taylor coefficients of the Lagrangean form phi(z)=zf(phi(z)) are examined with a focus on the calculations of the asymptotic coefficients. The expansions are simple and useful, and we discuss their use in some enumerating sequences in trees, lattice paths and planar maps.

Cite as

Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh. Asymptotic Expansions for Sub-Critical Lagrangean Forms. 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. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hwang_et_al:LIPIcs.AofA.2018.29,
  author =	{Hwang, Hsien-Kuei and Kang, Mihyun and Duh, Guan-Huei},
  title =	{{Asymptotic Expansions for Sub-Critical Lagrangean Forms}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{29:1--29:13},
  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.29},
  URN =		{urn:nbn:de:0030-drops-89224},
  doi =		{10.4230/LIPIcs.AofA.2018.29},
  annote =	{Keywords: asymptotic expansions, Lagrangean forms, saddle-point method, singularity analysis, maps}
}

Search Results

Documents authored by Duh, Guan-Huei

Enumeration of Bipartite Acyclic Digraphs

Abstract

Cite as

Asymptotic Expansions for Sub-Critical Lagrangean Forms

Abstract

Cite as

Thanks for your feedback!

Could not send message