On Tuesday 04 September 2007, "Jason" wrote:

On Tue, 4 Sep 2007, Michael Speciner wrote:

...

My daughter asked me a question based on a homework assignment:

Given n objects, and a choice of a comparison (<, =, >) between each of the nChoose2 pairs of them, what is the maximum number of the nChoose3 triples of the objects that can simultaneously violate transitivity (e.g. A > B >= C >= A)?

You must be using a specialized definition of <,=,> if A>B>=C>=A is true. Can you be more specific?

No, he's using a *generalized* definition (or, rather, no definition at all) of <, =, >. Imagine that you draw up a big table, n by n in size, and in each cell of the table you put one of "first bigger", "second bigger", and "equal". (Without regard for any relationships that may actually hold between the objects, and for whether the relationships represented by your table make any sort of sense.) So there are 3^(n^2) possible tables. Now write a > b if the (a,b) entry in the table says "first bigger", etc. Again, ">" here needn't have anything to do with any other relation called ">" that you might already have between the objects, and it needn't make sense. In particular, it might happen that a > b >= c >= a. (With these new crazy definitions of ">", ">=", etc.) And the question is: among all those 3^(n^2) crazy redefinitions of ">", some will be crazier than others in that they'll make more relations like "a > b > c > a" true; so how crazy can you get? How many {a,b,c} can you arrange to have that violate transitivity in this sort of way? -- g