The feasible region for consecutive patterns of permutations is a cycle polytope
Jacopo Borga Raul Penaguiao
math.CO math.PR


[NO \title GIVEN]
    [NO \author GIVEN]
    December 30, 2023
======================



This is a shorter version of the preprint <cit.> that is currently submitted to a journal.
Many proofs and details omitted here can be found in <cit.>.









§ INTRODUCTION





 §.§ Motivations




Despite not presenting any probabilistic result here, we give some motivations that come from the study of random permutations.
This is a classical topic at the interface of combinatorics and discrete probability theory. There are two main approaches to it: the first concerns the study of statistics on permutations, and the second, more recent, looks for the limits of permutations themselves. The two approaches are not orthogonal and many results relate them, for instance <ref> below.  

In order to study the limit of permutations, two main notions of convergence have been defined: a global notion of convergence (called permuton convergence) and a local notion of convergence (called Benjamini–Schramm convergence, or BS-convergence, for short).
A permuton is a probability measure on the unit square with uniform marginals.
The notion of permuton limit for permutations has been introduced in <cit.>, and represents the scaling limit of a permutation seen as a permutation matrix, as the size grows to infinity. The study of permuton limits is an active and exciting research field in combinatorics, see for instance <cit.> and references therein.
On the other hand, the notion of BS-limit for permutations is more recent, and it has been introduced in <cit.>. 
Informally, in order to investigate BS-limits, we study the permutation in a neighborhood around a randomly marked point in its one-line notation. Limiting objects for this framework are called infinite rooted permutations and are in bijection with total orders on the set of integer numbers. 
BS-limits have also been studied in some other works, see for instance <cit.>.

Let n∈=_>0. We denote by 𝒮_n the set of permutations of size n, and by  the set of all permutations.
We recall the definition of patterns for permutations. For σ∈_n, π∈_k and a subsequence 1≤ i_1 < … < i_k≤ n, we say that σ(i_1) …σ(i_k) is an occurrence of π in σ, if σ(i_1) …σ(i_k) has the same relative order as π. If the indices i_1, … ,i_k form an interval, then we say that σ(i_1) …σ(i_k) is a consecutive occurrence of π in σ.
We denote by (π,σ) (resp. by (π,σ)) the number of occurrences (resp. consecutive occurrences) of a pattern π in σ.
For example, if π = 132 and σ = 72638145, we have that (π,σ) = 7 and (π,σ) = 1.
We also denote by (π,σ) (resp. (π,σ)) the proportion of classical occurrences (resp. consecutive occurrences) of a permutation π∈_k in σ∈_n, that is 

    (π,σ)(π,σ)/nk∈[0,1] ,     (π,σ)(π,σ)/n∈[0,1]  .

The following theorems provide relevant combinatorial characterizations of the two aforementioned notions of convergence for permutations.


	For any n∈, let σ^n∈ and assume that |σ^n|→∞. The sequence (σ^n)_n∈ converges to some permuton P if and only if there exists a vector (Δ_π(P))_π∈𝒮 of non-negative real numbers (that depends on P) such that, for all π∈𝒮,
	
    (π,σ^n)→Δ_π(P).





	For any n∈, let σ^n∈ and assume that |σ^n|→∞. The sequence (σ^n)_n∈ converges in the Benjamini–Schramm topology to some random infinite rooted permutation σ^∞ if and only if there exists a vector (Γ_π(σ^∞))_π∈𝒮 of non-negative real numbers (that depends on σ^∞) such that, for all π∈𝒮,
	
    (π,σ^n)→Γ_π(σ^∞).





A natural question, motivated by the theorems above, is the following: given a finite family of patterns 𝒜⊆ and a vector (Δ_π)_π∈𝒜∈ [0,1]^𝒜, or (Γ_π)_π∈𝒜∈ [0,1]^𝒜, does there exist a sequence of permutations (σ^n)_n∈ such that |σ^n|→∞ and

    (π,σ^n)→Δ_π,   for all  π∈𝒜,

or

    (π,σ^n)→Γ_π,   for all  π∈𝒜 ?


We consider the classical pattern limiting sets, sometimes called the feasible region for (classical) patterns, defined as

    clP_k    {v⃗∈ [0,1]^_k| ∃ (σ^m)_m∈∈^ s.t. |σ^m| →∞ and (π, σ^m ) →v⃗_π,∀π∈_k  }
    
    =   {(Δ_π(P))_π∈_k| P is a permuton}  ,

and we introduce the consecutive pattern limiting sets, called here the feasible region for consecutive patterns,

    P_k    {v⃗∈ [0,1]^_k| ∃ (σ^m)_m∈∈^ s.t. |σ^m| →∞ and (π, σ^m ) →v⃗_π, ∀π∈_k }
    
    =   {(Γ_π(σ^∞))_π∈_k| σ^∞ is a random infinite rooted shift-invariant permutation}  .


For the precise definition of shift-invariant permutations see <cit.>. The equalities in (<ref>) and (<ref>) follow from <cit.> and <cit.> respectively.

The feasible region clP_k was previously studied in several papers (see <ref>). 
The main goal of this project is to analyze the feasible region P_k, that turns out to be related to specific graphs called overlap graphs (see <ref>) and its corresponding cycle polytope (see <ref>).
In particular, the feasible region P_k is convex.
This is not in general true for the region clP_k.



 §.§ Definitions and informal statement of the main results


To introduce our main results we need two key definitions.


	
	The overlap graph [k] is a directed multigraph with labeled edges, where the vertices are elements of _k-1 and for every π∈_k there is an edge labeled by π from the pattern induced by the first k-1 indices of π to the pattern induced by the last k-1 indices of π.


The overlap graphs  [3] and [4] are displayed in <ref> and <ref> respectively.




We denote the convex hull of a family ℱ of points by ℱ.
A non-empty cycle 𝒞 in a directed multigraph is said to be a simple cycle if it does not repeat vertices.


	
	Let G=(V,E) be a directed multigraph.
	For each non-empty cycle 𝒞 in G, define e⃗_𝒞∈ℝ^E so that
	
    (e⃗_𝒞)_e number of occurrences of e in /|𝒞|,   for all   e∈ E.

	We define the cycle polytope of G to be P(G) {e⃗_𝒞 |  𝒞 is a simple cycle of  G }.


The example of the cycle polytope P([3]) is given in <ref>.



Our first result is a full description of the feasible region P_k as the cycle polytope of the overlap graph [k] (see <ref>). 



The second result deals with the dimension and the equations that define the cycle polytope of a general directed multigraph (see <ref>) and a description of the associated face poset (see <ref>).
From this theorem, the dimension and the equations of P_k can be directly computed.

Our last result addresses a slightly different question. We intertwine the notions of classical patterns and consecutive patterns, and discuss the shape of the resulting feasible region. 
In <ref>, we reduce the description of this new feasible region to the independent descriptions of the feasible regions for pattens and consecutive patterns discussed in <ref>.



 §.§ State-of-the-art and a conjecture





  §.§.§ The feasible region for classical patterns


The feasible region clP_k was first studied in <cit.> for some particular families of patterns instead of the whole _k. The authors specifically studied patterns of small size (2 or 3) showing that, already in these cases, the problem of describing the associated feasible region presents a lot of difficulties. They also showed that this region is not always convex (see for instance <cit.>).



The set clP_k was also studied in <cit.>, even though with a different objective.
There, it was shown that clP_k contains an open ball B with dimension |I_k|, where I_k is the set of permutations of size at most k that are ⊕-indecomposable.
Specifically, for a particular ball B⊆^I_k, the authors constructed permutons P_x⃗ such that Δ_π(P_x⃗) = x⃗_π, for each point x⃗∈ B and each π∈ I_k.

The work done in <cit.> opened the problem of finding the maximal dimension of an open ball contained in clP_k, and placed a lower bound on it.
In <cit.> an upper bound for this maximal dimension is indirectly given as the number of so-called Lyndon permutations of size at most k, whose set we denote ℒ_k.
The author shows that for any permutation π that is not a Lyndon permutation, (π, σ ) can be expressed as a polynomial on the functions {(τ, σ ) |τ∈ℒ_k } that does not depend on σ.
It follows that clP_k sits inside an algebraic variety of dimension |ℒ_k|.
We expect that this bound is sharp since this is the case for small values of k.


The feasible region clP_k is full-dimensional inside a manifold of dimension |ℒ_k|.








  §.§.§ Overlap graphs


Overlap graphs were already studied in previous works. We give here a brief summary of the relevant literature. The overlap graph [k] is the line graph of the de Bruijn graph for permutations of size k-1. The latter was introduced in <cit.> and further studied in <cit.>, where the authors studied universal cycles (sometime also called de Bruijn cycles) of several combinatorial structures, including permutations. 
In this case, a universal cycle of order n is a cyclic word of size n! on an ordered alphabet of N letters that contains all the patterns of size n as consecutive patterns. In <cit.> it was conjectured (and then proved in <cit.>) that such universal cycles always exist when the alphabet is of size N=n+1. 
In <cit.> the authors enumerate some families of simple cycles of these graphs.
This starts the undertaking of describing all simple cycles of a explicit de Bruijn graph.
As a consequence, this also gives a description of the vertices of the corresponding cycle polytope.

The existence of Eulerian and Hamiltonian cycles in classical de Bruijn graphs is shown in <cit.>.
We remark that applying the same ideas, we can prove the existence of both Eulerian and Hamiltonian cycles in [k].
We further remark that with an Eulerian path in [k], we can construct a permutation σ of size k!+k -1 such that (π,  σ ) = 1 for any π∈_k.
This is a so-called “superpermutation” of minimal size for consecutive patterns.



  §.§.§ Polytopes and cycle polytopes



Polytopes associated to graphs have been objects of research for a long time in computer science and graph theory.
A striking example is the flow polytope, introduced in <cit.>.
This is a polytope that is associated to a root system and a flow vector.
If we specifically take a root system of type A_n, this can be described by an undirected graph on [n]{1,…,n}: in this way, if we are given a graph G=([n], E) and a flow vector a⃗∈^n, its corresponding flow polytope is in fact defined as

    ℱ_G(a⃗ ) {x⃗∈^E| ∑_{j <i}∈ Ex⃗_{j <i} - ∑_{i <j}∈ Ex⃗_{i <j} = a⃗_i,   i ∈ [n] }  .



Classical examples of polytopes that are flow polytopes are the Stanley–Pitman polytope, also called the parking function polytope, and the 
Chan–Robbins–Yuen polytope, a polytope on the space of doubly stochastic square matrices.
In <cit.>, the authors obtain formulas for the volume and the number of integer points in its interior.
In particular, they recover a formula for the volume of the Chan–Robbins–Yuen polytope, due to Zeilberger, in his very short paper <cit.>.



In <cit.> and in <cit.>, unrescaled cycle polytopes (U-cycle polytopes for short)[The U-cycle polytopes and the cycle polytopes introduced in <ref> are intrinsically related to one another, as the vertices of the U-cycle polytope of a directed multigraph G are defined as the incidence vectors of simple cycles of G. In <ref>, we additionally rescale each of the vertices so that the coordinates sum up to one. The U-cycle polytopes were considered in the literature simply under the name of cycle polytopes. However, here, we adopt the name of cycle polytopes to our family of polytopes for the sake of simplifying the terminology in this extended abstract.] were introduced.
The U-cycle polytopes for undirected graphs were considered to tackle the Simple Cycle Problem <cit.>, that also goes by the name of Weighted Girth Problem <cit.>. 
Balas & Oosten <cit.> and Balas & Stephan <cit.> compute the dimension of the U-cycle polytope of the complete graph (that is, the complete directed graph without loops) and describe the faces of co-dimension one of the corresponding polytope.
In comparison, we study and give a dimension theorem for cycle polytopes (instead of U-cycle polytopes) for general directed multigraphs (not restricting to the case of complete graphs). Our results extend some results of Gleiss, Leydold and Stadler <cit.>.




§ FIRST MAIN RESULT: DESCRIPTION OF THE FEASIBLE REGION

Our first main result is the following.


	
	P_k is the cycle polytope of the overlap graph [k]. Its dimension is k! - (k-1)! and its vertices are given by the simple cycles of [k].


In addition, we can also determine the equations that describe the polytope P_k (for that see <cit.>).



To establish that P_k=P([k]), the first step is the following result.


	
	The feasible region P_k is convex.



	Since P_k is closed (this is an easy consequence of the fact that P_k is a set of limit points) it is enough to consider rational convex combinations of points in P_k, i.e. it is enough to establish that for all v⃗_1,v⃗_2∈ P_k and all s,t∈, we have that
	
    s/s+tv⃗_1+t/s+tv⃗_2∈ P_k.

	For σ∈, we define the vector _k( σ)  ((π,σ))_π∈_k. Fix v⃗_1,v⃗_2∈ P_k and s,t∈. Since v⃗_1,v⃗_2∈ P_k, there exist two sequences (σ^m_1)_m∈, (σ^m_2)_m∈ such that |σ^m_i|m→∞⟶∞ and _k( σ^m_i)m→∞⟶v⃗_i, for i=1,2.
	
	Define t_m t· |σ^m_1| and s_m s· |σ^m_2| and set τ^m to be equal to the direct sum[For τ∈_m and σ∈_n, the direct sum of τ and σ is the permutation  τ(1)…τ(m)(σ(1) + m)…(σ(n)+m).] of s_m copies of σ_1^m and t_m copies of σ_2^m.
	
	We note that for every π∈_k, we have
	
    (π,τ^m)=s_m·(π,σ^m_1)+t_m·(π,σ^m_2)+Er,

	where Er≤(s_m+t_m-1)· |π|. This error term comes from the number of intervals of size |π| that intersect the boundary of some copies of σ^m_1 or σ^m_2. Hence
	
    (π,τ^m)   =s_m·|σ^m_1|·(π,σ^m_1)+t_m·|σ^m_2|·(π,σ^m_2)+Er/s_m·|σ^m_1|+t_m· |σ^m_2|
       =s/s+t(π,σ^m_1)+t/s+t(π,σ^m_2)+O(|π|(1|σ^m_1|+1|σ^m_2|)).

	As m tends to infinity, we have 
    _k(τ^m)→s/s+tv⃗_1+t/s+tv⃗_2,
 
	since |σ^m_i|m→∞⟶∞ and _k( σ^m_i)m→∞⟶v⃗_i, for i=1,2. Noting also that
	
    |τ^m|→∞,

	we can conclude that ss+tv⃗_1+ts+tv⃗_2∈ P_k. This ends the proof.


Using <ref> we can show that P_k=P([k]) using a surjective correspondence between permutations of size m+k-1 and walks of length m in the overlap graph [k].
This correspondence is built in such a way that the vertices on the walk are in bijection with the consecutive patterns of size k appearing in the corresponding permutation (for that we refer to <cit.>).

We use this correspondence as follows.
First we show that P([k])⊆ P_k: Thanks to <ref> it is enough to show that for each simple cycle 𝒞∈[k], the vector e⃗_𝒞 belongs to P_k. For that we consider the sequence of walks (w_m)_m∈ obtained concatenating m copies of 𝒞, and we show that a corresponding sequence of permutations (σ^m)_m≥ 1 satisfies _k(σ^m) →e⃗_𝒞.
Second we show that P_k⊆ P([k]): For any vector v⃗∈ P_k, we consider a sequence of permutations (σ^m)_m∈ such that _k(σ^m)→v⃗. This sequence of permutations corresponds to a sequence of walks in [k].
By decomposing each of these walks into simple cycles (plus a small tail) we show that the original vector v⃗ is arbitrarily close to P([k]).

Finally, the result on the dimension, the description of the vertices and the equations describing P_k are a consequence of general results for cycle polytopes (see details for the computation of the dimension in <ref>, and for the remaining features in <cit.>).



§ SECOND MAIN RESULT: DIMENSION AND FACES OF CYCLE POLYTOPES



In <cit.>, we establish a full description of the cycle polytope of a general directed multigraph (see <ref> below) and of its face poset (see <ref> below).
We give here these descriptions omitting the proofs.

We say that a directed multigraph is full if every edge is contained in a cycle.


If G is a directed multigraph and H⊆ G is its largest full subgraph, then the dimension of the polytope P(G) is

    P(G) = |E(H)| - |V(H)| + |{ connected components of  H } |- 1  .



In particular, if G is a strongly connected graph, then P(G) = |E(G)| - |V(G)|.


Additionally,  we are able to describe the equations that define P(G) (for a precise statement see <cit.>).
We highlight that <ref>, together with P_k = P([k]), yields the dimension of the feasible region P_k stated in <ref>.

The proof of <ref> follows from a generalization of some previous results of Gleiss, Leydold and Stadler <cit.>. We refer the reader to <cit.> for further details.






























































We also give an order-preserving bijection between faces of P(G) and full subgraphs of G (ordered by inclusion of edge sets), giving a description of the face poset of P(G).


	
	The face poset of P(G) is isomorphic to the poset of full subgraphs of G according to the following identification:
	
    H ↦ P(G)_H {x⃗∈ P(G) | x_e = 0  for  e∉E(H) }  .

	Further, if we identify P(H) with its image under the canonical injection ^E(H)↪^E(G), we have that P(H) =  P(G)_H.
	
	In particular, P(G)_H =|E(H)| - |V(H)| + |{ connected components of  H } |- 1.


The above result is proved in <cit.> and illustrated in <ref>. 





§ THIRD MAIN RESULT: MIXING CLASSICAL AND CONSECUTIVE PATTERNS


We saw in <ref> that the feasible region clP_k for classical pattern occurrences has been studied in several papers. 
In this extended abstract, the feasible region P_k of limiting points for consecutive pattern occurrences was described. A natural question is the following: what is the feasible region if we mix classical and consecutive patterns?
We reduce this question to the description of the original feasible regions separately in the following result.

 
	For any two points v⃗_1 ∈ P_k, v⃗_2∈ clP_k, consider two sequences
	(σ^m_1)_m∈∈^ and (σ^m_2)_m∈∈^ such that 
	
    |σ^m_1| →∞,  ((π, σ^m_1))_π∈_k→v⃗_1,   and   
    	|σ^m_2| →∞,  ((π, σ^m_2 ))_π∈_k→v⃗_2.

	Then the sequence (σ^m_3)_m∈ defined[An interval in a permutation σ=σ(1)…σ(n) is a factor σ(i)σ(i+1)…σ(j), for j≥ i, such that the set {σ(i),σ(i+1),…,σ(j)} forms an interval of . If σ is a permutation of size n and τ_1,…,τ_n are permutations, then the inflation of σ by τ_1,…,τ_n (denoted by σ[τ_1,…,τ_n]) is the permutation with disjoint intervals τ'_1,…,τ'_n, each respectively isomorphic to τ_1,…,τ_n, from left to right, whose relative order is given by σ.] by σ^m_3σ^m_2[σ^m_1,…,σ^m_1], for all m∈,
	satisfies
	
    |σ^m_3|→∞,   ((π, σ^m_3))_π∈_k→v⃗_1   and  ((π, σ^m_3 ))_π∈_k→v⃗_2.
	


This result shows a sort of independence between classical and consecutive patterns, in the sense that knowing the limiting proportion of classical patterns of a certain sequence of permutations imposes no constraints for the limiting proportion of consecutive patterns and vice versa.


	In <ref> we saw that the proportion of occurrences (resp. consecutive occurrences) in a sequence of permutations (σ^m)_m∈ characterizes the permuton limit (resp. Benjamini–Schramm limit) of the sequence. From <ref>, we can construct a sequence of permutations where the permuton limit is the decreasing diagonal and the Benjamini–Schramm limit is the classical increasing total order on the integer numbers.
	
	We remark that a particular instance of this “independence phenomenon” for local/scaling limits of permutations was recently observed by Bevan, who pointed out in <cit.> that “the knowledge of the local structure of uniformly random permutations with a specific fixed proportion of inversions reveals nothing about their global form”. Here, we prove that this is a universal phenomenon which is not specific to the framework studied by Bevan.




The size of σ^m_3 trivially tends to infinity.
We skip the proof of the limit ((π, σ^m_3))_π∈_k→v⃗_1 since it involves similar techniques as the ones used in the proof of <ref>.
Finally, for the limit ((π, σ^m_3 ))_π∈_k→v⃗_2, note that setting n=|σ^m_3| and k=|π|,

    (π,σ^m_3) = (π,σ^m_3)/nk  
    	=ℙ(_ I(σ^m_3)=π),

where I is a random set, uniformly chosen among the nk subsets of [n] with k elements (we denote random quantities in bold). Let E^m be the event that the random set I contains two indices i, j of [|σ^m_3|] that belong to the same copy of σ^m_1 in σ^m_3. We have that ℙ(_ I(σ^m_3)=π) rewrites as

    ℙ(_ I(σ^m_3)=π |E^m)·ℙ(E^m)+ℙ(_ I(σ^m_3)=π |(E^m)^C)·ℙ((E^m)^C),

where (E^m)^C denotes the complement of the event E^m. We claim that

    ℙ(E^m)≤ k(k-1)/(2·|σ^m_2|)→0.

Indeed, the factor k(k-1)/2 counts the number of pairs i,j in a set of cardinality k and the factor 1/|σ^m_2| is an upper bound for the probability that given a uniform two-element set { i, j} then i,  j belong to the same copy of σ^m_1 in σ^m_3 (recall that there are |σ^m_2| copies of σ^m_1 in σ^m_3). Note also that 

    ℙ(_ I(σ^m_3)=π |(E^m)^C)=(π,σ^m_2)→v⃗_2.

 Using <ref>, we obtain that ((π, σ^m_3 ))_π∈_k→v⃗_2. 

abbrv

