Special issues

Editors: Sergi Elizalde ; Christoph Haase ; Dieter Rautenbach ; Hadas Shachnai

A logical limit law for $231$-avoiding permutations

Michael Albert ; Mathilde Bouvel ; Valentin Féray ; Marc Noy.

We prove that the class of 231-avoiding permutations satisfies a logical limit law, i.e. that for any first-order sentence $\Psi$, in the language of two total orders, the probability $p_{n,\Psi}$ that a uniform random 231-avoiding permutation of size $n$ satisfies $\Psi$ admits a limit as $n$ is large. Moreover, we establish two further results about the behavior and value of $p_{n,\Psi}$: (i) it is either bounded away from $0$, or decays exponentially fast; (ii) the set of possible limits is dense in $[0,1]$. Our tools come mainly from analytic combinatorics and singularity analysis.

Hypergraphs with Polynomial Representation: Introducing $r$-splits

François Pitois ; Mohammed Haddad ; Hamida Seba ; Olivier Togni.

Inspired by the split decomposition of graphs and rank-width, we introduce the notion of $r$-splits. We focus on the family of $r$-splits of a graph of order $n$, and we prove that it forms a hypergraph with several properties. We prove that such hypergraphs can be represented using only $\mathcal O(n^{r+1})$ of its hyperedges, despite its potentially exponential number of hyperedges. We also prove that there exist hypergraphs that need at least $\Omega(n^r)$ hyperedges to be represented, using a generalization of set orthogonality.

Exactly Hittable Interval Graphs

S. M. Dhannya ; N. S. Narayanaswamy ; K. K. Nisha.

Given a set system $\mathcal{X} = \{\mathcal{U},\mathcal{S}\}$, where $\mathcal{U}$ is a set of elements and $\mathcal{S}$ is a set of subsets of $\mathcal{U}$, an exact hitting set $\mathcal{U}'$ is a subset of $\mathcal{U}$ such that each subset in $\mathcal{S}$ contains exactly one element in $\mathcal{U}'$. We refer to a set system as exactly hittable if it has an exact hitting set. In this paper, we study interval graphs which have intersection models that are exactly hittable. We refer to these interval graphs as exactly hittable interval graphs (EHIG). We present a forbidden structure characterization for EHIG. We also show that the class of proper interval graphs is a strict subclass of EHIG. Finally, we give an algorithm that runs in polynomial time to recognize graphs belonging to the class of EHIG.

(k − 2)-linear connected components in hypergraphs of rank k

Florian Galliot ; Sylvain Gravier ; Isabelle Sivignon.

We define a q-linear path in a hypergraph H as a sequence (e_1,...,e_L) of edges of H such that |e_i ∩ e_i+1 | ∈ [[1, q]] and e_i ∩ e_j = ∅ if |i − j| > 1. In this paper, we study the connected components associated to these paths when q = k − 2 where k is the rank of H. If k = 3 then q = 1 which coincides with the well-known notion of linear path or loose path. We describe the structure of the connected components, using an algorithmic proof which shows that the connected components can be computed in polynomial time. We then mention two consequences of our algorithmic result. The first one is that deciding the winner of the Maker-Breaker game on a hypergraph of rank 3 can be done in polynomial time. The second one is that tractable cases for the NP-complete problem of "Paths Avoiding Forbidden Pairs" in a graph can be deduced from the recognition of a special type of line graph of a hypergraph.

Minimal toughness in special graph classes

Gyula Y. Katona ; Kitti Varga.

Let $t$ be a positive real number. A graph is called $t$-tough if the removal of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$ components, and all graphs are considered 0-tough. The toughness of a graph is the largest $t$ for which the graph is $t$-tough, whereby the toughness of complete graphs is defined as infinity. A graph is minimally $t$-tough if the toughness of the graph is $t$, and the deletion of any edge from the graph decreases the toughness. In this paper, we investigate the minimum degree and the recognizability of minimally $t$-tough graphs in the classes of chordal graphs, split graphs, claw-free graphs, and $2K_2$-free graphs.

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.

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\cr k}\Bigr\rangle$, and $\Bigl\langle\matrix{D_n\cr k}\Bigr\rangle$ be the Eulerian numbers in the types A, B, and D, respectively -- that is, the number of permutations of n elements with $k$ descents, the number of signed permutations (of $n$ elements) with $k$ type B descents, the number of even signed 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 give bijective proofs of the identity $$B_n(t^2) = (1 + t)^{n+1}S_n(t) - 2^n tS_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 of signed permutations as paths. Using this representation we also establish a bijective 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 threshold graphs.

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$. The inversion number of $D$, denoted by ${\rm inv}(D)$, is the minimum number of inversions needed to make $D$ acyclic. Denoting by $\tau(D)$, $\tau' (D)$, and $\nu(D)$ the cycle transversal number, the cycle arc-transversal number and the cycle 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$ such that ${\rm inv}(D)\leq g(\nu(D))$. We conjecture that for any two oriented graphs $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 the first two inequalities are tight. We prove this conjecture when ${\rm inv}(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$ of the third inequality satisfies $g(1)\leq 4$. We then consider the complexity of deciding whether ${\rm inv}(D)\leq k$ for a given oriented graph $D$. We show that it is NP-complete for $k=1$, which together 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 that deciding whether ${\rm inv}(T)\leq k$ for a given tournament $T$ is polynomial-time solvable.

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. In this paper, we consider the equitable coloring problem in block graphs. Recall that the latter are graphs in which each 2-connected component is a complete graph. The problem remains hard in the class of block graphs. In this paper, we present some graph theoretic results relating various parameters. Then we use them in order to trace some algorithmic implications, mainly dealing with the fixed-parameter tractability of the problem.

Enumerating two permutation classes by the number of cycles

Kassie Archer.

We enumerate permutations in the two permutation classes $\text{Av}_n(312, 4321)$ and $\text{Av}_n(321, 4123)$ by the number of cycles each permutation admits. We also refine this enumeration with respect to several statistics.

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.

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

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 relational signature are the age of a structure if and only if $\Phi$ has the joint embedding property. We prove that the computational problem whether a given universal sentence $\Phi$ has the joint embedding property is undecidable, even if $\Phi$ is additionally Horn and the signature of $\Phi$ only contains relation symbols of arity at most two.

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 structure is polymorphism-homogeneous if and only if the algebra itself is polymorphism-homogeneous. We show that polymorphism-homogeneity is also equivalent to the property that algebraic sets (i.e., solution sets of systems of equations) are exactly those sets of tuples that are closed under the centralizer clone of the algebra. Furthermore, we prove that the aforementioned properties hold if and only if the algebra is injective in the category of its finite subpowers. We also consider two additional conditions: a stronger variant for polymorphism-homogeneity and for injectivity, and we describe explicitly the finite semilattices, lattices, Abelian groups and monounary algebras satisfying any one of these three conditions.

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 the collection of finite induced subgraphs of $G$, considered up to isomorphy and ordered by embeddability. It is well-quasi-ordered (wqo) for this order if it contains no infinite antichain. A graph is \emph{path-minimal} if it contains finite induced paths of unbounded length and every induced subgraph $G'$ with this property embeds $G$. We construct $2^{\aleph_0}$ path-minimal graphs whose ages are pairwise incomparable with set inclusion and which are wqo. Our construction is based on uniformly recurrent sequences and lexicographical sums of labelled graphs.

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, it maps pairs of congruent elements onto pairs of congruent elements. We show that on the algebra of binary trees whose leaves are labeled by letters of an alphabet containing at least three letters, a function is congruence preserving if and only if it is polynomial.

The undecidability of joint embedding for 3-dimensional permutation classes
Samuel Braunfeld.
As a step towards resolving a question of Ruškuc on the decidability of joint embedding for hereditary classes of permutations, which may be viewed as structures in a language of 2 linear orders, we show the corresponding problem is undecidable for hereditary classes of structures in a language of 3 linear orders.

Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations
Hanna Mularczyk.
Defant, Engen, and Miller defined a permutation to be uniquely sorted if it has exactly one preimage under West's stack-sorting map. We enumerate classes of uniquely sorted permutations that avoid a pattern of length three and a pattern of length four by establishing bijections between these classes and various lattice paths. This allows us to prove nine conjectures of Defant.

Two examples of Wilf-collapse
Michael Albert ; Vít Jelínek ; Michal Opler.
Two permutation classes, the X-class and subpermutations of the increasing oscillation are shown to exhibit an exponential Wilf-collapse. This means that the number of distinct enumerations of principal subclasses of each of these classes grows much more slowly than the class itself whereas a priori, based only on symmetries of the class, there is no reason to expect this. The underlying cause of the collapse in both cases is the ability to apply some form of local symmetry which, combined with a greedy algorithm for detecting patterns in these classes, yields a Wilf-collapse.

Enumeration of Dumont permutations avoiding certain four-letter patterns
Alexander Burstein ; Opel Jones.
In this paper, we enumerate Dumont permutations of the fourth kind avoiding or containing certain permutations of length 4. We also conjecture a Wilf-equivalence of two 4-letter patterns on Dumont permutations of the first kind.

Fillings of skew shapes avoiding diagonal patterns
Vít Jelínek ; Mark Karpilovskij.
A skew shape is the difference of two top-left justified Ferrers shapes sharing the same top-left corner. We study integer fillings of skew shapes. As our first main result, we show that for a specific hereditary class of skew shapes, which we call D-free shapes, the fillings that avoid a north-east chain of size $k$ are in bijection with fillings that avoid a south-east chain of the same size. Since Ferrers shapes are a subclass of D-free shapes, this result can be seen as a generalization of previous analogous results for Ferrers shapes. As our second main result, we construct a bijection between 01-fillings of an arbitrary skew shape that avoid a south-east chain of size 2, and the 01-fillings of the same shape that simultaneously avoid a north-east chain of size 2 and a particular non-square subfilling. This generalizes a previous result for transversal fillings.

Flip-sort and combinatorial aspects of pop-stack sorting
Andrei Asinowski ; Cyril Banderier ; Benjamin Hackl.
Flip-sort is a natural sorting procedure which raises fascinating combinatorial questions. It finds its roots in the seminal work of Knuth on stack-based sorting algorithms and leads to many links with permutation patterns. We present several structural, enumerative, and algorithmic results on permutations that need few (resp. many) iterations of this procedure to be sorted. In particular, we give the shape of the permutations after one iteration, and characterize several families of permutations related to the best and worst cases of flip-sort. En passant, we also give some links between pop-stack sorting, automata, and lattice paths, and introduce several tactics of bijective proofs which have their own interest.

Catalan words avoiding pairs of length three patterns
Jean-Luc Baril ; Carine Khalil ; Vincent Vajnovszki.
Catalan words are particular growth-restricted words counted by the eponymous integer sequence. In this article we consider Catalan words avoiding a pair of patterns of length 3, pursuing the recent initiating work of the first and last authors and of S. Kirgizov where (among other things) the enumeration of Catalan words avoiding a patterns of length 3 is completed. More precisely, we explore systematically the structural properties of the sets of words under consideration and give enumerating results by means of recursive decomposition, constructive bijections or bivariate generating functions with respect to the length and descent number. Some of the obtained enumerating sequences are known, and thus the corresponding results establish new combinatorial interpretations for them.

Enumeration of Permutation Classes and Weighted Labelled Independent Sets
Christian Bean ; Émile Nadeau ; Henning Ulfarsson.
In this paper, we study the staircase encoding of permutations, which maps a permutation to a staircase grid with cells filled with permutations. We consider many cases, where restricted to a permutation class, the staircase encoding becomes a bijection to its image. We describe the image of those restrictions using independent sets of graphs weighted with permutations. We derive the generating function for the independent sets and then for their weighted counterparts. The bijections we establish provide the enumeration of permutation classes. We use our results to uncover some unbalanced Wilf-equivalences of permutation classes and outline how to do random sampling in the permutation classes. In particular, we cover the classes $\mathrm{Av}(2314,3124)$, $\mathrm{Av}(2413,3142)$, $\mathrm{Av}(2413,3124)$, $\mathrm{Av}(2413,2134)$ and $\mathrm{Av}(2314,2143)$, as well as many subclasses.

Bounded affine permutations I. Pattern avoidance and enumeration
Neal Madras ; Justin M. Troyka.
We introduce a new boundedness condition for affine permutations, motivated by the fruitful concept of periodic boundary conditions in statistical physics. We study pattern avoidance in bounded affine permutations. In particular, we show that if $\tau$ is one of the finite increasing oscillations, then every $\tau$-avoiding affine permutation satisfies the boundedness condition. We also explore the enumeration of pattern-avoiding affine permutations that can be decomposed into blocks, using analytic methods to relate their exact and asymptotic enumeration to that of the underlying ordinary permutations. Finally, we perform exact and asymptotic enumeration of the set of all bounded affine permutations of size $n$. A companion paper will focus on avoidance of monotone decreasing patterns in bounded affine permutations.

Unary profile of lambda terms with restricted De Bruijn indices
Katarzyna Grygiel ; Isabella Larcher.
In this paper we present an average-case analysis of closed lambda terms with restricted values of De Bruijn indices in the model where each occurrence of a variable contributes one to the size. Given a fixed integer k, a lambda term in which all De Bruijn indices are bounded by k has the following shape: It starts with k De Bruijn levels, forming the so-called hat of the term, to which some number of k-colored Motzkin trees are attached. By means of analytic combinatorics, we show that the size of this hat is constant on average and that the average number of De Bruijn levels of k-colored Motzkin trees of size n is asymptotically Θ(√ n). Combining these two facts, we conclude that the maximal non-empty De Bruijn level in a lambda term with restrictions on De Bruijn indices and of size n is, on average, also of order √ n. On this basis, we provide the average unary profile of such lambda terms.

Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency
OLivier Bodini ; Matthieu Dien ; Antoine Genitrini ; Frédéric Peschanski.
In this paper we address the problem of understanding Concurrency Theory from a combinatorial point of view. We are interested in quantitative results and algorithmic tools to refine our understanding of the classical combinatorial explosion phenomenon arising in concurrency. This paper is essentially focusing on the the notion of synchronization from the point of view of combinatorics. As a first step, we address the quantitative problem of counting the number of executions of simple processes interacting with synchronization barriers. We elaborate a systematic decomposition of processes that produces a symbolic integral formula to solve the problem. Based on this procedure, we develop a generic algorithm to generate process executions uniformly at random. For some interesting sub-classes of processes we propose very efficient counting and random sampling algorithms. All these algorithms have one important characteristic in common: they work on the control graph of processes and thus do not require the explicit construction of the state-space.