An exchange matrix @math dominates an exchange matrix @math if the signs of corresponding entries weakly agree, with the entry of @math always having weakly greater absolute value. When @math dominates @math , interesting things happen in many cases (but not always): the identity map between the associated mutation-linear structures is often mutation-linear; the mutation fan for @math often refines the mutation fan for @math ; the scattering (diagram) fan for @math often refines the scattering fan for @math ; and there is often an injective homomorphism from the principal-coefficients cluster algebra for @math to the principal-coefficients cluster algebra for @math , preserving @math -vectors and sending the set of cluster variables for @math (or an analogous larger set) into the set of cluster variables for @math (or an analogous larger set). The scope of the description "often" is not the same in all four contexts and is not settled in any of them. In this paper, we prove theorems that provide examples of these dominance phenomena.
All of the references cited just above are concerned primarily with notions of morphisms of cluster algebras, but, to the author's knowledge, the homomorphisms proposed here do not fit into any category of cluster algebras already proposed. One category, proposed in @cite_19 , features . These require that initial cluster variables (including frozen'' variables) map to cluster variables or to integers. In our examples, the map restricts to a bijection on (non-frozen) initial cluster variables, but the frozen variables (which we call and denote by @math ) may map to other elements of the cluster algebra. In @cite_14 , it is shown that each rooted cluster morphism defines a seed homomorphism, or, loosely speaking, a dominance relationship in the broader sense allowing submatrices and or a sign change as above. Other notions of morphisms between cluster algebras include the of [Section 12] ca4 and [Section 3] universal and the of @cite_7 , both of which fix the exchange matrix @math .
@cite_19 @cite_14 @cite_7
2594579884 2963395513 2531021157 1985875030
We introduce a category of cluster algebras with fixed initial seeds. This category has countable coproducts, which can be constructed combinatorially, but no products. We characterise isomorphisms and monomorphisms in this category and provide combinatorial methods for constructing special classes of monomorphisms and epimorphisms. In the case of cluster algebras from surfaces, we describe interactions between this category and the geometry of the surfaces. We introduce quasi-homomorphisms of cluster algebras, a flexible notion of a map between cluster algebras of the same type (but with different coefficients). The definition is given in terms of seed orbits, the smallest equivalence classes of seeds on which the mutation rules for non-normalized seeds are unambiguous. We present examples of quasi-homomorphisms involving familiar cluster algebras, such as cluster structures on Grassmannians, and those associated with marked surfaces with boundary. We explore the related notion of a quasi-automorphism, and compare the resulting group with other groups of symmetries of cluster structures. For cluster algebras from surfaces, we determine the subgroup of quasi-automorphisms inside the tagged mapping class group of the surface. In our LICS 2004 paper we introduced an approach to the study of the local structure of finite algebras and relational structures that aims at applications in the Constraint Satisfaction Problem (CSP). This approach involves a graph associated with an algebra @math or a relational structure A, whose vertices are the elements of @math (or A), the edges represent subsets of @math such that the restriction of some term operation of @math is ‘good’ on the subset, that is, act as an operation of one of the 3 types: semilattice, majority, or affine. In this paper we significantly refine and advance this approach. In particular, we prove certain connectivity and rectangularity properties of relations over algebras related to components of the graph connected by semilattice and affine edges. We also prove a result similar to 2-decomposition of relations invariant under a majority operation, only here we do not impose any restrictions on the relation. These results allow us to give a new, somewhat more intuitive proof of the bounded width theorem: the CSP over algebra @math has bounded width if and only if @math does not contain affine edges. Actually, this result shows that bounded width implies width (2,3). We also consider algebras with edges from a restricted set of types. In particular, it can be proved that type restrictions are preserved under the standard algebraic constructions. Finally, we prove that algebras without semilattice edges have few subalgebras of powers, that is, the CSP over such algebras is also polynomial time. We consider the following general correlation-clustering problem [N. Bansal, A. Blum, S. Chawla, Correlation clustering, in: Proc. 43rd Annu. IEEE Symp. on Foundations of Computer Science, Vancouver, Canada, November 2002, pp. 238-250]: given a graph with real nonnegative edge weights and a 〈+〉 〈-〉 edge labelling, partition the vertices into clusters to minimize the total weight of cut 〈+〉 edges and uncut 〈-〉 edges. Thus, 〈+〉 edges with large weights (representing strong correlations between endpoints) encourage those endpoints to belong to a common cluster while 〈-〉 edges with large weights encourage the endpoints to belong to different clusters. In contrast to most clustering problems, correlation clustering specifies neither the desired number of clusters nor a distance threshold for clustering; both of these parameters are effectively chosen to be best possible by the problem definition.Correlation clustering was introduced by [Correlation clustering, in: Proc. 43rd Annu. IEEE Syrup. on Foundations of Computer Science, Vancouver, Canada, November 2002, pp. 238-250], motivated by both document clustering and agnostic learning. They proved NP-hardness and gave constant-factor approximation algorithms for the special case in which the graph is complete (full information) and every edge has the same weight. We give an O(log n)-approximation algorithm for the general case based on a linear-programming rounding and the "region-growing" technique. We also prove that this linear program has a gap of Ω(log n), and therefore our approximation is tight under this approach. We also give an O(r3)-approximation algorithm for Kr, r-minor-free graphs. On the other hand, we show that the problem is equivalent to minimum multicut, and therefore APX-hard and difficult to approximate better than Θ(log n).