Introduction to Higher Mathematics
Mathematics 750 – Unit 2: Combinatorics and Graph Theory
Brown University – Fall, 2018
Professor Joseph Silverman

 Topic We will study topics from combinatorics and graph theory. The text for this unit of Math 750 may be downloaded from: Introduction to Higher Mathematics: Unit 2: Combinatorics and Graph Theory . Mathematics Department, Kassar House, Room 202 863-1124 jhs@math.brown.edu Math 750–760 Course Website Math 750–760 Unit #2 Website Monday 9:30-10:15 am (starts Oct 15, ends Nov 5) Thursday 10:00-11:00 am (starts Oct 11, ends Nov 1) Click here for Information about Office Hours and Other Academic Resources TuTh 1:00–2:20pm (J hour) Watson Institute Room 116 (111 Thayer Street) Homework assignments are posted below. It is best if you do the reading before the class where we cover the material.

Schedule, Reading Assignments, HW Assignments
Class Date Chapter Reading Topic Homework Due Date Optional Challenge/Fun Problems
0 Review of Summation Notation (Review this online material before Unit #2 starts)
1 Tues 10/9 1 1.1–1.2 Pigeonhole Principle. Putting things in order; multiplication rule. HW 1: # 1.1, 1.3, 1.6, 1.8, 1.9 Thur 10/11 # 1.7
2 Thur 10/11 1 1.3–1.4 Bijections. Subsets. (Class activity: randomized playlists.) HW 2: # 1.10, 1.12, 1.14, 1.15, 1.16, 1.18 Thur 10/18 # 1.13, 1.17, 1.19
3 Tues 10/16 1 1.4–1.5 Subsets; stars and bars. (Class activity: Catalan bijections.)
4 Thur 10/18 1 1.5–1.6 Inclusion/exclusion. Derangements. HW 3: # 1.20, 1.21, 1.23 Thur 10/25 # 1.22, 1.24
5 Tues 10/23 1 & 2 1.6 & 2.1 Erdös-Ko-Rado theorem. Graphs. (Class activity: sprouts)
6 Thur 10/25 2 2.1–2.2 A zoo of graphs. Counting trees. (Class activity: counting trees.) HW 4: # 2.1, 2.2, 2.3, 2.5 , 2.10, 2.11
For 2.5, you do not have to write down the Prüfer code.
Thur 11/1 # 2.6, 2.7, 2.9, 2.14
7 Tues 10/30 2 2.3 Graph coloring. The five color map theorem. (Class activity: coloring a map)
8 Thur 11/1 2 2.4 The five color map theorem. Non-planar graphs. (Class activity: Königsberg bridge problem) HW 5: Study for exam. Tues 11/6
9 Tues 11/6 Unit 2 Exam — Click here for Exam Solutions

Course and Unit Goals: Math 750–760 is a year-long class that exposes students to six basic areas of mathematics. It is team taught by six members of the faculty. Fall topics include logic, set theory, combinatorics/graph theory, and analysis. Spring topics include number theory, abstract algebra, and geometry. The class emphasizes rigorous proofs and concrete interesting examples. The specific goals for the Combinatorics and Graph Theory Unit are to learn fundamentals topics from combinatorics and graph theory.

Learning Activities and Time Allocation: Learning activities for this part of the course include class attendance, weekly problem sets, and a unit exam. The time to complete these activities are (1) attending lectures, approximately 3 hours/week; (2) reading material in the book, approximately 2 hours/week; (3) working on the problem sets, approximately 7 hours/week.

Assessment: Course grades will be determined by the quality of problem sets submitted and by grades on the unit exams and the final exam.

Expectations of Students: It is expected that students will attend all lectures and participate in class discussion in an appropriate manner. Assignments are due on the listed dates. All students are expected to abide by Brown's academic code, which may found here

Syllabus:

1. Combinatorics
• Pigeonhole principle
• Putting things in order
• Bijections
• Subsets and the binomial theorem
• The principle of inclusion/exclusion
2. Graph theory
• Graphs
• Spanning trees
• Graph coloring
3. As time permits, further topics chosen from:
• Extremal combinatorics
• Matching
• Ramsey theory
• The probabilistic method

Academic Support: Brown University is committed to full inclusion of all students. Please inform me early in the term if you have a disability or other conditions that might require accommodations or modification of any of these course procedures. You may speak with me after class or during office hours. For more information, please contact Student and Employee Accessibility Services at 401-863-9588 or SEAS@brown.edu.