Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] It's Not a Tree After All

Expand Messages
  • Lance Fortnow
    On Sunday, I posted a link to the 2003 NCAA Division 1 Men s Basketball Championship Brackets which I called America s Favorite Binary Tree . But in a strange
    Message 1 of 1 , Mar 18 6:57 AM
    • 0 Attachment
      On Sunday, I posted a link to the 2003 NCAA Division 1 Men's Basketball Championship Brackets which I called "America's Favorite Binary Tree". But in a strange twist the championship is not quite a tree this year.

      In a usual year the rules are simple. Each team plays its sibling. The winner advances to the parent node and the process repeats. The team that reaches the root is the champion.

      The tree structure gives a nice uniqueness factor. If Notre Dame plays Duke this year, they would have to meet in the fourth round. There is no scenario of plays in the other games that would cause Notre Dame to play Duke in any other round.

      So why isn't it a tree this year? The problem is Brigham Young University. If BYU wins their first three games, they would have played their fourth game on Sunday, March 30. BYU is a Mormon school and school policy forbids games on Sundays. The NCAA solution is the following: If BYU wins their first two games they would swap with one of the teams from the Midwest subtree which plays its fourth round on Saturday the 29th. In the more likely event that BYU does not win its first two games the original schedule will hold.

      It's not hard to show that the uniqueness property above no longer holds and thus the tournament this year no longer can be represented as a tree.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 3/18/2003 9:52:57 AM

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.