Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose four teams, the Aces, the Birds, the Cats, and the Dogs, played each other once. The Aces beat all three opponents except the Birds. The Birds lost to all opponents except the Aces. The Dogs beat the Cats. Represent the results of these games with a directed graph.

A dominance order is a listing of teams such that the ith team in the order beats the (i+1)th team. Find all dominance orders in the graph.

enter image description here

This is the directed graph for the teams, but I don't get the second part. Would a dominance order be ADCB?

share|cite|improve this question

Yes, it would. There is no other dominance order that begins AD: you can have ADB, but B does not beat C, so you can’t complete the order. If you start with AC, the next team clearly must be B, and the order cannot be completed. AB is impossible, so ADCB is the only dominance order beginning with A.

If you begin with B, you must continue with A, and since CD is impossible, the only possible further continuation yields the order BADC.

Similarly, it’s easy to check that CBAD is the only possibility starting with C.

I’ll leave the Dxxx case to you to finish off.

share|cite|improve this answer
if looking at BADC, would ADC be another dominance order or would it be redundant to mention it? – curiousmind1995 Oct 13 '15 at 19:53
@curiousmind1995: It would not be a dominance order on the given set of teams. It would be a dominance order (and in fact the only one) on the subset $\{A,C,D\}$ of teams. – Brian M. Scott Oct 13 '15 at 19:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.