Difference between revisions of "Combinatorics and Graph Theory"
| Line 17: | Line 17: | ||
[[Category: Courses]] | [[Category: Courses]] | ||
| + | [[Category: Bristol]] | ||
| + | [[Category: Easton]] | ||
| + | [[Category: Haverford]] | ||
| + | [[Category: Santa Cruz]] | ||
| + | [[Category: Tempe]] | ||
Revision as of 17:34, 30 September 2017
Combinatorics and Graph Theory (DMAT), formerly known as Discrete Math, is a CAA course where students use math concepts for real world situations. This course is offered at Haverford and Santa Cruz. It was formerly offered at Easton. It has a prerequisite of Algebra I.
Course Description
During the CTY all-site meeting on opening day, what is the smallest number of students who need to enter the auditorium before there will be at least three students in the room who already knew each other before attending CTY, or at least three students who were all strangers before they arrived? This problem can be illustrated by a type of graph in which vertices representing students are connected by edges that are colored to indicate friendships. This course introduces students to such problems and how to approach them as they learn the mathematics of combinatorics.
This course begins with an exploration of enumerative combinatorics. Students use different techniques of mathematical proof and ideas in set theory to solve a variety of problems, and they study topics such as binomial coefficients, permutations, and partitions. For example, students employ bijective functions to turn seemingly tedious counting problems into much simpler problems, such as how to determine the number of games played in the March Madness tournament without needing to pull out your bracket and count one by one.
Students then investigate graph theory, an area of mathematics that is used in modern applications in fields such as computer science, counterterrorism, and navigation. One famous question in graph theory posed in the early 1800s—whether you can color any map using just four colors so that no two adjacent areas share the same color—took over 100 years for mathematicians to answer in the affirmative. Students explore this question and other historic problems in graph theory as they delve into concepts such as cycles, planarity, algorithms, and graph colorings.
Along the way, students encounter problems that are challenging and fun, and that can be solved with creativity and determination, even without a prior background in college-level math.
Note: A graphing calculator, such as a TI-83 Plus or TI-84, is required.
