Document Open Access Logo

Universal Properties of Catalytic Variable Equations

Authors Michael Drmota , Eva-Maria Hainzl

PDF
Thumbnail PDF

File

LIPIcs.AofA.2022.7.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

Michael Drmota
  • TU Wien, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstrasse 8-10, A-1040 Vienna, Austria
Eva-Maria Hainzl
  • TU Wien, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstrasse 8-10, A-1040 Vienna, Austria

Funding

  • Drmota, Michael: Research supported by the Austrian Science Foundation FWF, projects F50-02, F55-02, and P35016.
  • Hainzl, Eva-Maria: Research supported by the Austrian Science Foundation FWF, project F55-02.

Acknowledgements

We thank the referees for their careful reading and their valuable comments for improving the presentation.

Cite AsGet BibTex

Michael Drmota and Eva-Maria Hainzl. Universal Properties of Catalytic Variable Equations. 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. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.AofA.2022.7

Abstract

Catalytic equations appear in several combinatorial applications, most notably in the enumeration of lattice paths and in the enumeration of planar maps. The main purpose of this paper is to show that under certain positivity assumptions the dominant singularity of the solution function has a universal behavior. We have to distinguish between linear catalytic equations, where a dominating square-root singularity appears, and non-linear catalytic equations, where we - usually - have a singularity of type 3/2.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Generating functions
Keywords
  • catalytic equation
  • singular expansion
  • univeral asymptotics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger. Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata. Algorithmica, 82(3):386-428, 2020. Google Scholar
  2. Cyril Banderier and Michael Drmota. Formulae and asymptotics for coefficients of algebraic functions. Comb. Probab. Comput., 24(1):1-53, 2015. URL: https://doi.org/10.1017/S0963548314000728.
  3. Cyril Banderier and Philippe Flajolet. Basic analytic combinatorics of directed lattice paths. Theor. Comput. Sci., 281(1-2):37-80, 2002. Google Scholar
  4. Mireille Bousquet-Mélou and Arnaud Jehanne. Polynomial equations with one catalytic variable, algebraic series and map enumeration. J. Comb. Theory, Ser. B, 96(5):623-672, 2006. URL: https://doi.org/10.1016/j.jctb.2005.12.003.
  5. W. G. Brown and W. T. Tutte. On the enumeration of rooted non-separable planar maps. Can. J. Math., 16:572-577, 1964. URL: https://doi.org/10.4153/CJM-1964-058-7.
  6. Michael Drmota. Random trees. An interplay between combinatorics and probability. Wien: Springer, 2009. URL: https://doi.org/10.1007/978-3-211-75357-6.
  7. Michael Drmota, Marc Noy, and Guan-Ru Yu. Universal singular exponents in catalytic variable equations. J. Comb. Theory, Ser. A, 185:33, 2022. Id/No 105522. URL: https://doi.org/10.1016/j.jcta.2021.105522.
  8. Michael Drmota and Konstantinos Panagiotou. A central limit theorem for the number of degree-k vertices in random maps. Algorithmica, 66(4):741-761, 2013. Google Scholar
  9. Michael Drmota and Guan-Ru Yu. The Number of Double Triangles in Random Planar Maps. In James Allen Fill and Mark Daniel Ward, editors, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), volume 110 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1-19:18, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.AofA.2018.19.
  10. Philippe Flajolet and Andrew Odlyzko. Singularity analysis of generating functions. SIAM J. Discrete Math., 3(2):216-240, 1990. URL: https://doi.org/10.1137/0403019.
  11. Helmut Prodinger. The kernel method: a collection of examples. Sémin. Lothar. Comb., 50:b50f, 19, 2003. Google Scholar
  12. W. T. Tutte. A census of planar maps. Can. J. Math., 15:249-271, 1963. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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