A diamond is 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, Š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.
Distinguish from the 5-edge 4-point undirected diamond graph.
Last revised on December 26, 2018 at 10:31:10. See the history of this page for a list of all contributions to it.