|
|
| Line 65: |
Line 65: |
| ====== MV3 implies LQ except in the case "xyzyx" (WIP) ====== | | ====== MV3 implies LQ except in the case "xyzyx" (WIP) ====== |
|
| |
|
| ====== An MV3 is pairwise MOS (PMOS) except in the case "xyzyx" (WIP) ====== | | ====== MV3 + LQ implies PMOS (WIP) ====== |
| TODO: account for case xyzyx.
| |
| | |
| To eliminate xyzyx we manually check all words up to length 5... (todo)
| |
| | |
| Now assume len(S) >= 6.
| |
| | |
| WOLOG consider chunks of x. Use q for any occurrence of either y and z.
| |
| | |
| say you have some intvl class (k steps) with 3 variants in x's and q's:
| |
| * S1 = a1x + b1q, represented by the word s1 in the MV3 scale
| |
| * S2 = a2x + b2q, word s2
| |
| * S3 = a3x + b3q, word s3
| |
| (si to be chosen later)
| |
| Say that the mos formed by the Ys and Zs is rY sZ, wolog r > s.
| |
| The # of chunks in rY sZ is s. The min chunk size is floor(r/s).
| |
| The idea is to keep extending si to the right until the chunk size in the MOS guarantees an extra variety.
| |
| | |
| First we prove that chunk sizes can't differ by 2 or more.
| |
| | |
| have some length (say that of biggest chunk of x's) word with no q's and >=2 q's.
| |
| | |
| now y[biggest]z => contradiction bc two kinds of "one q"
| |
| | |
| so some non biggest chunk has to have y[chunk]z (or z[chunk]y)
| |
| | |
| then by using size of [y[non-biggest chunk]z] you get a contradiction bc you can scoot to get an x (since consecutive q's cant happen if there are consecutive x's)
| |
| | |
| u get [xyxxx...x]z, x[yxxxx...xz]x, y[x...xz], and all x's from the max chunk
| |
| | |
| If we have more q's than x's then we can't have "xx", so we're done.
| |
| | |
| This proves the claim about chunk sizes.
| |
| | |
| ''To be continued...''
| |
|
| |
|
| ====== PMOS implies AG (except in the case xyxzxyx) (WIP) ====== | | ====== PMOS implies AG (except in the case xyxzxyx) (WIP) ====== |