Classification problem for graphs and lattices is wild.

DOI10.1007/S10958-013-1363-0zbMATH Open1302.06009arXiv1008.4903OpenAlexW2030124182MaRDI QIDQ384722FDOQ384722

Authors: Ruvim Lipyanski, Natalia Vanetik 

Publication date: 28 November 2013

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Isomorphisms of Graph Groups
• Homology of certain algebras defined by graphs
• Congruence lattices of finite \(p\)-algebras
• Complexity of matrix problems
• 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)