We characterize the rank of edge connection matrices of partition functions of real vertex models, as the dimension of the homogeneous components of the algebra of @math -invariant tensors. Here @math is the sub- group of the real orthogonal group that stabilizes the vertex model. This answers a question of Bal 'azs Szegedy from 2007.
Let @math positive and @math symmetric. Lov 'asz @cite_5 characterized the ranks of the vertex connection matrices of the parameter @math . Let @math . Two distinct vertices @math are called if @math for all @math .
@cite_5
1975568166 2060898859 2141382791 2095567216
Connection matrices were introduced in [M. Freedman, L. Lovasz, A. Schrijver, Reflection positivity, rank connectivity, and homomorphism of graphs (MSR Tech Report # MSR-TR-2004-41) ftp: ftp.research.microsoft.com pub tr TR-2004-41.pdf], where they were used to characterize graph homomorphism functions. The goal of this note is to determine the exact rank of these matrices. The result can be rephrased in terms of the dimension of graph algebras, also introduced in the same paper. Yet another version proves that if two k-tuples of nodes behave in the same way from the point of view of graph homomorphisms, then they are equivalent under the automorphism group. We introduce and study the notions of pair-wise and source-wise preservers.Given an undirected N-vertex graph G = (V, E) and a subset P of pairs of vertices, let G' = (V, H), H ⊆ E, be called a pair-wise preserver of G with respect to P if for every pair u, w ∈ P, dist G' (u, w) = dist G (u, w). For a set S ⊆ V of sources, a pair-wise preserver of G with respect to the set of all pairs P = (S 2) of sources is called a source-wise preserver of G with respect to S.We prove that for every undirected possibly weighted N-vertex graph G and every subset P of P = O(N1 2) pairs of vertices of G, there exists a linear-size pair-wise preserver of G with respect to P. Consequently, for every subset S ⊆ V of S = O(N1 4) sources, there exists a linear-size source-wise preserver of G with respect to S. On the negative side we show that neither of the two exponents (1 2 and 1 4) can be improved even when the attention is restricted to unweighted graphs.Our lower bounds involve constructions of dense convexly independent sets of vectors with small Euclidean norms. We believe that the link between the areas of Discrete Geometry and spanners that we establish is of independent interest, and might be useful in the study of other problems in the area of low-distortion embeddings. It is shown that a graph parameter can be realized as the number of homomorphisms into a fixed (weighted) graph if and only if it satisfies two linear algebraic conditions: reflection positivity and exponential rank-connectivity. In terms of statistical physics, this can be viewed as a characterization of partition functions of vertex models. Abstract Let G be a simple graph with vertices 1, 2, …, n . We consider representations of G by nonzero vectors x 1 ,x 2 ,…,x n ϵ R d such that for i ≠ j the inner product x i · x j is negative or zero according as vertex i is adjacent to or not adjacent to vertex j . The least dimension d necessary for such representations is studied as a function of G and of various restrictions placed upon the coordinates of the vectors and the values of the inner products. In particular, for some d such that d n 2 , there always exists a representation in which all coordinates are from −1,1 and all negative inner products have the same value. Various types of vector representations of graphs are related to Hadamard matrices, families of sets with prescribed intersections, and other combinatorial problems.