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).

Completing spans to diamonds

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.

  • L. A. Bokut, Y. Fong, W-F. Ke, Composition-diamond lemma for associative conformal algebras, J. Algebra 272 (2004), no. 2, 739–774.

Other notion of a diamond

Distinguish from the 5-edge 4-point undirected diamond graph.

Revised on May 11, 2011 00:03:33 by Mike Shulman (