Math 5100 Applied Combinatorics

2018-2019– Semester II

• Official Syllabus
• Lecture Notes
• Generic Course Objectives
• Classroom Behaviour
• On the use of electronic aparati
• In Praise of Lectures
• UPR Regulations concerning Academic Integrity and Reasonable Accommodation”

Miscellaneous Notes

1. Digraph Taxonomy
2. Directed Graphs
3. Equivalence Relations
4. Simple Graphs
5. Elementary Combinatorial Formulae
6. The Symmetric Difference
7. Balls in Boxes
8. Binomial-Multinomial Theorems
9. Multisets
10. Partitions
11. Inclusion Exclusion Principle
12. On the Number of Surjections
13. Function Digraphs
14. Group Actions
15. Orbit Stabilizer Theorem
16. Cycle Structure
17. Chemical Isomers and Coloring

Homework

1. Functions
2. Relations
3. Dirichlet Principle
4. Elementary Combinatorial Exercises
5. Balls in Boxes
6. Graph Combinatorics

Sample Exams

• MATH 5100 Practice Exam I

Syllabus

1. Preliminary material
   1. Digraphs
   2. permutation digraphs.
   3. orders and pre-orders.
   4. equivalence relations and partitions.
   5. lattices and boolean algebras.
2. Elementary Combinatorics
   1. the inclusion-exclusion principle.
   2. the pigeonhole principle.
   3. the binomial and multinomial theorems and their
      relationship with colorings.
3. Simple Graphs
   1. Paths and cycles.
   2. Graph connectivity.
   3. Trees.
   4. Bipartite graphs
   5. Isomorphism and
      automorphism of simple graphs.
4. Group Theory
   1. Permutation and symmetry groups.
   2. The dihedral groups.
   3. Permutation groups.
   4. Cyclic groups.
   5. Morphisms.
   6. Congruences and quotients.
   7. Cosets.
   8. Lagrange’s Theorem.
   9. Normal subgroups.
   10. The first isomorphism theorem.
   11. Cayley’s Theorem.
5. Group Actions
   1. Actions and subactions.
   2. Coloring type actions.
   3. The orbit-stabilizer theorem.
   4. Burnsides lemma.
6. Polya Theory
   1. The Polya–Redfield theorem.
   2. The counting of chemical isomers.
   3. The double group and counting of isomorphism classes of simple graphs.
   4. Miscellaneous applications.

Grade

Your grade will be based upon two partial exams and a comprehensive final exam. Extra credit will not be given. The grading scale will be no worse than the following:   A: 90-100;    B: 80-89;    C: 65-79;    D: 55-64;   F: < 55.   Copying or other forms of cheating will result in an automatic F for the course.   In accord with UPR regulations, persistent lateness or unexcused abscence from class may result in a failing grade and loss of financial support.

Grading Scale

Letter grade ( A, B, C, E or F )

Text

1. • Balakrishnan, V. K. Combinatorics McGraw Hill, 1995.

Bibliography

1. Peter J. Eccles, Introduction to Mathematical Reasoning, Cambridge University Press, 1999.
2. Ian Stewart and David Tall, Foundations of Mathematics, Oxford University Press, 1986.
3. R. F. Lax, Modern Algebra and Discrete Structures, (paperback) Addison Wesley 1997.
4. R. Lidl and G. Pilz, Applied Abstract Algebra, Springer, 1998.
5. G. Polya, Combinatorial enumeration of groups, graphs, and chemical compounds, Springer.
6. Robert F. Lax, Modern Algebra and Discrete Structures, Harper Collins, 1991.