Cluster Monomials in Graph Laurent Phenomenon Algebras
Guilherme Zeus Dantas e Moura Ramanuja Charyulu Telekicherla Kandalam Dora Woodruff


Fast photon-mediated entanglement of continuously-cooled trapped ions 
 for quantum networking
    Christopher Monroe
    April 29, 2024
==============================================================================================




    Laurent Phenomenon algebras,
    first introduced by ,
    are a generalization of cluster algebras that still possess many salient features of cluster algebras.
    Linear Laurent Phenomenon algebras,
    defined by ,
    are a subclass of Laurent Phenomenon algebras
    whose structure is given by the data of a directed graph.
    The main result of this paper is that the cluster monomials of a linear Laurent Phenomenon algebra form a linear basis,
    conjectured by  and analogous to a result for cluster algebras by .






§ INTRODUCTION
 

clusteralgebrasi introduced cluster algebras, which are commutative algebras with generators grouped into sets called clusters, and they have applications in various mathematical contexts such as Lie theory, triangulations of surfaces, and Teichmüller theory.

The core idea of cluster algebras is that the generators, known as cluster variables, are organized into sets called clusters, and these clusters are related by exchange binomials, which allow for the exchange of variables within a cluster according to the rule:

    old variable×new variable = exchange binomial

The Laurent Phenomenon is a remarkable property of cluster algebras, stating that any cluster variable can be expressed as a Laurent polynomial when written as a rational function in terms of any other cluster.
This property, along with other salient features of cluster algebras, holds in more general settings as well.
Laurent Phenomenon algebras, introduced by LP, are a generalization of cluster algebras that retain many of these salient features, including the Laurent Phenomenon.
In Laurent Phenomenon algebras, the exchange polynomials can be irreducible polynomials, rather than just binomials.

linearLP defined a specific class of Laurent Phenomenon algebras called graph Laurent Phenomenon algebras, which are characterized by the structure of a directed graph  and provide an explicit description of the cluster variables and clusters of a graph Laurent Phenomenon algebra 𝒜_.
About this structure, [Conjecture 7.3a]linearLP conjectured Theorem <ref>.


    Let  be a graph, and let 𝒜_ be the associated LP algebra with coefficient ring . Then, the cluster monomials of 𝒜_ form a basis over R.


Theorem <ref> parallels the case for cluster algebras, where basis proved that cluster monomials form a linear basis in finite type cluster algebras.

The main result of this paper is a proof of Theorem <ref>, which is split into two parts.
First, we establish the linear independence of cluster monomials in a graph LP algebra, as stated in Theorem <ref>.
Second, we demonstrate that cluster monomials in a graph LP algebra form an -linear spanning set, as stated in Theorem <ref>.

In Section <ref>, we recall and expand upon definitions and results from <cit.>.
In Section <ref>, we prove that cluster monomials in a graph LP algebra are linearly independent over .
In Section <ref>, we prove that cluster monomials in a graph LP algebra form an -linear spanning set.
In Section <ref>, we present partial results on a positivity conjecture [Conjecture 7.3b]linearLP.



 §.§ Acknowledgments
 

This project was partially supported by RTG grant NSF/DMS-1745638.
It was supervised as part of the University of Minnesota School of Mathematics Summer 2023 REU program.
The first author was supported by Haverford College's KINSC Summer Scholar funding.
We would like to thank our mentor Pasha Pylyavskyy and our teaching assistant Robbie Angarone for their guidance and support.



§ PRELIMINARIES AND NOTATIONAL CONVENTIONS
 



 §.§ Multisets
 

A multiset S is a sequence of sets S1⊃ S2⊃⋯ indexed by the positive integers.
We say that x has multiplicity m in S if m+1 is the smallest positive integer such that x ∉ Sm+1.
In this case, if m > 0, it follows that x ∈ Sm.
Therefore, Si is the set of elements with multiplicity at least i in S.
A set S is naturally identified with the multiset given by the sequence S ⊃∅⊃∅⊃⋯, that is, we interpret a set as a multiset with all multiplicities equal to 1.

Given multisets S and T, we say that S and T are disjoint if S1 and T1 are disjoint.
We say that S is contained in T, denoted by S ⊂ T, if Si⊂ Ti for all i.
The sum of two multisets S and T is the multiset S  T with the multiplicity of each element x being the sum of its multiplicities in S and T.
If S is contained in T, the subtraction of S from T is the multiset T  S with the multiplicity of each element x being the subtraction of its multiplicity in S from its multiplicity in T.

We may define a multiset by simply listing its elements, with the multiplicity of each element being the number of times it appears in the list.
For example, S = {1, 1, 2, 3} is the multiset with elements 1, 2, 3 and multiplicities 2, 1, 1, respectively, in which case we have S1 = {1, 2, 3}, S2 = {1}, and Si = ∅ for all i ≥ 3.

When summations, multiplications, and other operations are applied to multisets, the result is obtained by applying the operation to the results obtained by applying the operation to each set in the sequence.
In other words,

    ∑_x ∈ S f(x) = ∑_m ∈∑_x ∈ Sm f(x),

and similarly for products and other operations.



 §.§ Directed graph
 

Let  be a directed graph with vertex set  and edge set .
We maintain this notation throughout the document.
Examples of directed graphs are given in Figure <ref>.





 §.§ Nested collections
 

A subset I ⊂ is strongly connected if the induced subgraph on I is strongly connected, that is, if for all vertices v, u ∈ I, there is some directed path contained in I from v to u.

For example,
taking  to be the directed graph in Figure <ref>,
the strongly connected sets of vertices are ∅, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, and {1, 2, 3, 4}.
Taking  to be the directed graph in Figure <ref>,
the strongly connected sets of vertices are ∅, {1}, {2}, {3}, {4}, {1, 3}, {1, 2, 3}, {1, 3, 4}, and {1, 2, 3, 4}.

Note that any subset U ⊂ is uniquely partitioned into maximal strongly connected subsets, called strongly connected components of U.

A (multi)set 𝒩 with elements from , where  denotes the powerset of ,
is a nested (multi)collection if

    
  * 
    for every pair I, J ∈𝒩,
    either I ⊂ J, J ⊂ I, or I ∩ J = ∅, and
    
  * 
    for any ℛ⊂𝒩 such that I ∩ J = ∅ for all distinct I, J ∈ℛ,
    each I ∈ℛ is a strongly connected component of the subgraph induced by ⋃_J ∈ℛ J.


Note that <ref>, applied to singletons ℛ, implies that each I ∈𝒩 is strongly connected.
Note that a multiset 𝒩 is a nested multicollection if and only if the set 𝒩1 is a nested collection.
We usually disregard the empty set when considering nested collections.

For example,
consider  to be the directed graph in Figure <ref>.
The set

    {{2},
            {4},
            {2, 3, 4},
            {1, 2, 3, 4}}
 
is a nested collection.
The set

    {{1},
            {1, 3},
            {1, 4},
        }

is not a nested collection because {1, 3} and {1, 4} do not satisfy <ref>.
The set

    {{2, 4},
            {2, 3, 4},
            {1, 2, 3, 4}}

is not a nested collection because ℛ = {{2, 4}} does not satisfy <ref>, since the strongly connected components of {2, 4} are {2} and {4}.
The set

    {{1},
            {3},
            {1, 2, 3},
            {1, 2, 3, 4}}

is not a nested collection because ℛ = {{1}, {3}} does not satisfy <ref>, since the only strongly connected component of {1, 3} is {1, 3}.

 
    The map 𝒩↦_I ∈𝒩 I is a bijection between the set of nested multicollections 𝒩 and the set of multisets T with elements from .


The proof of Lemma <ref> is split into two parts: surjectivity and injectivity.


    Let T be a multiset with elements from .
    We construct a nested multicollection 𝒩 such that T = _I ∈𝒩 I.

    Recall that Ti denotes the set of elements of T with multiplicity at least i.
    Note that T1⊃ T2⊃⋯.
    Let 𝒩_i be the set of strongly connected components of the subgraph induced by Ti.
    Let 𝒩 = _i ∈𝒩_i.
    Then, 
    
    T = _i ∈ Ti = _i ∈_I ∈𝒩_i I = _I ∈𝒩 I.


    First, we show that 𝒩 satisfies <ref>.
    Let I, J ∈𝒩.
    Then, I ∈𝒩_i and J ∈𝒩_j for some i, j ∈.
    Recall that I is a strongly connected component of the subgraph induced by Ti, and J is a strongly connected component of the subgraph induced by Tj.
    Without loss of generality, i ≤ j, therefore, Ti⊃ Tj.
    Therefore, there exists a strongly connected component K of the subgraph induced by Ti such that J ⊂ K.
    Moreover, since I and K are strongly connected components of the subgraph induced by Ti, I = K or I ∩ K = ∅.
    In the first case, I ⊂ J, 
    while in the second case, I ∩ J = ∅,
    as desired.

    Now we show that 𝒩 satisfies <ref>,
    that is, for any ℛ⊂𝒩 such that I ∪ J = ∅ for all distinct I, J ∈ℛ,
    each I ∈ℛ is a strongly connected component of the subgraph induced by R = ⋃_J ∈ℛ J.
    We prove by induction on the number of elements of ℛ.
    If ℛ = ∅, then the statement is vacuously true.
    Suppose that ℛ has at least one element.
    Let i ∈ be the minimum index such that ℛ∩𝒩_i ≠∅, and let I ∈ℛ∩𝒩_i.
    Then, all J ∈ℛ are subsets of Ti, and consequently, R = ⋃_J ∈ℛ J is a subset of Ti.
    Therefore, I ⊂ R ⊂ Ti.
    Since I is a strongly connected component of the subgraph induced by Ti, it follows that I is a strongly connected component of the subgraph induced by R.
    The connected components of the subgraph induced by R different from I are the connected components of R ∖ I.
    Applying the induction hypothesis to ℛ∖{I}, we obtain that each J ∈ℛ∖{I} is a strongly connected component of the subgraph induced by R ∖ I, and therefore, each J ∈ℛ is a strongly connected component of the subgraph induced by R, as desired.

    Therefore, 𝒩 is a nested multicollection and T = _I ∈𝒩 I, as desired.



    Let T be a multiset with elements from . We prove that there is a unique nested multicollection 𝒩 such that T = _I ∈𝒩 I.
    The proof is by induction on the number of elements of T.
    If T = ∅, then 𝒩 = ∅ is the unique nested multicollection such that T = _I ∈𝒩 I.

    Suppose that T has at least one element.
    Let 𝒩 be a nested multicollection such that T = _I ∈𝒩 I.
    Let T^(1) be the set of elements of T with multiplicity at least 1.
    Let ℛ be the set of maximal elements of 𝒩.
    Note that, for all v ∈ T^(1), there exists a unique I ∈ℛ such that v ∈ I.
    Therefore, T^(1) = _I ∈ℛ I.
    Since 𝒩 is nested and I ∪ J = ∅ for all distinct I, J ∈ℛ, it follows that each I ∈ℛ is a strongly connected component of the subgraph induced by T^(1).
    Hence, ℛ is the set of strongly connected components of the subgraph induced by T^(1).

    Let T' = T  T^(1), and let 𝒩' = 𝒩ℛ.
    Since T = _I ∈𝒩 I and T^(1) = _I ∈ℛ I,
    it follows that T' = _I ∈𝒩' I.
    Since 𝒩 is nested, 𝒩' is nested.
    By the induction hypothesis, 𝒩' is the unique, and consequently, 𝒩 is the unique.




 §.§ Laurent polynomial ring
 

Let the coefficient ring  be a ring over 
containing elements A_v for each v ∈ which are algebraically independent.
For example,  could be
[A_v : v ∈].
Let ambient ring  be the rational function field over 
in the independent variables X_v for v ∈.
Let ⊂ denote the Laurent polynomial ring over 
in the independent variables X_v for v ∈, that is,
= [X_v^± 1 : v ∈].

The monomials in  in the variables X_v and X_v^-1 for v ∈ are called Laurent monomials.
Any Laurent monomial can be written as

    UT = ∏_v ∈ U X_v / ∏_v ∈ T X_v,

where U and T are disjoint multisets with elements in .
As a module over , the Laurent polynomial ring  has a basis consisting of all Laurent monomials.



 §.§ Multifunctions
 

Let I be a multiset with elements from .
A multifunction f (of ) on I is a directed multigraph with vertex set  and edge multiset _f such that

    
  * for each vertex v ∈, the outdegree of v in f is its multiplicity in I, and
    
  * each edge in _f is either a loop or an edge in .


If I is a set, then a multifunction on I is naturally identified with a function from I to , explaining the chosen nomenclature.

A multifunction f is acyclic if the only cycles in f are loops.
Given two multifunctions f and g on multisets I and J, respectively, we define their sum f  g as the multifunction on I  J obtained by taking the sum of the edge multisets of f and g.

For example, take  to be the directed graph in Figure <ref>.
Examples of multifunctions of  are given in Figure <ref>.
The multifunctions in Figure <ref> and Figure <ref> are acyclic, and the multifunction in Figure <ref> is not acyclic.





 §.§ Weight of a multifunction
 

The weight of a multifunction f on I, denoted by f, is the non-Laurent polynomial in  given by

    f
        = ∏_(v, w) ∈_fX_(v, w),

where

    X_(v, w) = 
        
        X_w   if  w ≠ v, 
    
        A_v   if  w = v.

For example,
the weights of the multifunctions in Figures <ref>, <ref>, and <ref> are, respectively,

    A_1 X_2^2 X_3,
            
        X_1 X_4,
          and    
        A_1 X_1 X_2^2 X_3 X_4.


The normalized weight of a multifunction f on I, denoted by f, is the Laurent polynomial in  given by

    f
        = f/∏_v ∈ I X_v
        = ∏_(v, w) ∈_fX_(v, w)/X_v.

For example,
the normalized weights of the multifunctions in Figures <ref>, <ref>, and <ref> are, respectively,

    A_1 X_2^2 X_3/X_1^3 X_2 = 
        A_1 X_2 X_3/X_1^3,
            X_1 X_4/X_3 X_4=
        X_1/X_3,
          and    A_1 X_1 X_2^2 X_3 X_4/X_1^3 X_2 X_3 X_4 =
        A_1 X_2/X_1^2.


We remark that the nomenclature of “weights” and “normalized weights” is not used by linearLP, although the concept is present in their work.

Note that both weights and normalized weights are products over edges of the multifunction, and therefore, if f and g are multifunctions, then 

    f  g = fg    and    f  g = fg.

Note that the normalized weight of a cycle is 1.
This observation will be used in the proof of Lemma <ref> in Section <ref>.



 §.§ The Y Laurent polynomials
 

Let I be a subset of .
We define the Laurent polynomial Y_I ∈ by

    Y_I = f : If/∏_i ∈ I X_i,

where the sum is over all acyclic multifunctions f on I.
Recall that, since I is a set, a multifunction on I is naturally identified with a function from I to .
We may rewrite Y_I in terms of normalized weights as Y_I = f:If.

For example,
taking  to be the directed graph in Figure <ref>,
the Laurent polynomial Y_{1, 2} is

    A_1X_1 + X_3X_1 + X_4X_1 +
            A_1A_2 + X_2A_2 + X_3A_2 + X_4A_2 +
            A_1X_3 + X_2X_3 + X_3^2  + X_4X_3
        /X_1X_2.

Note that the eleven terms in the numerator correspond to the eleven acyclic multifunctions on {1, 2},
which are all twelve multifunctions on {1, 2} by assigning one of the possible four edges to 1,
and one of the possible three edges to 2,
except for the assignment of the edge (1, 2) to 1 and the edge (2, 1) to 2 which is not acyclic.



 §.§ Graph LP algebra and clusters
 

The central algebraic structure of our research is the graph Laurent phenomenon algebra  over  associated to , defined by linearLP.
linearLP proved that  is the algebra over  generated by 
X_v for v ∈ and Y_I for strongly connected I ⊂.
The reader who is new to graph LP algebras can simply take this as the definition of .

Although only the Laurent polynomials Y_I for strongly connected I ⊂ are generators of ,
the Laurent polynomials Y_I for I ⊂ are in  as well, as guaranteed by Lemma <ref>.

 
    Let I be a subset of .
    Then, Y_I = ∏_J Y_J, where the product is over the strongly connected components J of the subgraph of  induced by I.


The monomials in  in the elements X_v for v ∈ v and Y_I for I ⊂ are simply called monomials.
Any monomial in  can be written as

    U𝒮 =
        ∏_v ∈ U X_v ∏_I ∈𝒮 Y_I,

where U is a multiset with elements in  and 𝒮 is a multiset with elements in .
The set of monomials in  is a spanning set of  as a module over .
The monomials in  in the elements Y_I for I ⊂ are called Y-monomials, which can be written as
∅𝒮 =
    ∏_I ∈𝒮 Y_I
where 𝒮 is a multiset with elements in .

The elements X_v for v ∈ and Y_I for strongly connected I ⊂ are grouped into sets called clusters.
We refer to <cit.> for the definition of clusters.
linearLP proved that the clusters of  are the sets of the form

    { X_v : v ∈ U}∪{Y_I : I ∈𝒩}

where U ⊂ and 𝒩 is a maximal nested collection on ∖ U.
The reader who is new to graph LP algebras can simply take this as the definition of the clusters of .

The monomials in  in the elements of a given cluster are called cluster monomials.
Any cluster monomial can be written as

    U𝒩 =
        ∏_v ∈ U X_v ∏_I ∈𝒩 Y_I,

where U is a multiset with elements in  and 𝒩 is a nested collection on ∖ U1.
The monomials in  in the elements Y_I for I ⊂ of a given cluster are called cluster Y-monomials, which can be written as ∅𝒩 = ∏_I ∈𝒩 Y_I where 𝒩 is a nested collection on .



§ LINEAR INDEPENDENCE
 

In this section, we show that the cluster monomials in a graph LP algebra are linearly independent.

By Lemma <ref>, we can reindex the cluster monomials by a pair (U, T) where U and T are disjoint multisets with vertices from , and the cluster monomial indexed by (U, T) is
UT = U𝒩,
where 𝒩 is the unique nested multicollection such that T = _I ∈𝒩 I.

 
    Let U_1, U_2, T_1, T_2 be multisets with vertices from 
    such that U_1 ∩ T_1 = U_2 ∩ T_2 = ∅.
    If U_1 ⊄U_2, then, when expanding U_1T_1 as a linear combination of Laurent monomials over , the coefficient of U_2T_2 is 0.
    If T_1 ⊅T_2, then, when expanding U_1T_1 as a linear combination of Laurent monomials over , the coefficient of U_2T_2 is 0.



    Let 𝒩_1 be the unique nested multicollection such that T_1 = _I ∈𝒩_1 I.
    Recall that
    
    U_1T_1
            = ∏_v ∈ U_1 X_v ∏_I ∈𝒩_1 Y_I
            = ∏_v ∈ U_1 X_v/∏_v ∈ T_1 X_v(
                ∏_I ∈𝒩_1f  I wt(f)
            ).
 

    Since ∏_I ∈𝒩_1f  I wt(f) is a polynomial, the numerator of any term of U_1T_1 is a multiple of ∏_v ∈ U_1 X_v.
    Hence, if U_1 ⊄U_2,
    then the coefficient of
    
    U_2T_2 = ∏_v ∈ U_2 X_v/∏_v ∈ T_2 X_v

    in U_1T_1 must be 0.

    Since ∏_I ∈𝒩_1f  I wt(f) is a polynomial,
    the denominator of any term of U_1T_1 is a divisor of ∏_v ∈ T_1 X_v.
    Hence, if T_1 ⊅T_2,
    then the coefficient of
    
    U_2T_2 = ∏_v ∈ U_2 X_v/∏_v ∈ T_2 X_v

    in U_1T_1 must be 0.


 
    Let U, T be multisets with vertices from .
    When expanding UT as a linear combination of Laurent monomials over , the coefficient of UT is ∏_v ∈ T A_v.



    Let 𝒩 be the unique nested multicollection such that T = _I ∈𝒩 I.
    Recall that
    
    UT
            = ∏_v ∈ U X_v ∏_I ∈𝒩 Y_I 
            = ∏_v ∈ U X_v/∏_v ∈ T X_v(
                ∏_I ∈𝒩f  I wt(f)
            ).


    Note that ∏_I ∈𝒩f  I wt(f) is a polynomial with constant term ∏_v ∈ T A_v, obtained from the constant acyclic function on each I ∈𝒩.
    Therefore, the coefficient of UT in UT is ∏_v ∈ T A_v.


 
    The set of cluster monomials of a graph LP algebra is linearly independent over .



    Suppose that there exists a nontrivial linear combination of cluster monomials that equals 0.
    Explicitly, suppose that there exists coefficients UT, not all zero, such that
    
    ∑_U, TUTUT = 0.


    Pick (U_0, T_0) with U_0T_0≠ 0 such that |U_0| - |T_0| is minimized.
    This implies that, for all (U, T) ≠ (U_0, T_0) such that UT≠ 0,
    it holds that |U| - |T| ≥ |U_0| - |T_0|, and consequently, U ⊄U_0 or T ⊅T_0.

    Hence, by Lemma <ref>, the coefficient of U_0T_0 in 
    UTUT
    is 0
    for all (U, T) ≠ (U_0, T_0) such that UT≠ 0;
    and, by Lemma <ref>, the coefficient of U_0T_0 in the expression
    U_0T_0U_0T_0
    is 
    U_0T_0∏_v ∈ T_0 A_v.
    Therefore, the coefficient of U_0T_0 in
    ∑_U, TUTUT
    is
    U_0T_0∏_v ∈ T_0 A_v ≠ 0,
    a contradiction.




§ SPANNING SET
 

In this section, we show that the cluster monomials in a graph LP algebra form a spanning set.



 §.§ Previous results
 

Let p vIw denote the statement that p is a vertex non-repeating directed path from v to w with intermediary vertices in I.
Let I ∖ p denote the set of vertices in I that are not in p.
Lemma <ref> allows us to rewrite the product of X_v and Y_I whenever v ∈ I.

 
Let I ∈ and v ∈ I.
Then,

    X_v Y_I =
        ∑_w ∈ I∑_p^vIw
        Y_I ∖ p  X_w
        +
        ∑_w ∉I∑_p^vIw
        Y_I ∖ p  A_w.


 


 §.§ Cluster Y-monomials span Y-monomials
 

Given a tuple of multifunctions, we define its weight as the product of the weights of its elements.

 
    Let ℱ, 𝒢 be sets of tuples of multifunctions.
    If ϕℱ→𝒢 preserves weights, that is, f = ϕ(f) for all  f ∈ℱ, then
    
    ∑_f ∈ℱf = ∑_g ∈𝒢| ϕ^-1(g) | g.
 



    Apply the weight-preserving property and double-count pairs (f, g) ∈ℱ×𝒢 such that ϕ(f) = g to obtain
    
    ∑_f ∈ℱf =
            ∑_f ∈ℱϕ(f) =
            ∑_g ∈𝒢| ϕ^-1(g) | g.
 


 
    Let ℱ_1, ℱ_2, 𝒢 be sets of tuples of multifunctions.
    If ϕ_1 ℱ_1 →𝒢 and
    ϕ_2 ℱ_2 →𝒢 preserve weights, and
    |ϕ_1^-1(g)| = |ϕ_2^-1(g)| for all g ∈𝒢, then
    
    ∑_f ∈ℱ_1f = ∑_f ∈ℱ_2f.
 



    Apply Lemma <ref> on ϕ_1 and on ϕ_2 to obtain
    
    ∑_f ∈ℱ_1f =
            ∑_g ∈𝒢| ϕ_1^-1(g) | g = 
            ∑_g ∈𝒢| ϕ_2^-1(g) | g = 
            ∑_f ∈ℱ_2f.
 


 
    Let 𝒮 be a multiset with elements in .
    Let T = _I ∈𝒮 I be the multiset containing the vertices that appear in the sets of 𝒮, counting multiplicities.
    Let 𝒯 be the multiset whose elements are T1, T2, …∈.
    Then,
    
    ∏_S ∈𝒮∑_f : Sf =
            ∏_T' ∈𝒯∑_f : T'f,

    and
    
    ∏_S ∈𝒮∑_f : Sf = ∏_T' ∈𝒯∑_f : T'f.




    Let S_1, S_2, … be the elements of 𝒮.
    Let T_1, T_2, … be the elements of 𝒯.
    Note that T = _i S_i = _j T_j.
    Let
    
    ℱ_1 = { (f_1, f_2, …) : f_i  is a multifunction on  S_i  for each  i ∈}, 
    ℱ_2 = { (f_1, f_2, …) : f_i  is a multifunction on  T_i  for each  i ∈}, 
    𝒢 = { g : g  is a multifunction on  T },

    and consider the functions
    ϕ_1 ℱ_1 →𝒢 and
    ϕ_2 ℱ_2 →𝒢
    where both functions send a tuple of multifunctions to the multifunction obtained by taking the sum of the edges of each multifunction in the tuple.

    Let g ∈𝒢.
    Let's count the number of (f_1, f_2, …) in ℱ_1 such that ϕ_1(f_1, f_2, …) = g.
    Fix v ∈.
    Let g_v denote the multiset of edges in g from v.
    Note that |g_v| is the multiplicity of v in T, which is the number of sets T_i in 𝒯 that contain v.
    Therefore, the number of ways to assign the edges of g_v to the appropriate functions f_i is
    
    |g_v|!/1^| g_v1|· 2^| g_v2|· 3^| g_v3|⋯.

    Therefore, the number of (f_1, f_2, …) in ℱ_1 such that ϕ_1(f_1, f_2, …) = g is
    
    | ϕ_1^-1(g) | =
            ∏_v ∈| g_v |!/1^| g_v1|· 2^| g_v2|· 3^| g_v3|⋯.


    The same argument applies to ϕ_2, and we obtain, for all g ∈𝒢,
    
    | ϕ_1^-1(g) | = | ϕ_2^-1(g) |.

    Hence, by Lemma <ref>, we obtain 
    
    ∑_f ∈ℱ_1f = ∑_f ∈ℱ_2f,

    which implies Equation (<ref>).
    The result in Equation (<ref>) follows by dividing both sides of Equation (<ref>) by ∏_v ∈ T X_v.


 
    Let S ∈.
    Then,
    
    ∑_f : Sf
            = ∑_C ∈𝒞_S Y_S ∖ C,

    where C ranges over the set 𝒞_S of all families of vertex-disjoint cycles in the restriction of  to S.



    Given a function f  S, a vertex can be in at most one cycle, since the only possible cycle containing v must be the periodic part of v, f(v), f^2(v), ….
    Therefore, each function f  S can be uniquely decomposed into a family of vertex-disjoint cycles C and an acyclic function g  S ∖ C such that f is the sum of g and the cycles in C.
    Similarly, given a family of vertex-disjoint cycles C and an acyclic function g  S ∖ C, a function f  S can be obtained by taking the sum of g and the cycles in C.
    Thus, there is a bijection between the set of functions f  S and the set of pairs (C, g) where C is a family of vertex-disjoint cycles and g  S ∖ C.

    Moreover,
    if this bijection associates f to (C, g),
    then the normalized weight of f is the product of the normalized weight of g and the normalized weight of the cycles in C.
    Since the normalized weigh of a cycle is 1, it follows that f = g.

    Finally,
    
    ∑_f : Sf
            = ∑_C ∈𝒞_Sg : S ∖ Cg
            = ∑_C ∈𝒞_S Y_S ∖ C.



 
    Let T be a multiset of vertices.
    Let 𝒯 be the multiset whose elements are T1, T2, …∈.
    Then, the Y-monomial ∅𝒯 is a cluster Y-monomial.



    Let 𝒩_i be the set of strongly connected components of the subgraph of  induced by Ti for each i ∈,
    and let 𝒩 = _i 𝒩_i.
    Lemma <ref> implies that 𝒩 is a nested multicollection.
    Finally, Lemma <ref> implies that Y_Ti = ∏_J ∈𝒩_i Y_J,
    and consequently
    
    ∅𝒯
            = ∏_i Y_Ti
            = ∏_i∏_J ∈𝒩_i Y_J
            = ∏_J ∈𝒩 Y_J
            = ∅𝒩.



 
    Any Y-monomial is an integer linear combination of cluster Y-monomials.
    More precisely, for any multiset 𝒮 with elements in , the cluster Y-monomial ∅𝒮 is an integer linear combination of cluster Y-monomials.
    Moreover, the cluster Y-monomials ∅ℛ in such a linear combination have that all vertices in ℛ are vertices in 𝒮.



    We use induction on the number of vertices in 𝒮.
    Assume, by induction hypothesis, that the result holds for any multiset ℛ with elements in  with a smaller number of vertices than 𝒮.

    Let T = _I ∈𝒮 I, that is, the multiset containing the vertices that appear in the sets of 𝒮, counting multiplicities.
    Let 𝒯 be the multiset whose elements are T1, T2, …∈.
    By Lemma <ref>, the Y-monomial ∅𝒯 is a cluster Y-monomial.

    If 𝒯 = 𝒮, then we are done because ∅𝒮 = ∅𝒯 is a cluster Y-monomial.
    Otherwise, 𝒯≠𝒮.
    From Lemma <ref>, we know that
    
    ∏_S ∈𝒮∑_f : Sf = ∏_T ∈𝒯∑_f : Tf.

    Applying Lemma <ref> to each term of both products, we obtain
    
    ∏_S ∈𝒮∑_C_S ∈𝒞_S Y_S ∖ C_S
            =
            ∏_T ∈𝒯∑_C_T∈𝒞_T Y_T ∖ C_T.

    Rewriting the equation above in terms of cluster Y-monomials, we obtain
    
    ∑_
                    (C_S1, 
                    C_S2, …) 
    90∈
    𝒞_S1×𝒞_S2×⋯∅{ 
                            S1∖ C_S1, …}
            =
            ∑_
                    (C_T1, 
                    C_T2, …) 
    90∈
    𝒞_T1×𝒞_T2×⋯∅{ 
                            T1∖ C_T1, …}.

    Note that when ∅ = C_S1 = C_S2 = ⋯, the term in the sum in the left-hand side is the cluster Y-monomial ∅𝒮.
    Therefore, the cluster Y-monomial ∅𝒮 evaluates to
    
    ∑_
                (C_T1, 
                C_T2, …) 
    90∈
    𝒞_T1×𝒞_T2×⋯∅{ 
                        T1∖ C_T1, …}
            -
            ∑_
                (C_S1, 
                C_S2, …) 
    90∈
    𝒞_S1×𝒞_S2×⋯
    except all ∅∅{ 
                        S1∖ C_S1, …}.


    Note that each monomial in the expression above of the form ±∅ℛ
    satisfies either ℛ = 𝒯 or ℛ has a fewer number of vertices than 𝒮.
    Hence, by Lemma <ref> and by the induction hypothesis, each monomial ∅ℛ in the expression above is an integer linear combination of cluster Y-monomials, and therefore, the Y-monomial ∅𝒮 is an integer combination of cluster Y-monomials.

    Moreover, note that each monomial in the expression above of the form ±∅ℛ have the property that all vertices in ℛ are vertices in 𝒮.
    Consequently, by the induction hypothesis, the cluster Y-monomials ∅ℛ in the expansion of ∅𝒮 are such that all vertices in ℛ are vertices in 𝒮.

    Therefore, by induction, the result holds.




 §.§ Cluster monomials span monomials
 

 
    Any monomial is a linear combination of cluster monomials over .
    More precisely, for any multiset U with elements in  and any multiset 𝒮 with elements in , the cluster monomial U𝒮 is a linear combination of cluster monomials over .



    We apply induction on the number of vertices in 𝒮, counting multiplicities.
    Assume, by induction hypothesis, that the cluster monomial Tℛ is a linear combination over  of cluster monomials whenever ℛ has a smaller number of vertices than 𝒮.

    Assume there exists v ∈ U such that v ∈ S for some S ∈𝒮.
    We can write
    
    U𝒮 = U {v}𝒮{S}· X_v · Y_S.

    Apply Lemma <ref> to X_v and Y_S to obtain
    
    X_v Y_S =
            ∑_w ∈ S∑_p^vSw
            Y_S ∖ p  X_w
            +
            ∑_w ∉S∑_p^vSw
            Y_S ∖ p  A_w.

    Therefore,
    
    U𝒮
            =    ∑_w ∈ S∑_p^vSwU {v}{w}𝒮{S}{S ∖ p}
        + 
            ∑_w ∉S∑_p^vSw
            A_w U {v}𝒮{S ∖ p}{S}.


    This implies that we can write U𝒮 as a linear combination over  of cluster monomials of the form Tℛ, where ℛ has a smaller number of vertices than 𝒮.
    Therefore, by the induction hypothesis, U𝒮 is a linear combination over  of cluster monomials.

    Otherwise, assume all v ∈ U satisfy v ∉S for all S ∈𝒮.
    We can write
    U𝒮 = U∅∅𝒮.
    Apply Theorem <ref> to obtain that ∅𝒮 is a linear combination over  of cluster Y-monomials of the form ∅ℛ, where the vertices in sets of ℛ are a subset of the vertices in sets of 𝒮.
    Explicitly,
    
    ∅𝒮 = ∑_ℛ c(ℛ) ∅ℛ,

    where the vertices in sets of ℛ are a subset of the vertices in sets of 𝒮.
    Therefore,
    
    U𝒮 = ∑_ℛ c(ℛ) Uℛ,

    and hence, U𝒮 is a linear combination over  of cluster monomials.




§ FURTHER DIRECTIONS AND CONCLUDING REMARKS
 

linearLP also propose Conjecture <ref>,
a stronger version of Theorem <ref> that states not only that any monomial of 𝒜_ is a linear combination of cluster monomials over , but also that the coefficients are nonnegative.
Conjecture <ref> is related to a positivity result for cluster algebras.

 
    Each monomial of 𝒜_ is a linear combination of cluster monomials over  with nonnegative coefficients.


We propose a slightly different conjecture, that is about Y-monomials instead of monomials, a stronger version of Theorem <ref> that states not only that any Y-monomial of 𝒜_ is a linear combination of cluster Y-monomials over , but also that the coefficients are nonnegative integers.

 
    Each Y-monomial of 𝒜_ is a linear combination of cluster Y-monomials with nonnegative integer coefficients.


Conjecture <ref> implies Conjecture <ref>, and the proof of this implication is analogous to the proof of Theorem <ref>.

The ideas from this paper might be useful to prove Conjecture <ref> (and hence Conjecture <ref>).
For example, we can solve the special case when  is a tree, as shown in Proposition <ref>.

 
    If  is a tree, then each Y-monomial of 𝒜_ is a linear combination of cluster Y-monomials over  with nonnegative integer coefficients.
    Moreover, each monomial of 𝒜_ is a linear combination of cluster monomials over  with nonnegative coefficients.


[Theorem 6.1]linearLP give a Ptolemy-like formula for expanding Y_IY_J into a positive integer linear combination of cluster monomials in the case where  is a path.
It is possible to extend this formula to the case where  is a tree, as shown in Proposition <ref>.
Proposition <ref> is the key lemma used in the proof of Proposition <ref>.

 
    Let  be a tree.
    Let I, J ⊂.
    A path from I to J is a list of vertices v_1, v_2, …, v_k such that v_1 ∈ I ∖ J, v_k ∈ J ∖ I, and all other vertices are in I ∩ J.
    Then, the expansion of Y_IY_J into cluster monomials is given by
    
    Y_IY_J = ∑_P Y_I ∪ J ∖ PY_I ∩ J ∖ P,
 
    where the sum is taken over all families P of disjoint paths from I to J.


Proposition <ref> can be used to recover the Ptolemy-like formula for paths given in [Theorem 6.1]linearLP.

A proof of Proposition <ref> can be derived using Lemma <ref>;
the reader can consult the authors' report <cit.> for a full proof of Proposition <ref>, as well as a proof of Proposition <ref>.
It would be interesting to further generalize this formula to all graphs, or to a larger class of graphs.

We illustrate Proposition <ref> by considering two examples of choices of a tree , illustrated in Figure <ref>, and choices of subsets I, J ⊂.




    Let = P_n, the path graph with vertices {1, 2, …, n}.
    Figure <ref> shows the path graph P_6.
    Let I = {1, 2, …, k} and J = {l, l+1, …, n}.
    If k < l - 1, then there is no path from I to J and Proposition <ref> implies that Y_I Y_J = Y_I ∪ J, which is a cluster monomial.
    If k ≥ l - 1, then the only path from I to J is {l-1, l, …, k, k+1}.
    Therefore, Y_I Y_J is expanded into two cluster monomials:
    one corresponding to the empty family of paths,
    and the other corresponding to the family containing the only path from I to J.
    Explicitly, we have
    
    Y_{1, …, k} Y_{l, …, n}
            = Y_{1, …, m} Y_{k+1, …, l-1}
              + Y_{1, …, l-1, k+1, …, n}.




    Let  be the tree with vertex set = {1, 2, 3, 4, 5, 6} and edge set = {23, 12, 45, 56, 52}, as shown in Figure <ref>.
    Let I = {1, 2, 4, 5} and let J = {2, 3, 5, 6}.
    There are six families of disjoint paths from I to J, 
    
    ∅,   { (1, 2, 3) },   { (4, 5, 6) },   { (1, 2, 5, 6) },   { (4, 5, 2, 3) },   { (1, 2, 3), (4, 5, 6) }.

    Therefore, Proposition <ref> implies that Y_IY_J is expanded into six cluster monomials, one for each family of disjoint paths. Explicitly,
    
    Y_{1, 2, 4, 5} Y_{2, 3, 5, 6}
            = Y_{1, 2, 3, 4, 5, 6} Y_{2, 5}
            + Y_{4, 5, 6} Y_{5}
            + Y_{1, 2, 3} Y_{2}
            + Y_{4, 3}
            + Y_{1, 6}
            + 1.





