We denote the proportion of consecutive patterns \(\pi\) in a permutation \(\sigma\) as
\(\widetilde{\text{c$-$}occ}(\pi, \sigma^m ) =\frac{\text{# of consecutive occurrences of $\pi$ in $\sigma$}}{|\sigma|}.\)We consider the consecutive pattern limiting sets, called the feasible region for consecutive patterns, defined for every \(k\in\mathbb{N}\)
\(P_k := \left\{\vec{v}\in [0,1]^{\mathcal{S}_k} \big| \exists (\sigma^m)_{m\in\mathbb{N}} \in \mathcal{S}^{\mathbb{N}} \text{ s.t. }|\sigma^m| \to\infty \text{ and } \widetilde{\text{c$-$}occ}(\pi, \sigma^m ) \to \vec{v}_{\pi}, \forall \pi\in\mathcal{S}_k \right\}.\)
We are able to obtain a full description of the feasible region \(P_k\) as the cycle polytope of a specific graph, called the overlap graph \(Ov(k)\).
Definition: The graph \(Ov(k)\) is a directed multigraph with labeled edges, where the vertices are elements of \(\mathcal{S}_{k-1}\) and for every \(\pi\in\mathcal{S}_{k}\) there is an edge labeled by \(\pi\) from the pattern induced by the first \(k-1\) indices of \(\pi\) to the pattern induced by the last \(k-1\) indices of \(\pi\).
We display here below the overlap graph \(Ov(4)\): the six vertices of the graph are painted in red and the edges are drawn as labeled arrows. Note that in order to obtain a clearer picture we did not draw multiple edges, but we use multiple labels (for example the edge from 231 to 312 is labeled with the permutations 3412 and 2413 and should be thought of as two distinct edges labeled with 3412 and 2413 respectively).
Definition: Let \(G=(V,E)\) be a directed multigraph. For each non-empty cycle \(\mathcal{C} \) in \(G \), define \(\vec{e}_{\mathcal{C}}\in \mathbb{R}^{E} \) so that
\((\vec{e}_{\mathcal{C}})_e := \frac{\text{# of occurrences of $e$ in $\mathcal{C}$}}{|\mathcal{C}|}, \quad \text{for all}\quad e\in E. \)
We define the cycle polytope of \(G \) to be the polytope \(P(G) := \text{conv} \{\vec{e}_{\mathcal{C}} | \, \mathcal{C} \text{ is a simple cycle of } G \} \).
Our first main result is the following.
Theorem: \(P_k \) is the cycle polytope of the overlap graph \(Ov(k) \). Its dimension is \(k! – (k-1)! \) and its vertices are given by the simple cycles of \(Ov(k) \). In addition, we also determine the equations that describe the polytope.
In the picture below you can see the four-dimensional polytope \(P_3\) given by the six patterns of size three. We highlight in light-blue one of the six three-dimensional facets of \(P_3\). This facet is a pyramid with square base. The polytope itself is a four-dimensional pyramid, whose base is the highlighted facet.
In order to prove the above theorem, we first prove general results for cycle polytopes of directed multigraphs and then we transfer them to the specific case of overlap graphs. Specifically, we are able to prove the following.
Theorem: The cycle polytope of a strongly connected directed multigraph \(G=(V,E)\) has dimension \(|E|-|V|\). We also determine the equations defining the polytope and we show that all its faces can be identified with some specific subgraphs of \(G \). This gives us a description of the face poset of the polytope.
Further, the computation of the dimension is generalized for any cycle polytope, even those that do not come from strongly connected graphs.
In the following picture we display the face structure of the cycle polytope of a graph. On the left-hand side of the picture (inside the dashed black ball) we have a graph G with two vertices and five edges. On the right-hand side, we draw the associated cycle polytope P(G) that is a pyramid with squared base. The blue dashed balls correspond to the simple cycles corresponding to the five vertices of the polytope. We also underline the relation between two edges of the polytope (in purple and orange respectively) and a face (in green) and the corresponding subgraphs. Note that, for example, the graph corresponding to the green face is just the union of the three graphs corresponding to the vertices of that face.
Published version (Algebraic Combinatorics)
An extended abstract of this work is available at this page.