On the algebraic numbers computable by some generalized Ehrenfest urns

Autor: Marie Albenque, Lucas Gerin

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol Vol. 14 no. 2 (2012)

This article deals with some stochastic population protocols, motivated by theoretical aspects of distributed computing. We modelize the problem by a large urn of black and white balls from which at every time unit a fixed number of balls are drawn a

Externí odkaz: https://doaj.org/article/e60472d8776043bd854f374cb0767b41

Growth function for a class of monoids

Autor: Marie Albenque, Philippe Nadeau

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AK,..., Iss Proceedings (2009)

In this article we study a class of monoids that includes Garside monoids, and give a simple combinatorial proof of a formula for the formal sum of all elements of the monoid. This leads to a formula for the growth function of the monoid in the homog

Externí odkaz: https://doaj.org/article/6b25dbf602be45af801b20c10bf33bcf

Scaling limit of triangulations of polygons

Autor: Xin Sun, Marie Albenque, Nina Holden

Publikováno v: Electronic Journal of Probability
Electronic Journal of Probability, Institute of Mathematical Statistics (IMS), 2020, 25, ⟨10.1214/20-EJP537⟩
Electronic Journal of Probability, 25
Electron. J. Probab.

We prove that random triangulations of types I, II, and III with a simple boundary under the critical Boltzmann weight converge in the scaling limit to the Brownian disk. The proof uses a bijection due to Poulalhon and Schaeffer between type III tria

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::913674d7ad5e8c2c0d4da39f5ad556c3
http://arxiv.org/abs/1910.04946

The scaling limit of random simple triangulations and random simple quadrangulations

Autor: Louigi Addario-Berry, Marie Albenque

Publikováno v: Annals of Probability
Annals of Probability, Institute of Mathematical Statistics, 2017, 45 (5), pp.2767-2825. ⟨10.1214/16-AOP1124⟩
Ann. Probab. 45, no. 5 (2017), 2767-2825

Let $M_n$ be a simple triangulation of the sphere $S^2$, drawn uniformly at random from all such triangulations with n vertices. Endow $M_n$ with the uniform probability measure on its vertices. After rescaling graph distance on $V(M_n)$ by $(3/(4n))

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::438fb7a7ab1ed786d63324c3579bd0ac
https://hal.archives-ouvertes.fr/hal-01185338

Convexity in partial cubes: the hull number

Autor: Marie Albenque, Kolja Knauer

Publikováno v: LATIN 2014
LATIN 2014, Mar 2014, Montevideo, Uruguay
11th Latin American Symposium on Theoretical Informatics (LATIN)
11th Latin American Symposium on Theoretical Informatics (LATIN), Mar 2014, Montevideo, Uruguay. pp.421-432, ⟨10.1007/978-3-642-54423-1_37⟩
Discrete Mathematics
Discrete Mathematics, Elsevier, 2016, 339 (2), pp.866-876. ⟨10.1016/j.disc.2015.10.032⟩
Discrete Mathematics, 2016, 339 (2), pp.866-876. ⟨10.1016/j.disc.2015.10.032⟩
LATIN 2014: Theoretical Informatics ISBN: 9783642544224
LATIN

We prove that the combinatorial optimization problem of determining the hull number of a partial cube is NP-complete. This makes partial cubes the minimal graph class for which NP-completeness of this problem is known and improves some earlier result

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5b7777877aa926eb552227ad98f6db5c
https://hal.science/hal-01457880/document