Math 5100 Applied Combinatorics

Rendered by QuickLaTeX.com

2018-2019– Semester II

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

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

    • 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.