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.     

效应代数的直觉模糊滤子

引入效应代数的直觉模糊滤子和它的水平滤子的概念,讨论了直觉模糊滤子与水平滤子间的关系,给出了直觉模糊滤子的等价描述,研究了直觉模糊滤子的几个运算性质。在两个经典效应代数的效应态射与效应同构意义下,讨论了这种直觉模糊滤子的像和前像问题。     

Inverse Subsemigroups of the Monogenic Free Inverse Semigroup

It is shown that every finitely generated inverse subsemigroup (submonoid) of the monogenic free inverse semigroup (monoid) is finitely presented. As a consequence, the homomorphism and the isomorphism problems for the monogenic free inverse semigroup (monoid) are proven to be decidable.     

On the Direct Indecomposability of Infinite Irreducible Coxeter Groups and the Isomorphism Problem of Coxeter Groups

In this article, we prove that any irreducible Coxeter group of infinite order, which is possibly of infinite rank, is directly indecomposable as an abstract group. The key ingredient of the proof is that we can determine, for an irreducible Coxeter group W, the centralizers in W of the normal subgroups of W that are generated by involu-tions. As a consequence, the problem of deciding whether two general Coxeter groups are isomorphic is reduced to the case of irreducible ones. We also describe the automorphism group of a general Coxeter group in terms of those of its irreducible components.     

Integral Loop Rings of Loops Whose Derived Subloop Is Central

It is proven that finite loops whose derived subloop is central are determined by Z, the ring of integers, that is, if L and M are two such loops and Z L ? Z M, then L ? M.     

Tracing Robert's use of representations to solve counting problems: A 16-year case study

This study describes how Robert used his external representations (formulae, notations, sketches, models, and figures) to solve progressively more challenging counting tasks over a 16-year period. In his explorations of counting tasks, Robert discovered intricate connections between solutions to problems that looked different on the surface. Using video data from Robert's problem solving, analyses of his solutions are presented that shed light on how he built new ideas from existing ideas and how he modified external representations to make new mathematical discoveries and provide justifications for his solutions.     

NON-ISOMORPHIC GROUPS WITH ISOMORPHICSPECTRAL TABLES AND BURNSIDE MATRICES

ＮＯＮ－ＩＳＯＭＯＲＰＨＩＣＧＲＯＵＰＳＷＩＴＨＩＳＯＭＯＲＰＨＩＣＳＰＥＣＴＲＡＬＴＡＢＬＥＳＡＮＤＢＵＲＮＳＩＤＥＭＡＴＲＩＣＥＳ￥Ｗ．ＫＩＭＭＥＲＬＥ；Ｋ．Ｗ．ＲＯＧＧＥＮＫＡＭＰ（ＭａｔｈｅｍａｔｉｓｃｈｅｓｉｎｓｔｉｔｕｔＢ，Ｕｎｉｖｅｒｓ...     

Gelfand–Mazur Theorems in normed algebras: A survey

The Gelfand–Mazur Theorem, a very basic theorem in the theory of Banach algebras states that: (Real version) Every real normed division algebra is isomorphic to the algebra of all real numbers $\mathbb{R}$, the complex numbers $\mathbb{C}$ or the quaternions $\mathbb{H}$; (Complex version) Every complex normed division algebra is isometrically isomorphic to $\mathbb{C}$. This theorem has undergone a large number of generalizations. We present a survey of these generalizations and also discuss some closely related unsettled issues.     

Statistics of isomorphism types in free products

Let Γ be a free product of finitely many finite- and infinite-cyclic groups. For a subgroup Δ of finite index given by its coset representation we compute its isomorphism type, i.e., its decomposition as a free product of finite- and infinite-cyclic groups. We determine the set of isomorphism types realized by finite-index subgroups, the asymptotics of the subgroup numbers with prescribed isomorphism types, and the distribution of the isomorphism types among subgroups of fixed index. Apart from group-theoretic arguments, the proofs of the present paper make use of asymptotic, combinatorial, and probabilistic ideas and techniques.