Complexity results in graph reconstruction

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:

(1)

, , , and .

(2)

For all k?2, and .

(3)

For all k?2, .

(4)

.

(5)

For all k?2, .

For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn_∃(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern_∃(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn_∀(G) and ern_∀(G), and give an example of a family {G_n}_n?4 of graphs on n vertices for which vrn_∃(G_n)<vrn_∀(G_n). For every k?2 and n?1, we show that there exists a collection of k graphs on (2^k-1+1)n+k vertices with 2ⁿ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.     

Isomorphisms between C-ternary algebras

In this paper, we prove the Hyers-Ulam-Rassias stability of homomorphisms in C^∗-ternary algebras and of derivations on C^∗-ternary algebras for the following Cauchy-Jensen additive mappings:

(0.1)     

ISOMORPHISMS AND DERIVATIONS IN C*-ALGEBRAS

In this article, we prove the Hyers-Ulam-Rassias stability of the following Cauchy-Jensen functional inequality:‖f (x) + f (y) + 2f (z) + 2f (w)‖≤‖ 2f x + y2 + z + w ‖(0.1)This is applied to investigate isomorphisms between C*-algebras, Lie C*-algebras and JC*-algebras, and derivations on C*-algebras, Lie C*-algebras and JC*-algebras, associated with the Cauchy-Jensen functional equation 2f (x + y/2 + z + w) = f(x) + f(y) + 2f(z) + 2f(w).     

Multiplicative Lie Isomorphisms Between Prime Rings

Let ? be a prime ring with 1 containing a nontrivial idempotent E, and let ?′ be another prime ring. If Φ:? → ?′ is a multiplicative Lie isomorphism, then Φ(T + S) = Φ(T) + Φ(S) + Z′ _T,S for all T, S ∈ ?, where Z′ _T,S is an element in the center 𝒵′ of ?′ depending on T and S.     

Algorithmic Information Distortions in Node-Aligned and Node-Unaligned Multidimensional Networks

In this article, we investigate limitations of importing methods based on algorithmic information theory from monoplex networks into multidimensional networks (such as multilayer networks) that have a large number of extra dimensions (i.e., aspects). In the worst-case scenario, it has been previously shown that node-aligned multidimensional networks with non-uniform multidimensional spaces can display exponentially larger algorithmic information (or lossless compressibility) distortions with respect to their isomorphic monoplex networks, so that these distortions grow at least linearly with the number of extra dimensions. In the present article, we demonstrate that node-unaligned multidimensional networks, either with uniform or non-uniform multidimensional spaces, can also display exponentially larger algorithmic information distortions with respect to their isomorphic monoplex networks. However, unlike the node-aligned non-uniform case studied in previous work, these distortions in the node-unaligned case grow at least exponentially with the number of extra dimensions. On the other hand, for node-aligned multidimensional networks with uniform multidimensional spaces, we demonstrate that any distortion can only grow up to a logarithmic order of the number of extra dimensions. Thus, these results establish that isomorphisms between finite multidimensional networks and finite monoplex networks do not preserve algorithmic information in general and highlight that the algorithmic information of the multidimensional space itself needs to be taken into account in multidimensional network complexity analysis.     

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.     

关于GL(3,2)的两个反例

指出GL(3,2)的两个不共轭的{2,3}-Hall子群都和S_4同构.由此,进一步给出两个不同构的S_4-模提供相同2-Brauer特征标的例子.     

Complete fuzzy topological hyperfields and fuzzy multiplication in the fuzzy real lines

Recently E. Sanchez has given a necessary and sufficient condition for the existence of a solution of a fuzzy $\text{A 1 X = C}$, with 1 the extension of a given binary operation in the universe of discourse.Using many valued logic we generalize this result and get a characterization also of the cases if $\text{A 1 X = C}$ has only nearly a solution.Additionally, we consider fuzzy relation equations and get similar results.