Search Results

Documents authored by Wallner, Michael

Document
DOI: 10.4230/LIPIcs.AofA.2024.7
Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models

Authors: Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner

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

Abstract
Composition schemes are ubiquitous in combinatorics, statistical mechanics and probability theory. We give a unifying explanation to various phenomena observed in the combinatorial and statistical physics literature in the context of q-enumeration (this is a model where objects with a parameter of value k have a Gibbs measure/Boltzmann weight q^k). For structures enumerated by a composition scheme, we prove a phase transition for any parameter having such a Gibbs measure: for a critical value q = q_c, the limit law of the parameter is a two-parameter Mittag-Leffler distribution, while it is Gaussian in the supercritical regime (q > q_c), and it is a Boltzmann distribution in the subcritical regime (0 < q < q_c). We apply our results to fundamental statistics of lattice paths and quarter-plane walks. We also explain previously observed limit laws for pattern-restricted permutations, and a phenomenon uncovered by Krattenthaler for the wall contacts in watermelons.
Cite as

Cyril Banderier, Markus Kuba, Stephan Wagner, and Michael Wallner. Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models. 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. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2024.7,
  author =	{Banderier, Cyril and Kuba, Markus and Wagner, Stephan and Wallner, Michael},
  title =	{{Composition Schemes: q-Enumerations and Phase Transitions in Gibbs Models}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{7:1--7:18},
  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.7},
  URN =		{urn:nbn:de:0030-drops-204427},
  doi =		{10.4230/LIPIcs.AofA.2024.7},
  annote =	{Keywords: Composition schemes, q-enumeration, generating functions, Gibbs distribution, phase transitions, limit laws, Mittag-Leffler distribution, chi distribution, Boltzmann distribution}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.15
Asymptotics of Relaxed k-Ary Trees

Authors: Manosij Ghosh Dastidar and Michael Wallner

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

Abstract
A relaxed k-ary tree is an ordered directed acyclic graph with a unique source and sink in which every node has out-degree k. These objects arise in the compression of trees in which some repeated subtrees are factored and repeated appearances are replaced by pointers. We prove an asymptotic theta-result for the number of relaxed k-ary tree with n nodes for n → ∞. This generalizes the previously proved binary case to arbitrary finite arity, and shows that the seldom observed phenomenon of a stretched exponential term e^{c n^{1/3}} appears in all these cases. We also derive the recurrences for compacted k-ary trees in which all subtrees are unique and minimal deterministic finite automata accepting a finite language over a finite alphabet.
Cite as

Manosij Ghosh Dastidar and Michael Wallner. Asymptotics of Relaxed k-Ary 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. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ghoshdastidar_et_al:LIPIcs.AofA.2024.15,
  author =	{Ghosh Dastidar, Manosij and Wallner, Michael},
  title =	{{Asymptotics of Relaxed k-Ary Trees}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{15:1--15:13},
  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.15},
  URN =		{urn:nbn:de:0030-drops-204506},
  doi =		{10.4230/LIPIcs.AofA.2024.15},
  annote =	{Keywords: Asymptotic enumeration, stretched exponential, Airy function, directed acyclic graph, Dyck paths, compacted trees, minimal automata}
}
Document
DOI: 10.4230/LIPIcs.AofA.2022.5
Enumeration of d-Combining Tree-Child Networks

Authors: Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Michael Wallner, and Guan-Ru Yu

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

Abstract
Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for bicombining tree-child networks which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to d-combining tree-child networks where every reticulation node has now d ≥ 2 parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves.
Cite as

Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Michael Wallner, and Guan-Ru Yu. Enumeration of d-Combining Tree-Child Networks. 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. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.AofA.2022.5,
  author =	{Chang, Yu-Sheng and Fuchs, Michael and Liu, Hexuan and Wallner, Michael and Yu, Guan-Ru},
  title =	{{Enumeration of d-Combining Tree-Child Networks}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{5:1--5:13},
  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.5},
  URN =		{urn:nbn:de:0030-drops-160914},
  doi =		{10.4230/LIPIcs.AofA.2022.5},
  annote =	{Keywords: Phylogenetic network, tree-child network, d-combining tree-child network, exact enumeration, asymptotic enumeration, reticulation node, limit law, stretched exponential}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.2
Latticepathology and Symmetric Functions (Extended Abstract)

Authors: Cyril Banderier, Marie-Louise Lackner, and Michael Wallner

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
In this article, we revisit and extend a list of formulas based on lattice path surgery: cut-and-paste methods, factorizations, the kernel method, etc. For this purpose, we focus on the natural model of directed lattice paths (also called generalized Dyck paths). We introduce the notion of prime walks, which appear to be the key structure to get natural decompositions of excursions, meanders, bridges, directly leading to the associated context-free grammars. This allows us to give bijective proofs of bivariate versions of Spitzer/Sparre Andersen/Wiener - Hopf formulas, thus capturing joint distributions. We also show that each of the fundamental families of symmetric polynomials corresponds to a lattice path generating function, and that these symmetric polynomials are accordingly needed to express the asymptotic enumeration of these paths and some parameters of limit laws. En passant, we give two other small results which have their own interest for folklore conjectures of lattice paths (non-analyticity of the small roots in the kernel method, and universal positivity of the variability condition occurring in many Gaussian limit law schemes).
Cite as

Cyril Banderier, Marie-Louise Lackner, and Michael Wallner. Latticepathology and Symmetric Functions (Extended Abstract). In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2020.2,
  author =	{Banderier, Cyril and Lackner, Marie-Louise and Wallner, Michael},
  title =	{{Latticepathology and Symmetric Functions (Extended Abstract)}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{2:1--2:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.2},
  URN =		{urn:nbn:de:0030-drops-120329},
  doi =		{10.4230/LIPIcs.AofA.2020.2},
  annote =	{Keywords: Lattice path, generating function, symmetric function, algebraic function, kernel method, context-free grammar, Sparre Andersen formula, Spitzer’s identity, Wiener - Hopf factorization}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.8
More Models of Walks Avoiding a Quadrant

Authors: Mireille Bousquet-Mélou and Michael Wallner

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
We continue the enumeration of plane lattice paths avoiding the negative quadrant initiated by the first author in [Bousquet-Mélou, 2016]. We solve in detail a new case, the king walks, where all 8 nearest neighbour steps are allowed. As in the two cases solved in [Bousquet-Mélou, 2016], the associated generating function is proved to differ from a simple, explicit D-finite series (related to the enumeration of walks confined to the first quadrant) by an algebraic one. The principle of the approach is the same as in [Bousquet-Mélou, 2016], but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree. We also explain why we expect the observed algebraicity phenomenon to persist for 4 more models, for which the quadrant problem is solvable using the reflection principle.
Cite as

Mireille Bousquet-Mélou and Michael Wallner. More Models of Walks Avoiding a Quadrant. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bousquetmelou_et_al:LIPIcs.AofA.2020.8,
  author =	{Bousquet-M\'{e}lou, Mireille and Wallner, Michael},
  title =	{{More Models of Walks Avoiding a Quadrant}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.8},
  URN =		{urn:nbn:de:0030-drops-120383},
  doi =		{10.4230/LIPIcs.AofA.2020.8},
  annote =	{Keywords: Enumerative combinatorics, lattice paths, non-convex cones, algebraic series, D-finite series}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.11
Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language

Authors: Andrew Elvey Price, Wenjie Fang, and Michael Wallner

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
We show that the number of minimal deterministic finite automata with n+1 states recognizing a finite binary language grows asymptotically for n → ∞ like Θ(n! 8ⁿ e^{3 a₁ n^{1/3}} n^{7/8}), where a₁ ≈ -2.338 is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two-parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Netwon polygons.
Cite as

Andrew Elvey Price, Wenjie Fang, and Michael Wallner. Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{elveyprice_et_al:LIPIcs.AofA.2020.11,
  author =	{Elvey Price, Andrew and Fang, Wenjie and Wallner, Michael},
  title =	{{Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.11},
  URN =		{urn:nbn:de:0030-drops-120419},
  doi =		{10.4230/LIPIcs.AofA.2020.11},
  annote =	{Keywords: Airy function, asymptotics, directed acyclic graphs, Dyck paths, bijection, stretched exponential, compacted trees, minimal automata, finite languages}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.11
Periodic Pólya Urns and an Application to Young Tableaux

Authors: Cyril Banderier, Philippe Marchal, and Michael Wallner

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

Abstract
Pólya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial non-linear partial differential equation indeed leads to linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.
Cite as

Cyril Banderier, Philippe Marchal, and Michael Wallner. Periodic Pólya Urns and an Application to Young Tableaux. 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. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{banderier_et_al:LIPIcs.AofA.2018.11,
  author =	{Banderier, Cyril and Marchal, Philippe and Wallner, Michael},
  title =	{{Periodic P\'{o}lya Urns and an Application to Young Tableaux}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-89045},
  doi =		{10.4230/LIPIcs.AofA.2018.11},
  annote =	{Keywords: P\'{o}lya urn, Young tableau, generating functions, analytic combinatorics, pumping moment, D-finite function, hypergeometric function, generalized Gamma distribution, Mittag-Leffler distribution}
}
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 About DROPS Imprint Privacy Contact