Interleaving: Difference between revisions
| Line 43: | Line 43: | ||
Say |''A''| = 2. (If |''A''| ≥ 3 then the proof is easy.) Say ''B'' is the set of all subwords of ''w'' (not intervals) subtending '''w'''<sub>1</sub>, and ''C'' is the set of all subwords ending in '''Z''' subtending '''w'''<sub>2</sub>. | Say |''A''| = 2. (If |''A''| ≥ 3 then the proof is easy.) Say ''B'' is the set of all subwords of ''w'' (not intervals) subtending '''w'''<sub>1</sub>, and ''C'' is the set of all subwords ending in '''Z''' subtending '''w'''<sub>2</sub>. | ||
Choose ''b'' in ''B'' and ''c'' in ''C'' and consider ''b''('''XZ''', '''YZ''') ''c''('''XZ''', '''YZ'''). | Choose ''b'' in ''B'' and ''c'' in ''C'' and consider the subwords ''b''('''XZ''', '''YZ''') and ''c''('''XZ''', '''YZ''') of ''S''. | ||
If ''k'' = 3, then we can just say ''b'' = ''x'' and ''c'' = ''y''. Suppose '''YZX''' does not occur in ''S''; then ''yx'' does not occur in ''w'' which is a contradiction, so ''YZX'' must occur. | If ''k'' = 3, then we can just say ''b'' = ''x'' and ''c'' = ''y''. Suppose '''YZX''' does not occur in ''S''; then ''yx'' does not occur in ''w'' which is a contradiction, so ''YZX'' must occur. | ||