# Preface to the special issue to the memory of Maurice Pouzet

Miguel Couceiro, Erkko Lehtonen, Pierre Monnin

<figure><img src="image_1.png" /></figure>

To cite this version:

Miguel Couceiro, Erkko Lehtonen, Pierre Monnin. Preface to the special issue to the memory of Maurice Pouzet. Discrete Mathematics and Theoretical Computer Science, 23 (2), 2023. hal-04860979

HAL Id: hal-04860979

https://inria.hal.science/hal-04860979v1

Submitted on 1 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Preface to the special issue
to the memory of Maurice Pouzet

Miguel Couceiro<fnref n="1" />,<fnref n="2" />

Erkko Lehtonen<fnref n="3" />

Pierre Monnin<fnref n="4" />

revisions 3rd Dec. 2022; accepted 1st Jan. 2023.

# 1 Motivation and the ALGOS 2020 conference

This volume follows the international conference "Algebras, graphs and ordered sets" (ALGOS 2020) that brought together some of the best specialists in the theory of graphs, relational structures and ordered sets, themes that are omnipresent in artificial intelligence and in knowledge discovery. One of the goals of this event was to provide a common ground for researchers in various fields of computer science and mathematics to meet, present their latest results, and discuss original applications in related scientific fields.

ALGOS 2020 was dedicated to Maurice Pouzet on the occasion of his 75th birthday, and thus welcomed submissions in areas closely related to Maurice's broad scientific interests, in particular,

• lattices and ordered sets,

• combinatorics and graph theory,

• set theory and the theory of relations,

• universal algebra and multi-valued logic,

as well as their applications in various areas of mathematics and computer science.

ALGOS 2020⁽<fnref n="1" />⁾ was to take place Wednesday August 26 through Friday August 28, 2020, at the Lorraine Research Laboratory in Computer Science and its Applications (LORIA), with support from University of Lorraine, CNRS and INRIA. Due to the COVID-19 pandemic, the conference was held online with a BigBlueButton platform provided by IRISA⁽<fnref n="2" />⁾.

<footnote n="1">¹ Université de Lorraine, CNRS, LORIA, Nancy, France</footnote>

<footnote n="2">² INESC-ID, Instituto Superior Técnico, Universidade de Lisboa, Portugal</footnote>

<footnote n="3">³ Department of Mathematics, Khalifa University, P.O. Box 127788, Abu Dhabi, United Arab Emirates</footnote>

<footnote n="4">⁴ Université Côte d'Azur, Inria, CNRS, I3S, Sophia-Antipolis, France</footnote>

<footnote>⁽¹⁾ https://algos2020.loria.fr</footnote>

<footnote>⁽ii⁾ Institut de Recherche en Informatique et Systèmes Aléatoires</footnote>
## 2 Contributions

This volume dedicated to the memory of the late Professor Maurice Pouzet (1943–2023) comprises eleven
contributions that pertain to the various research interests of Maurice Pouzet.

The first, *The algebra of binary trees is affine complete* is by André Arnold, Patrick Cégielski, Serge Grigorieff, and Irène Guessarian. The authors consider an algebra of binary trees whose leaves are labeled by letters of an alphabet with at least three letters, and show that a function is congruence preserving on such an algebra if and only if it is polynomial, which constitutes the first example of a non-commutative and non-associative affine complete algebra.

The second, *Polymorphism-homogeneity and universal algebraic geometry* is by Endre Tóth and Tamás Waldhauser, in which they study the polymorphism-homogeneity property. In particular, they show that a relational structure assigned to any finite algebra in a canonical way is polymorphism-homogeneous if and only if the algebra is polymorphism-homogeneous. They also demonstrate that polymorphism-homogeneity is equivalent to the property of algebraic sets being exactly the sets of tuples closed under the centralizer clone of the algebra. They determine that the two previous properties hold if and only if the algebra is injective in the category of its finite subpowers.

The third, *Graphs containing finite induced paths of unbounded length*, is by Maurice Pouzet and Imed Zaguia. Using uniformly recurrent sequences and lexicographical sums of labeled graphs, they construct $2^{\aleph_0}$ path-minimal graphs whose ages are pairwise incomparable with set inclusion and well-quasi-ordered.

The fourth, *Universal Horn sentences and the joint embedding property*, is by Manuel Bodirsky, Jakub Rydval, and André Schrottenloher. This paper concerns aspects of the following decision problem: Given a universal sentence $\Phi$ in a finite relational signature, does the class $[\Phi]^{<\omega}$ of all finite models of $\Phi$ have the joint embedding property? By a classical result of Fraïssé, $[\Phi]^{<\omega}$ is the age of some relational structure if and only if $[\Phi]^{<\omega}$ has the joint embedding property. In 2019, Braunfeld proved the undecidability of this problem. It is shown in this paper that this decision problem remains undecidable even in the special case when the signature contains only binary symbols and the universal sentence $\Phi$ is additionally Horn.

The fifth, *On the Boolean dimension of a graph and other related parameters*, is by Maurice Pouzet, Hamza Si Kaddour, and Bhalchandra Thatte. The main focus of this paper is on the somewhat recently introduced Boolean dimension of graphs. Three other well-established notions of dimensions are also considered: the inner, geometric, and symplectic dimensions. In the case when the Boolean dimension is finite, the possible relationships between these four different dimensions are described; in particular, the Boolean and inner dimensions coincide in this case. The authors discover an exact formula for the Boolean dimension of a tree in terms of star decompositions. Finally, the relationship between the inversion index of tournaments and the Boolean dimension of graphs is discussed.

The sixth, *Induced betweenness in order-theoretic trees*, is by Bruno Courcelle. In his earlier work, the author showed that the class **BO** of betweenness structures of countable order-theoretic forests is monadic second-order definable. It was left as a conjecture that the class **IBO** of induced substructures of the structures in **BO** is monadic second-order definable. This conjecture is proved in the current paper.
Moreover, it is shown that the class IBO is first-order definable, but a first-order defining sentence is not yet known.

The seventh, *Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs*,
is by Hanna Furmańczyk and Vahan Mkrtchyan. An *equitable colouring* of a graph is a vertex colouring
such that the sizes of any two colour classes differ by at most one. A graph in which each 2-connected
component is a complete graph is called a *block graph*. The problem of deciding whether a graph has
an equitable colouring with a given number of colours is NP-complete, and it remains hard even when
restricted to block graphs. In this paper, the authors investigate the parameterized complexity of the
equitable colouring problem of block graphs with respect to various parameters.

The eighth, *On the inversion number of oriented graphs*, is by Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, and Frédéric Havet. The authors consider oriented graphs and their inversion number, i.e., the minimum number of inversions needed to make them acyclic. They bound this number to the cycle transversal number, the cycle arc-transversal number, and the cycle packing number. They prove the conjecture that the inversion number of the dijoin of two graphs is the sum of their inversion numbers in some cases. They also study the complexity of deciding whether the inversion number of a graph is lower than *k*, and show that this problem is NP-complete for *k* = 1, which together with the above conjecture would imply that it is NP-complete for every *k*, contrasting with previous work.

The ninth, *Bijective proofs for Eulerian numbers of types B and D*, is by Luigi Santocanale. The author considered the Eulerian numbers in the type A (that counts number of permutations of *n* elements with *k* descents), type B (that counts the number of signed permutations of *n* elements with *k* type B descents), and in type D (that count the number of even signed permutations of *n* elements with *k* type D descents), and provides recursive forms for computing the latter two. He also considers a representation of signed permutations as paths, which he uses to provide enumerative results of threshold graphs.

The tenth, *Bounding the number of minimal transversals in tripartite 3-uniform hypergraphs*, is by
Alexandre Bazin, Laurent Beaudou, Giacomo Kahn, and Kaveh Khoshkhah. The authors focus on the
maximum number of minimal transversals in 3-partite 3-uniform hypergraphs on *n* vertices, and prove
that this number grows at least like 1.4977ⁿ and at most like 1.5012ⁿ.

The last contribution, *On graph rewriting systems termination through language theory*, is by Guil-laume Bonfante and Miguel Couceiro. The authors address a termination problem for graph rewriting systems that is rooted in Natural Language Processing (NLP), and which suffers from two main lim-itations: the large number of rewriting rules, and the lack of algebraic structure. To overcome these difficulties, the authors propose two orders on graphs that are stable under any context, namely, the ma-trix multiset-path order and the rational embedding order, which they use to show that a graph rewriting system is terminating if and only if it is compatible with a suitable notion of interpretation.
## 3 Acknowledgments

The editors would like to express their sincere thanks to the authors and reviewers of this volume in memory of Maurice Pouzet. We are also indebted to Jens Gustedt and the whole editorial team of the Discrete Mathematics & Theoretical Computer Science journal<sup>(iii)</sup> for their continuous help and support.

On a personal note, Miguel Couceiro had the honor of knowing Maurice as a close friend, and had the privilege of collaborating with him, sharing countless blissful moments in research. Not only was Maurice one of the greatest mathematicians of our time, with an immense scientific culture that he gladly shared with all his entourage, but he was a wonderful human being with an overwhelming heart.

Maurice, j'espère que tu t'es trompé et que tu nous regardes et vois à quel point tu nous manques...

Nancy, France

Abu Dhabi, United Arab Emirates

Sophia-Antipolis, France

Miguel Couceiro

Erkko Lehtonen

Pierre Monnin

<footnote>(iii) https://dmtcs.episciences.org/</footnote>