Combinatorial Enumeration and Optimization

Homepage

Courses

Organisers

Location

Events

Registration

Questions

Poster

A/Prof Ian Wanless
Monash University

Dr Thomas Britz
The University of New South Wales

Synopsis

Combinatorial enumeration deals with clever ways of counting combinatorial objects such as permutations, partitions, graphs, words etc. We will concentrate on using generating functions to do the counting for us. Combinatorial optimisation deals with clever ways of arranging objects so that they fit together and includes strategies for solving scheduling problems, planning optimal travel routes, and designing cheap and yet robust communications networks. We will consider several classical (and beloved) optimization theorems.

Weeks 1 and 2: Combinatorial Enumeration (Ian Wanless)

We will learn how to use the magic of ordinary and exponential generating functions in order to:

  • find explicit formulae for combinatorial numbers
  • solve recurrence relations
  • discover bijections
  • apply the principle of inclusion-exclusion
  • estimate the growth rate of a sequence
  • prove identities

Weeks 3 and 4: Combinatorial Optimization (Thomas Britz)

  • Part A: Min-Max Theorems
    • Hall's Marriage Theorem
    • K├Ânig's Theorem and Dilworth's Theorem
    • Applications
    • Generalizations
  • Part B: Graph Algorithms
    • Augmenting Paths
    • Spanning Trees
    • Traversing Circuits

Contact hours

28 hours of hours spread over four weeks, plus consultation as required.

Prerequisites

No prior experience of generating functions, combinatorics or graph theory will be assumed. All that is required is a basic level of mathematical maturity that any honours student should have.

Resources

  1. H.S.Wilf, Generatingfunctionology, 3rd ed, A K Peters, Wellesley, MA, 2006.
    Also available for free from the author's website: http://www.math.upenn.edu/~wilf/
  2. J.H. van Lint and R.M. Wilson, A course in combinatorics, 2nd ed, Cambridge University Press, Cambridge, 2001.

About Ian Wanless

Ian was awarded his PhD in 1998 from the Australian National University. He then had short stints at University of Melbourne, Oxford University, ANU and Charles Darwin University before settling at Monash University, where he is now an associate professor. The picture shows him at the grave of his inspiration, the legendary Leonhard Euler.

About Thomas Britz

Thomas Britz received the PhD degree in Mathematics from the University of Aarhus, Denmark, in 2003. Since then, he has held postdoctoral positions at the University of Victoria, Canada, at the Technical University of Denmark, and at the University of New South Wales, where he now is a Lecturer. His research interests mostly lie in combinatorics and extremal set theory, though he is also interested in related areas such as coding theory, combinatorial matrix theory, and applications of all these theories.