Characterising quotients of projective Fraïssé limits

A characterisation is given of all topological spaces that can be obtained as quotients D/RD, where RD is an equivalence relation and (D,RD) is the projective Fraïssé limit of a projective Fraïssé family of finite topological structures in the language of graph theory.     

On finite groups with the cayley isomorphism property

Let G be a finite group, and let Cay(G, S) be a Cayley digraph of G. If, for all T ⊂ G, Cay(G, S) ≅ Cay(G, T) implies S^α = T for some α ∈ Aut(G), then Cay(G, S) is called a CI-graph of G. For a group G, if all Cayley digraphs of valency m are CI-graphs, then G is said to have the m-DCI property; if all Cayley graphs of valency m are CI-graphs, then G is said to have the m-CI property. It is shown that every finite group of order greater than 2 has a nontrivial CI-graph, and all finite groups with the m-CI property and with the m-DCI property are characterized for small values of m. A general investigation is made of the structure of Sylow subgroups of finite groups with the m-DCI property and with the m-CI property for large values of m. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 21–31, 1998     

ON NON-DETERMINED EHRENFEUCHT-FRAÏSSÉ GAMES AND UNSTABLE THEORIES

In this paper we prove under some set theoretical assumptions that if T is a countable unstable theory then there is a pair of models of T such that Ehrenfeucht-Fraïssé games between these models of large variety of lengths are non-determined.     

A graph isomorphism algorithm using pseudoinverses

For a graph ofm nodes andn edges, an algorithm for testing the isomorphism of graphs is given. The complexity of the algorithm is a maximum ofO(mn ²) in almost all cases, with a considerable reduction if sparsity is exploited. If isomorphism is present, the pseudoinverses of the Laplace matrices of the graphs will be row and column permutations of each other. Advantage can be taken of certain features of the incidence matrices or of properties of the graphs to reduce computation time.     

On the isomorphism classes of Legendre elliptic curves over finite fields

In this paper,the number of isomorphism classes of Legendre elliptic curves over finite field is enumerated.     

On the algorithmic construction of classifying spaces and the isomorphism problem for biautomatic groups

We show that the isomorphism problem is solvable in the class of central extensions of word-hyperbolic groups,and that the isomorphism problem for biautomatic groups reduces to that for biautomatic groups with finite centre.We describe an algorithm that,given an arbitrary finite presentation of an automatic group Γ,will construct explicit finite models for the skeleta of K(Γ,1) and hence compute the integral homology and cohomology of Γ.     

Improved random graph isomorphism

Canonical labeling of a graph consists of assigning a unique label to each vertex such that the labels are invariant under isomorphism. Such a labeling can be used to solve the graph isomorphism problem. We give a simple, linear time, high probability algorithm for the canonical labeling of a G(n,p) random graph for p[ω(ln⁴n/nlnlnn),1−ω(ln⁴n/nlnlnn)]. Our result covers a gap in the range of p in which no algorithm was known to work with high probability. Together with a previous result by Bollobás, the random graph isomorphism problem can be solved efficiently for p[Θ(lnn/n),1−Θ(lnn/n)].     

Stable isomorphism of dual operator spaces

We prove that two dual operator spaces X and Y are stably isomorphic if and only if there exist completely isometric normal representations ? and ψ of X and Y, respectively, and ternary rings of operators M₁, M₂ such that and . We prove that this is equivalent to certain canonical dual operator algebras associated with the operator spaces being stably isomorphic. We apply these operator space results to prove that certain dual operator algebras are stably isomorphic if and only if they are isomorphic. Consequently, we obtain that certain complex domains are biholomorphically equivalent if and only if their algebras of bounded analytic functions are Morita equivalent in our sense. Finally, we provide examples motivated by the theory of CSL algebras.     

拟L商群的同态与同构

HX群是由一个群向其幂集上提升的群结构．文[1]将HX群推广到一类特殊的格-原子格L上,称之为AHX群．本文研究了一类特殊的AHX群-拟L商群的同态与同构,获得与拟商群相类似的结果．     

Two graph isomorphism polytopes

The convex hull ψ_n,n of certain (n!)² tensors was considered recently in connection with graph isomorphism. We consider the convex hull ψ_n of the n! diagonals among these tensors. We show: 1. The polytope ψ_n is a face of ψ_n,n. 2. Deciding if a graph G has a subgraph isomorphic to H reduces to optimization over ψ_n. 3. Optimization over ψ_n reduces to optimization over ψ_n,n. In particular, this implies that the subgraph isomorphism problem reduces to optimization over ψ_n,n.     

Computational complexity of reconstruction and isomorphism testing for designs and line graphs

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of t-(v,k,λ) designs. For this class of highly regular graphs, we obtain a worst-case running time of O(vlogv+O(1)) for bounded parameters t, k, λ.In a first step, our approach makes use of the Babai-Luks algorithm to compute canonical forms of t-designs. In a second step, we show that t-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.     

On graphs whose Laplacian matrix’s multipartite separability is invariant under graph isomorphism

Normalized Laplacian matrices of graphs have recently been studied in the context of quantum mechanics as density matrices of quantum systems. Of particular interest is the relationship between quantum physical properties of the density matrix and the graph theoretical properties of the underlying graph. One important aspect of density matrices is their entanglement properties, which are responsible for many nonintuitive physical phenomena. The entanglement property of normalized Laplacian matrices is in general not invariant under graph isomorphism. In recent papers, graphs were identified whose entanglement and separability properties are invariant under isomorphism. The purpose of this note is to completely characterize the set of graphs whose separability is invariant under graph isomorphism. In particular, we show that this set consists of K_2,2 and its complement, all complete graphs and no other graphs.     

矩阵C*代数上的群作用与*-同构

通过矩阵C^*代数上的不变群作用,给出了决定C^*结构的一个充分条件。     

The complete isomorphism class of an operator space

Suppose is an infinite-dimensional operator space and is a positive integer. We prove that for every there exists an operator space such that the formal identity map is a complete isomorphism, is an isometry, and . This provides a non-commutative counterpart to a recent result of W. Johnson and E. Odell.

     

Decomposition of an order isomorphism between matrix-ordered Hilbert spaces

The purpose of this note is to show that any order isomorphism between noncommutative -spaces associated with von Neumann algebras is decomposed into a sum of a completely positive map and a completely co-positive map. The result is an version of a theorem of Kadison for a Jordan isomorphism on operator algebras.

     

Power and potential maps induced by any semivalue: Some algebraic properties and computation by multilinear extensions

The notions of total power and potential, both defined for any semivalue, give rise to two endomorphisms of the vector space of cooperative games on any given player set where the semivalue is defined. Several properties of these linear mappings are stated and the role of unanimity games as eigenvectors is described. We also relate in both cases the multilinear extension of the image game to the multilinear extension of the original game. As a consequence, we derive a method to compute for any semivalue by means of multilinear extensions, in the original game and also in all its subgames, (a) the total power, (b) the potential, and (c) the allocation to each player given by the semivalue.