vol. 23 no. 2, special issue in honour of Maurice Pouzet


1. The algebra of binary trees is affine complete

Andre Arnold ; Patrick Cegielski ; Serge Grigorieff ; Irene Guessarian.
A function on an algebra is congruence preserving if, for any congruence, itmaps pairs of congruent elements onto pairs of congruent elements. We show thaton the algebra of binary trees whose leaves are labeled by letters of analphabet containing at least three letters, a function is congruence preservingif and only if it is polynomial.

2. Polymorphism-homogeneity and universal algebraic geometry

Endre Tóth ; Tamás Waldhauser.
We assign a relational structure to any finite algebra in a canonical way,using solution sets of equations, and we prove that this relational structureis polymorphism-homogeneous if and only if the algebra itself ispolymorphism-homogeneous. We show that polymorphism-homogeneity is alsoequivalent to the property that algebraic sets (i.e., solution sets of systemsof equations) are exactly those sets of tuples that are closed under thecentralizer clone of the algebra. Furthermore, we prove that the aforementionedproperties hold if and only if the algebra is injective in the category of itsfinite subpowers. We also consider two additional conditions: a strongervariant for polymorphism-homogeneity and for injectivity, and we describeexplicitly the finite semilattices, lattices, Abelian groups and monounaryalgebras satisfying any one of these three conditions.

3. Graphs containing finite induced paths of unbounded length

Maurice Pouzet ; Imed Zaguia.
The age $\mathcal{A}(G)$ of a graph $G$ (undirected and without loops) is thecollection of finite induced subgraphs of $G$, considered up to isomorphy andordered by embeddability. It is well-quasi-ordered (wqo) for this order if itcontains no infinite antichain. A graph is \emph{path-minimal} if it containsfinite induced paths of unbounded length and every induced subgraph $G'$ withthis property embeds $G$. We construct $2^{\aleph_0}$ path-minimal graphs whoseages are pairwise incomparable with set inclusion and which are wqo. Ourconstruction is based on uniformly recurrent sequences and lexicographical sumsof labelled graphs.

4. Universal Horn Sentences and the Joint Embedding Property

Manuel Bodirsky ; Jakub Rydval ; André Schrottenloher.
The finite models of a universal sentence $\Phi$ in a finite relationalsignature are the age of a structure if and only if $\Phi$ has the jointembedding property. We prove that the computational problem whether a givenuniversal sentence $\Phi$ has the joint embedding property is undecidable, evenif $\Phi$ is additionally Horn and the signature of $\Phi$ only containsrelation symbols of arity at most two.

5. On the Boolean dimension of a graph and other related parameters

Maurice Pouzet ; Hamza Si Kaddour ; Bhalchandra Thatte.
We present the Boolean dimension of a graph, we relate it with the notions of inner, geometric and symplectic dimensions, and with the rank and minrank of a graph. We obtain an exact formula for the Boolean dimension of a tree in terms of a certain star decomposition. We relate the Boolean dimension with the inversion index of a tournament.

6. Induced betweenness in order-theoretic trees

Bruno Courcelle.
The ternary relation B(x,y,z) of betweenness states that an element y is between the elements x and z, in some sense depending on the considered structure. In a partially ordered set (N,≤), B(x,y,z):⇔x<y<z∨z<y<x, and the corresponding betweenness structure is (N,B). The class of betweenness structures of linear orders is first-order definable. That of partial orders is monadic second-order definable. An order-theoretic tree is a partial order such that the set of elements larger that any element is linearly ordered and any two elements have an upper-bound. Finite or infinite rooted trees ordered by the ancestor relation are order-theoretic trees. In an order-theoretic tree, B(x,y,z) means that x<y<z or z<y<x or x<y≤x⊔z or z<y≤x⊔z, where x⊔z is the least upper-bound of incomparable elements x and z. In a previous article, we established that the corresponding class of betweenness structures is monadic second-order definable.We prove here that the induced substructures of the betweenness structures of the countable order-theoretic trees form a monadic second-order definable class, denoted by IBO. The proof uses a variant of cographs, the partitioned probe cographs, and their known six finite minimal excluded induced subgraphs called the bounds of the class. This proof links two apparently unrelated topics: cographs and order-theoretic trees.However, the class IBO has finitely many bounds, i.e., minimal excluded finite induced […]

7. Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs

Hanna Furmańczyk ; Vahan Mkrtchyan.
An equitable coloring of a graph $G=(V,E)$ is a (proper) vertex-coloring of$G$, such that the sizes of any two color classes differ by at most one. Inthis paper, we consider the equitable coloring problem in block graphs. Recallthat the latter are graphs in which each 2-connected component is a completegraph. The problem remains hard in the class of block graphs. In this paper, wepresent some graph theoretic results relating various parameters. Then we usethem in order to trace some algorithmic implications, mainly dealing with thefixed-parameter tractability of the problem.

8. On the inversion number of oriented graphs

Jørgen Bang-Jensen ; Jonas Costa Ferreira da Silva ; Frédéric Havet.
Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$consists in reversing the direction of all arcs with both ends in $X$. Theinversion number of $D$, denoted by ${\rm inv}(D)$, is the minimum number ofinversions needed to make $D$ acyclic. Denoting by $\tau(D)$, $\tau' (D)$, and$\nu(D)$ the cycle transversal number, the cycle arc-transversal number and thecycle packing number of $D$ respectively, one shows that ${\rm inv}(D) \leq\tau' (D)$, ${\rm inv}(D) \leq 2\tau(D)$ and there exists a function $g$ suchthat ${\rm inv}(D)\leq g(\nu(D))$. We conjecture that for any two orientedgraphs $L$ and $R$, ${\rm inv}(L\rightarrow R) ={\rm inv}(L) +{\rm inv}(R)$where $L\rightarrow R$ is the dijoin of $L$ and $R$. This would imply that thefirst two inequalities are tight. We prove this conjecture when ${\rminv}(L)\leq 1$ and ${\rm inv}(R)\leq 2$ and when ${\rm inv}(L) ={\rm inv}(R)=2$and $L$ and $R$ are strongly connected. We also show that the function $g$ ofthe third inequality satisfies $g(1)\leq 4$. We then consider the complexity of deciding whether ${\rm inv}(D)\leq k$ fora given oriented graph $D$. We show that it is NP-complete for $k=1$, whichtogether with the above conjecture would imply that it is NP-complete for every$k$. This contrasts with a result of Belkhechine et al. which states thatdeciding whether ${\rm inv}(T)\leq k$ for a given tournament $T$ ispolynomial-time solvable.

9. Bijective proofs for Eulerian numbers of types B and D

Luigi Santocanale.
Let $\Bigl\langle\matrix{n\cr k}\Bigr\rangle$, $\Bigl\langle\matrix{B_n\crk}\Bigr\rangle$, and $\Bigl\langle\matrix{D_n\cr k}\Bigr\rangle$ be theEulerian numbers in the types A, B, and D, respectively -- that is, the numberof permutations of n elements with $k$ descents, the number of signedpermutations (of $n$ elements) with $k$ type B descents, the number of evensigned permutations (of $n$ elements) with $k$ type D descents. Let $S_n(t) =\sum_{k = 0}^{n-1} \Bigl\langle\matrix{n\cr k}\Bigr\rangle t^k$, $B_n(t) =\sum_{k = 0}^n \Bigl\langle\matrix{B_n\cr k}\Bigr\rangle t^k$, and $D_n(t) =\sum_{k = 0}^n \Bigl\langle\matrix{D_n\cr k}\Bigr\rangle t^k$. We givebijective proofs of the identity $$B_n(t^2) = (1 + t)^{n+1}S_n(t) - 2^ntS_n(t^2)$$ and of Stembridge's identity $$D_n(t) = B_n(t) -n2^{n-1}tS_{n-1}(t).$$ These bijective proofs rely on a representation ofsigned permutations as paths. Using this representation we also establish abijective correspondence between even signed permutations and pairs $(w, E)$with $([n], E)$ a threshold graph and $w$ a degree ordering of $([n], E)$,which we use to obtain bijective proofs of enumerative results for thresholdgraphs.

10. Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs

Alexandre Bazin ; Laurent Beaudou ; Giacomo Kahn ; Kaveh Khoshkhah.
We focus on the maximum number of minimal transversals in 3-partite 3-uniform hypergraphs on n vertices. Those hypergraphs (and their minimal transversals) are commonly found in database applications. In this paper we prove that this number grows at least like 1.4977^n and at most like 1.5012^n.