In graph theory, by a diamond one means a finite directed graph without oriented cycles which is a union of two (directed) chains with common minimum and common maximum (some other intermediate points and even edges may be in common as well).
It is often interesting wheather a given span in some partial ordered set can be completed into a diamond. The property of a collection of spans to consist of spans which are expandable into diamonds is very useful in the theory of rewriting systems and producing normal forms in algebra. There are classical results e.g. Newman’s diamond lemma (wikipedia), Širšov-Bergman’s diamond lemma (Širšov is also sometimes spelled as Shirshov), and Church-Rosser theorem (and the corresponding Church-Rosser confluence property).
Alonzo Church, J. Barkley Rosser, Some properties of conversion, Trans. AMS 39, No. 3. (May 1936), pp. 472–482, (jstor)
A. I. Širšov, Some algorithm problems for Lie algebras (Russian)
Sibirsk. Mat. Ž. 3 1962, 292–296, MR0183753
George M. Bergman, Adam O. Hausknecht, The diamond lemma for ring theory, Advances in Mathematics 29 (1978) 178-218, (doi)
L. A. Bokutʹ, I. P. Shestakov, Some results by A. I. Shirshov and his school, Second International Conference on Algebra (Barnaul, 1991), 1–12, Contemp. Math. 184, Amer. Math. Soc. 1995.
L. A. Bokut’, Unsolvability of the word problem and subalgebras of finitely presented Lie algebras, Izv. Akad. Nauk S.S.S.R. Ser. Mat. 36 (1972), 1173-1219 (Russian).
See diamond lemma and the discussion starting here.
L. A. Bokut, Y. Fong, W-F. Ke, Composition-diamond lemma for associative conformal algebras, J. Algebra 272 (2004), no. 2, 739–774.
Vladimir Dotsenko, Pedro Tamaroff, Tangent complexes and the Diamond Lemma, arxiv/2010.14792
The celebrated Diamond Lemma of Bergman gives an effectively verifiable criterion of uniqueness of normal forms for term rewriting in associative algebras. We present a new way to interpret and prove this result from the viewpoint of homotopical algebra. Our main result states that every multiplicative free resolution of an algebra with monomial relations gives rise to its own Diamond Lemma, so that Bergman’s condition of “resolvable ambiguities” becomes the first non-trivial component of the Maurer–Cartan equation in the corresponding tangent complex. The same approach works for many other algebraic structures, emphasizing the relevance of computing multiplicative free resolutions of algebras with monomial relations.
Distinguish from the 5-edge 4-point undirected diamond graph.
Last revised on April 17, 2023 at 14:35:22. See the history of this page for a list of all contributions to it.