Preliminary Examination

in Mathematical Computer Science

Combinatorics Cluster

This is one of four possible preliminary exams in computer science. Students are requested to solve 5 out of 8 or 9 problems. Past exams should be available from the Mathematics Library or the office of the Director of Graduate Studies or the MCS web home page. Questions are drawn from the following courses and their prerequisites.

**MCS 521 Combinatorial Optimization:**The course can cover different topics each time it is offered from among the following. Network optimization (shortest paths, maximum flows, minimum-cost flows, matching problems), matroid theory (elementary properties, duality, greedy algorithm, matroid sum and matroid intersection), polyhedral combinatorics (theorems of the alternatives and linear programming duality, faces, extreme points and facets of polyhedra, integral polyhedra).

*Texts:*- E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.
- R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows, Prentice Hall, 1993.
- G. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization, Wiley 1988.

**MCS 531 Introduction to Error-Correcting Codes:**Basic concepts in coding such as weight distribution, covering radius, questions about minimum distance, various families of codes such as greedy codes, self-dual codes, perfect codes.

*Text:*- V. Pless, The Theory of Error-Correcting Codes, Wiley Interscience, Second ed., 1989.

**MCS 591 Advanced Topics in Combinatorial Theory:**The course can cover different topics each time it is offered from among the following. Graphs and trees, coloring of graphs and Ramsey theory, combinatorial designs, systems of distinct representatives, Moebius inversion, Stirling and Gaussian numbers, recursions and generating functions, Polya theory of counting, Dilworth theorem and extremal set theory.

*Texts:*- J. H. Van Lint and R. M. Wilson: A Course in Combinatorics, Cambridge University Press, 1992.
- R. A. Brualdi, Introductory Combinatorics, Second ed., Prentice Hall, 1992.

Web Source: http://www.math.uic.edu/~hanson/CombinPrelimSyllabus.html

**
Email Comments or Questions to Professor Hanson
or
Email Comments or Questions to Professor Peled
**