Levi lemma

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (September 2007) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In mathematics, in the area of combinatorics, the Levi lemma states that, for all strings u, v,x and y, if uv=xy, then there exists a string w such that either

uw=x and v=wy

or

u=xw and wv=y

That is, there is a string w that is "in the middle", and can be grouped to one side or the other.

The above is known as the Levi lemma for strings; the lemma can occur in a more general form in graph theory and in monoid theory; for example, there is a more general Levi lemma for traces.