Combinatorics and Graph Theory

From RealCTY
Jump to navigation Jump to search
Combinatorics and Graph Theory
Mathematics Course
Course CodeDMAT
Year Opened2004
Sites OfferedSCZ
Previously OfferedASU, BRI, EST
Part of a series on
Realcty logo 20060831.png
CTY Courses
Category · Template · Baby CTY
Sites
Allentown · Bristol · Haverford · Hong Kong · Santa Cruz · Seattle
Humanities
Foundations of Psychology
Bioethics · Great Cases: American Legal History
Introduction to Logic · Philosophy
The Roots of English · Comparative Law
Writing
Whodunit? Mystery and Suspense in Literature and Film
Crafting the Essay
The Graphic Novel
Math
Geometry through Art
Paradoxes and Infinities · Mathematical Modeling
Computer Science
Foundations of Programming
Economics
The Mathematics of Money · Game Theory and Economics
Science
Zoology · Principles of Engineering Design
Biotechnology · Chemistry in Society
Introduction to Astronomy
Anatomy and Physiology
The Physics of Sports
Whales and Estuary Systems · The Chesapeake Bay
Defunct Courses
Colonial Life · Beyond America
Civil War and Reconstruction · US Environmental History
Victorian Women · America in the Cold War
The Making of California · The Civil Rights Movement
Politics of Place · Eastern Philosophy
Drama · Writing and Reading Seminar
Public Speaking and Communication · Poetry
Writing the History Paper · Writing American Autobiography
The Short Story · Drama 2: From Stage to Screen
Shakespeare in Performance · Math and Music
Math Workshop · Mathematical Investigations
Math and Art · Algebra and its Applications
Geometry and its Applications · Probability and Statistics
Chaos and Fractals · Introduction to Geology
Exercise Physiology · Environmental Engineering
Nuclear Science · The Critical Essay: Cinema
Medical Sciences: Pharmacology & Toxicology · The Modern City
Writing About Place: The Monterey Bay

Course Description

From the CTY Summer Catalog:

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.