Axel Bacher

Contact

Laboratoire d'Informatique de Paris Nord
Université Paris 13
99, rue Jean-Baptiste Clément
93430 Villetaneuse

E-mail : bacher at lipn.fr

Mon CV se trouve ici.

Thèmes de recherche

Mes principaux thèmes de recherche :

• Combinatoire énumérative et bijective ;
• Combinatoire analytique ;
• Génération aléatoire.

Thèse

J'ai soutenu le 31 octobre 2011 ma thèse, intitulée chemins et animaux : applications de la théorie des empilements de pièces. Cette thèse a été effectuée au LaBRI, sous la direction de Mireille Bousquet-Mélou.

Articles

• (2015) Anticipated rejection algorithms and the Darling-Mandelbrot Distribution, avec Andrea Sportiello. Algorithmica, 74(1): 1-20.

  We study in limit law the complexity of some anticipated rejection random sampling algorithms. We express this complexity in terms of a probabilistic process, the threshold sum process. We show that, under the right conditions, the complexity is linear and admits as a limit law a so-called Darling-Mandelbrot distribution, studied by Darling (Trans Am Math Soc 73:95-107, 1952) and Lew (Constr Approx 10(1):15-30, 1994). We also give an explicit form to the density of the Darling-Mandelbrot distribution and derive some of its analytic properties.

• (2014) The Dyck pattern poset, avec Antonio Bernini, Luca Ferrari, Benjamin Gunby, Renzo Pinzani et Julian West. Discrete Mathematics, 321: 12-23.

  We introduce the notion of pattern in the context of lattice paths, and investigate it in the specific case of Dyck paths. Similarly to the case of permutations, the pattern-containment relation defines a poset structure on the set of all Dyck paths, which we call the Dyck pattern poset. Given a Dyck path P, we determine a formula for the number of Dyck paths covered by P, as well as for the number of Dyck paths covering P. We then address some typical pattern-avoidance issues, enumerating some classes of pattern-avoiding Dyck paths. We also compute the generating function of Dyck paths avoiding any single pattern in a recursive fashion, from which we deduce the exact enumeration of such a class of paths. Finally, we describe the asymptotic behavior of the sequence counting Dyck paths avoiding a generic pattern, we prove that the Dyck pattern poset is a well-ordering and we propose a list of open problems.

• (2012) Average site perimeter of directed animals on the two-dimensional lattices. Discrete Mathematics, 312(5): 1038-1058 [ PDF | arXiv ].

  We introduce new combinatorial (bijective) methods that enable us to compute the average value of three parameters of directed animals of a given area, including the site perimeter. Our results cover directed animals of any one-line source on the square lattice and its bounded variants, and we give counterparts for most of them in the triangular lattices. We thus prove conjectures by Conway and Le Borgne. The techniques used are based on Viennot's correspondence between directed animals and heaps of pieces (or elements of a partially commutative monoid).

• (2011) Weakly directed self-avoiding walks, avec Mireille Bousquet-Mélou. Journal of Combinatorial Theory Ser. A, 118(8): 2365-2391 [ PDF | arXiv ].

  We define a new family of self-avoiding walks (SAW) on the square lattice, called weakly directed walks. These walks have a simple characterization in terms of the irreducible bridges that compose them. We determine their generating function. This series has a complex singularity structure and in particular, is not D-finite. The growth constant is approximately 2.54 and is thus larger than that of all natural families of SAW enumerated so far (but smaller than that of general SAW, which is about 2.64). We also prove that the end-to-end distance of weakly directed walks grows linearly. Finally, we study a diagonal variant of this model.

Conférences

• Continued Classification of 3D Lattice Models in the Positive Octant, avec Manuel Kauers et Rika Yatchak. FPSAC 2016.

  We continue the investigations of lattice walks in the three dimensional lattice restricted to the positive octant. We separate models which clearly have a D-finite generating function from models for which there is no reason to expect that their generating function is D-finite, and we isolate a small set of models whose nature remains unclear and requires further investigation. For these, we give some experimental results about their asymptotic behaviour, based on the inspection of a large number of initial terms. At least for some of them, the guessed asymptotic form seems to tip the balance towards non-D-finiteness.

• Weakly prudent self-avoiding bridges, avec Nicholas Beaton. FPSAC 2014, 827-838 [ PDF ]

  We define and enumerate a new class of self-avoiding walks on the square lattice, which we call weakly prudent bridges. Their definition is inspired by two previously-considered classes of self-avoiding walks, and can be viewed as a combination of those two models. We consider several methods for recursively generating these objects, each with its own advantages and disadvantages, and use these methods to solve the generating function, obtain very long series, and randomly generate walks of arbitrary size. We find that the growth constant of these walks is approximately 2.58, which is larger than that of any previously-solved class of self-avoiding walks.

• A bijective proof of multivariate Lagrange inversion using the Cyclic Lemma., avec Gilles Schaeffer. Eurocomb 2013, 551-556 [ PDF ].

  We give a multitype extension of the cycle lemma of (Dvoretzky and Motzkin 1947). This allows us to obtain a combinatorial proof of the multivariate Lagrange inversion formula that generalizes the celebrated proof of (Raney 1963) in the univariate case, and its extension in (Chottin 1981) to the two variable case. Until now, only the alternative approach of (Joyal 1981) and (Labelle 1981) via labelled arborescences and endofunctions had been successfully extended to the multivariate case in (Gessel 1983), (Goulden and Kulkarni 1996), (Bousquet et al. 2003), and the extension of the cycle lemma to more than 2 variables was elusive. The cycle lemma has found a lot of applications in combinatorics, so we expect our multivariate extension to be quite fruitful: as a first application we mention economical linear time exact random sampling for multispecies trees.

• Directed and multi-directed animals on the King's lattice. Eurocomb 2013, 535-541 [ PDF | arXiv ].

  Let N be the directed lattice defined as the square lattice with directed bonds W, NW, N, NE, E. We enumerate directed animals on this lattice using a bijection with Viennot's heaps of pieces. We also define and enumerate a superclass of directed animals, the elements of which are called multi-directed animals. This follows Bousquet-Mélou and Rechnitzer's work on the directed triangular and square lattices. Our final results show that directed and multi-directed animals asymptotically behave similarly to the ones on the triangular and square lattices.

• Efficient random sampling of binary and unary-binary trees via holonomic equations, avec Olivier Bodini et Alice Jacquot. ANALCO 2013. [ PDF | arXiv ].

  We present a new uniform random sampler for binary trees with n internal nodes consuming 2n + Theta(log(n)²) random bits on average. This makes it quasi-optimal and out-performs the classical Remy algorithm. We also present a sampler for unary-binary trees with n nodes taking Theta(n) random bits on average. Both are the first linear-time algorithms to be optimal up to a constant.

• Weakly directed self-avoiding walks, avec Mireille Bousquet-Mélou. FPSAC 2010. [ PDF | arXiv ].

  We define a new family of self-avoiding walks (SAW) on the square lattice, called weakly directed walks. These walks have a simple characterization in terms of the irreducible bridges that compose them. We determine their generating function. This series has a complex singularity structure and in particular, is not D-finite. The growth constant is approximately 2.54 and is thus larger than that of all natural families of SAW enumerated so far (but smaller than that of general SAW, which is about 2.64). We also prove that the end-to-end distance of weakly directed walks grows linearly. Finally, we study a diagonal variant of this model.

Prépublications

• (2016) A new bijection on m-Dyck paths with application to random sampling [ PDF | arXiv ]

  We present a new bijection between variants of m-Dyck paths (paths with steps in {+1,−m} starting and ending at height 0 and remaining at non-negative height), which generalizes a classical bijection between Dyck prefixes and pointed Łukasiewicz paths. As an application, we present a new random sampling procedure for m-Dyck paths with a linear time complexity and using a quasi-optimal number of random bits. This outperforms Devroye's algorithm, which uses O(n log n) random bits.

• (2016) Generating random permutations by coin-tossing: classical algorithms, new analysis and modern implementation, avec Olivier Bodini, Hsien-Kuei Hwang et Tsung-Hsi Tsai [ PDF ]

  Several simple, classical, little-known algorithms in the statistical literature for generating random permutations by coin-tossing are examined, analyzed and implemented. These algo- rithms are either asymptotically optimal or close to being so in terms of the expected number of times the random bits are generated. In addition to asymptotic approximations to the expected complexity, we also clarify the corresponding variances, as well as the asymptotic distribu- tions. A brief comparative discussion with numerical computations in a multicore system is also given.

• (2015) MergeShuffle: a very fast, parallel random permutation algorithm, avec Olivier Bodini, Alexandros Hollender et Jérémie Lumbroso [ PDF | arXiv | github ]

  This article introduces an algorithm, MergeShuffle, which is an extremely efficient algorithm to generate random permutations (or to randomly permute an existing array). It is easy to implement, runs in n log 2n+O(1) time, is in-place, uses n log 2n+Θ(n) random bits, and can be parallelized accross any number of processes, in a shared-memory PRAM model. Finally, our preliminary simulations using OpenMP suggest it is more efficient than the Rao-Sandelius algorithm, one of the fastest existing random permutation algorithms. We also show how it is possible to further reduce the number of random bits consumed, by introducing a second algorithm BalancedShuffle, a variant of the Rao-Sandelius algorithm which is more conservative in the way it recursively partitions arrays to be shuffled. While this algorithm is of lesser practical interest, we believe it may be of theoretical value.

• (2013) Generalized Dyck paths of bounded height [ PDF | arXiv ]

  Generalized Dyck paths (or discrete excursions) are one-dimensional paths that take their steps in a given finite set S, start and end at height 0, and remain at a non-negative height. Bousquet-Mélou showed that the generating function E_k of excursions of height at most k is of the form F_k/F_k+1, where the F_k are polynomials satisfying a linear recurrence relation. We give a combinatorial interpretation of the polynomials F_k and of their recurrence relation using a transfer matrix method. We then extend our method to enumerate discrete meanders (or paths that start at 0 and remain at a non-negative height, but may end anywhere). Finally, we study the particular case where the set S is symmetric and show that several simplifications occur.