Andrei Asinowski
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Andrei Asinowski has a total of 55 co-authors. Here are the top co-authors by number of shared publications:
- Toufik Mansour
University of Haifa
8 shared publications - Gill Barequet
Department of Computer Science, The Technion—Israel Institute of Technology, Haifa, Israel
7 shared publications Gadi Aleksandrowicz
4 shared publicationsGill Barequet
3 shared publications- Meir Katchalski
Faculty of Mathematics, Technion–Israel Institute of Technology, Haifa 32000
3 shared publications Ronnie Barequet
3 shared publications
Latest Publications
- Open Access
- 14 March 2025
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 5 (1)
Combinatorics of rectangulations: old and new bijections
- 14 March 2025
- Published by California Digital Library (CDL) in Combinatorial Theory
- Vol. 5 (1)
Open AccessCombinatorics of rectangulations: old and new bijections
- Open Access
Combinatorics of rectangulations: Old and new bijections
A rectangulation is a decomposition of a rectangle into finitely many rectangles. Via natural equivalence relations, rectangulations can be seen as combinatorial objects with a rich structure, with links to lattice congruences, flip graphs, polytopes, lattice paths, Hopf algebras, etc. In this paper, we first revisit the structure of the respective equivalence classes: weak rectangulations that preserve rectangle-segment adjacencies, and strong rectangulations that preserve rectangle-rectangle adjacencies. We thoroughly investigate posets defined by adjacency in rectangulations of both kinds, and unify and simplify known bijections between rectangulations and permutation classes. This yields a uniform treatment of mappings between permutations and rectangulations that unifies the results from earlier contributions, and emphasizes parallelism and differences between the weak and the strong cases. Then, we consider the special case of guillotine rectangulations, and prove that they can be characterized - under all known mappings between permutations and rectangulations - by avoidance of two mesh patterns that correspond to "windmills" in rectangulations. This yields new permutation classes in bijection with weak guillotine rectangulations, and the first known permutation class in bijection with strong guillotine rectangulations. Finally, we address enumerative issues and prove asymptotic bounds for several families of strong rectangulations.
Open AccessCombinatorics of rectangulations: Old and new bijections
A rectangulation is a decomposition of a rectangle into finitely many rectangles. Via natural equivalence relations, rectangulations can be seen as combinatorial objects with a rich structure, with links to lattice congruences, flip graphs, polytopes, lattice paths, Hopf algebras, etc. In this paper, we first revisit the structure of the respective equivalence classes: weak rectangulations that preserve rectangle-segment adjacencies, and strong rectangulations that preserve rectangle-rectangle adjacencies. We thoroughly investigate posets defined by adjacency in rectangulations of both kinds, and unify and simplify known bijections between rectangulations and permutation classes. This yields a uniform treatment of mappings between permutations and rectangulations that unifies the results from earlier contributions, and emphasizes parallelism and differences between the weak and the strong cases. Then, we consider the special case of guillotine rectangulations, and prove that they can be characterized - under all known mappings between permutations and rectangulations - by avoidance of two mesh patterns that correspond to "windmills" in rectangulations. This yields new permutation classes in bijection with weak guillotine rectangulations, and the first known permutation class in bijection with strong guillotine rectangulations. Finally, we address enumerative issues and prove asymptotic bounds for several families of strong rectangulations.
- 10 September 2022
- Published by Springer Nature in Annals of Combinatorics
- Vol. 26 (4) , 997-1020
Polycubes with Small Perimeter Defect
- 10 September 2022
- Published by Springer Nature in Annals of Combinatorics
- Vol. 26 (4) , 997-1020
Polycubes with Small Perimeter Defect
- Open Access
- 13 October 2019
- Published by Springer Nature in Algorithmica
- Vol. 82 (3) , 386-428
Analytic Combinatorics of Lattice Paths with Forbidden Patterns, the Vectorial Kernel Method, and Generating Functions for Pushdown Automata
In this article we develop a vectorial kernel method—a powerful method which solves in a unified framework all the problems related to the enumeration of words generated by a pushdown automaton. We apply it for the enumeration of lattice paths that avoid a fixed word (a pattern), or for counting the occurrences of a given pattern. We unify results from numerous articles concerning patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. This refines the study by Banderier and Flajolet from 2002 on enumeration and asymptotics of lattice paths: we extend here their results to pattern-avoiding walks/bridges/meanders/excursions. We show that the autocorrelation polynomial of this forbidden pattern, as introduced by Guibas and Odlyzko in 1981 in the context of rational languages, still plays a crucial role for our algebraic languages. En passant, our results give the enumeration of some classes of self-avoiding walks, and prove several conjectures from the On-Line Encyclopedia of Integer Sequences. Finally, we also give the trivariate generating function (length, final altitude, number of occurrences of the pattern p), and we prove that the number of occurrences is normally distributed and linear with respect to the length of the walk: this is what Flajolet and Sedgewick call an instance of Borges’s theorem.
- 13 October 2019
- Published by Springer Nature in Algorithmica
- Vol. 82 (3) , 386-428
Open AccessAnalytic Combinatorics of Lattice Paths with Forbidden Patterns, the Vectorial Kernel Method, and Generating Functions for Pushdown Automata
In this article we develop a vectorial kernel method—a powerful method which solves in a unified framework all the problems related to the enumeration of words generated by a pushdown automaton. We apply it for the enumeration of lattice paths that avoid a fixed word (a pattern), or for counting the occurrences of a given pattern. We unify results from numerous articles concerning patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. This refines the study by Banderier and Flajolet from 2002 on enumeration and asymptotics of lattice paths: we extend here their results to pattern-avoiding walks/bridges/meanders/excursions. We show that the autocorrelation polynomial of this forbidden pattern, as introduced by Guibas and Odlyzko in 1981 in the context of rational languages, still plays a crucial role for our algebraic languages. En passant, our results give the enumeration of some classes of self-avoiding walks, and prove several conjectures from the On-Line Encyclopedia of Integer Sequences. Finally, we also give the trivariate generating function (length, final altitude, number of occurrences of the pattern p), and we prove that the number of occurrences is normally distributed and linear with respect to the length of the walk: this is what Flajolet and Sedgewick call an instance of Borges’s theorem.
- 8 March 2018
- Published by Springer Nature
- p. 195-206
Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects
- 8 March 2018
- Published by Springer Nature
- p. 195-206
Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects
- 1 March 2018
- Published by Elsevier in Computational Geometry
- Vol. 68, 7-33
Point sets with many non-crossing perfect matchings
- 1 March 2018
- Published by Elsevier in Computational Geometry
- Vol. 68, 7-33
Point sets with many non-crossing perfect matchings
- 1 November 2017
- Published by Elsevier in Information Processing Letters
- Vol. 127, 62-66
Recovering highly-complex linear recurrences of integer sequences
- 1 November 2017
- Published by Elsevier in Information Processing Letters
- Vol. 127, 62-66
Recovering highly-complex linear recurrences of integer sequences
- 1 August 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 61, 61-67
Enumerating Polyominoes with Fixed Perimeter Defect
- 1 August 2017
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 61, 61-67
Enumerating Polyominoes with Fixed Perimeter Defect
- 1 May 2017
- Published by Elsevier in European Journal of Combinatorics
- Vol. 62, 92-114
Counting triangulations of some classes of subdivided convex polygons
- 1 May 2017
- Published by Elsevier in European Journal of Combinatorics
- Vol. 62, 92-114
Counting triangulations of some classes of subdivided convex polygons
- 1 December 2016
- Published by Elsevier in Discrete Mathematics
- Vol. 339 (12) , 2919-2932
Counting houses of Pareto optimal matchings in the house allocation problem
- 1 December 2016
- Published by Elsevier in Discrete Mathematics
- Vol. 339 (12) , 2919-2932
Counting houses of Pareto optimal matchings in the house allocation problem