[EM] sprucing up

[Forest Simmons]

> Date: Tue, 28 Dec 2004 13:40:07 -0800
> From: Ted Stern <tedstern at mailinator.com>
> Subject: [EM] Re: Sprucing up MMPO and other methods
>
...

>
> I have a question about the first stage, eliminating covered candidates:
>
> On 21 Dec 2004 at 16:09 PST, Forest Simmons wrote:
>> 1.  Eliminate covered candidates until each remaining candidate has a short
>> (length one or two) beat path to each of the other remaining candidates.
>>
> [...]
>
>>
>> In step one form a matrix M whose (i,j) element is one if candidate i
>> beats candidate j pairwise (as well as in the case if i=j), but is zero
>> otherwise.  Then form the matrix A=M^2.
>>
...

>
> This implies that M  equals
>
>  0  1  1  0
>  0  0  1  0
>  0  0  0  1
>  1  1  0  0

Actually M has 1's down the main diagonal because of the i=j proviso in my 
definition of M.

...

> I think it is possible to show that every 4-candidate cycle can be reduced to
> 3 candidates this way.  Can you verify this?

Yes, as I mentioned before, if you put arrows on the edge of a tetrahedron 
so that no vertex is a source or a sink, then all such arrangements of 
arrows are isomorphic. So once you've shown that one of these reduces to a 
three cycle, then you've shown that all of them do.

Forest