Classification problem for graphs and lattices is wild.

DOI10.1007/S10958-013-1363-0MaRDI QIDQ384722zbMATH OpenOpenAlexFDO

Authors Ruvim Lipyanski, Natalia Vanetik

Publication date 28 November 2013

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.4903

zbMATH Keywords

finite latticesalgebraic latticesclassification problem for graphswild classification problems

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Canonical forms, reductions, classification (15A21) Free lattices, projective lattices, word problems (06B25)

Abstract: We prove that the classification problem for graphs and several types of algebraic lattices (distributive, congruence and modular) up to isomorphism contains the classification problem for pairs of matrices up to simultaneous similarity.

Recommendations

• scientific article; zbMATH DE number 1491624
• scientific article; zbMATH DE number 3815
• scientific article; zbMATH DE number 247192
• scientific article; zbMATH DE number 3885922
• Boundary classes of graphs for some recognition problems
• Solving problems on special classes of graphs
• The geodesic classification problem on graphs
• scientific article; zbMATH DE number 2091962
• The Classification of Finitely Spreading Graphs

Cites work

• scientific article; zbMATH DE number 3366941 (Why is no real title available?)
• Complexity of matrix problems
• Congruence lattices of finite p-algebras
• Homology of certain algebras defined by graphs
• Isomorphisms of Graph Groups
• STACS 2005

Cited in

(4)

• Wildness for tensors
• Complexity of matrix problems
• On Borel complexity of the isomorphism problems for graph related classes of Lie algebras and finite \(p\)-groups
• Identical inclusions of semilattices

This page was built for publication: Classification problem for graphs and lattices is wild.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q384722)