Recommended Courses in Discrete Mathematics

May 24, 2010 Mathematics 2,083 Views

MATH 8001 Graph Theory I.

Three credits. Three hours of lecture per week. Prerequisites: MATH 5CCC (Graph Theory).

Review of elementary graph theory. Trees. Matrix-tree theorem. Enumerating spanning trees of a graph. Graph decompositions. Connectivity and k–connectivity of graphs. Disjoint paths and connectivity of graphs. Menger’s and Whitney’s theorems. Graph assembling and disassembling of 3–connected and quasi 4-connected graphs. Various Euler problems. Hamiltonian cycles. The k–closure of a graph. Bondy–Chvátal’s theorem. Long cycles in a graph. Dirac’s theorem. Factors. Maximum and perfect matchings. Tutte’s and Edmonds–Gallai’s theorems. Berge–Tutte duality theorem. Perfect graphs. Lovász’ theorem. Edge colorings. Vising’s theorem. Independent sets and cliques. Vertex colorings. Brook’s theorem. Embeddings of graphs in the plane. Kuratowski’s, Whitney’s, MacLane’s and Kelmans’ planarity criteria. Five-colour and four-colour theorems on planar graphs. On the hamiltonicity of planar graphs.

Justification

It is difficult to overestimate the importance of graph theory in contemporary mathematics and its applications. Deep and elegant in itself, graph theory contains many wonderful ideas and results. Methods and ideas of graph theory are widely used in many other areas of mathematics. Graph theory has a tremendous number of applications. It would not be an exaggeration to say that graph theory is one of the most applicable areas of mathematics. It serves as a theoretical basis for a great variety of applied areas such as computer science, operations research, management science, electrical and mechanical engineering, chemistry, biology, etc. This course will be useful to the students who are planning to pursue doctoral studies in mathematics and its applications.

Objectives

This course will furnish the student with an excellent basis for study and research in a wide variety of mathematical areas. It will provide the student with skills which will be of use in mathematics and in various applications.

Syllabus

Historical remarks. Interrelations between graph theory and other areas of mathematics and some areas of science.
The main concepts of graph theory (review).
Trees. Spanning trees of a graph, and their algebraic and geometric interpretations.
Enumerating spanning trees of a graph (Matrix–tree theorem. Coding of spanning trees of a graph. The number of spanning trees of decomposable graphs).
Graph decompositions (Decomposition of graphs on components, edge blocks and vertex blocks (review). Decomposition of 2–connected graphs on 3–connected blocks).
Graph assembling and disassembling (Ear–decompositions of 3–connected, cyclically 4–connected and quasi–4-connected graphs).
Disjoint paths in a graph (Vertex and edge cuts, and connectivity of graphs. Menger’s and Whitney’s theorems. The Ford–Fulkerson theorem.).
Euler problems (A criteria for a graph and digraph to have an Euler tour or Euler trail (review). Euler trail set with at most one odd trail. Arborescences and Euler tours in digraphs.).
Hamiltonian problems (Hamiltonian cycles and paths. k–stable properties and k–closure of graphs. Bondy–Chvátal theorem. Sufficient conditions for graph hamiltonicity.).
Long cycles in a graph. Dirac’s theorem. Cycles through a given subset of elements in a graph. Kelmans–Lomonosov’s theorems.
Factors. Matchings and coverings in bipartite graphs (review). Stable marriage problem.
Matchings in a graph (Maximum and perfect matchings. Tutte’s theorem. Berge–Tutte duality theorem. Edmonds–Gallai structure theorem.).
Edge colorings. Vising’s theorem.
Independent sets and cliques.
Vertex colorings (2–coloring and odd cycles (review). Brook’s theorem (review). Coloring of special graphs. Perfect graphs. Lovász’ theorem. Strong perfect graph conjecture.).
Cycle and cocycle spaces of a graph (Combinatorial duality of graphs. Whitney’s cycle isomorphism theorem and its strengthenings and generalizations. Kelmans’ cycle semi–isomorphism and semi–duality theorems.).
Graph planarity (Various embeddings of a graph into a plane. Geometrical duality of graphs. Euler’s formula (review). Kuratowski’s, Whitney’s, MacLane’s and Kelmans’ planarity criteria.)
Coloring of planar graphs (Five–colour and four-colour theorems on planar graphs and related topics).
Hamiltonicity of planar graphs.

Text

D.B. West, Introduction to Graph Theory, Prentice Hall, 1996.
J.A. Bondy and U.S.R. Murty, Graph Theory With Applications, North Holland, Amsterdam, 1976.

Bibliography

B. Bollobás, Extremal Graph Theory, Academic Press, London, New York, San Francisko, 1978.
M. Behzad, G. Chartrand, and L. Lesniak, Graphs and Digraphs, Wadsworth International Group, 1991.
A.K. Kelmans, A New Planarity Criterion for 3-connected Graphs, J. Graph Theory, 5 (1981) 259–267.

Alexander Kelmans
San Juan 1995

MATH 8005. Discrete Algorithms.

Three credits. Three hours of lecture per week. Prerequisites: MATH 5CCC (Graph Theory).

Branch and bound strategy. Dynamic programming principle. Optimal paths in graphs. Optimal spanning trees in graphs. 2–coloring and odd cycles in a graph. Depth–first search in a graph and its applications. Properties of depth–first search tree. Graph decomposition algorithms. Graph assembling algorithms. Graph planarity algorithms. Euler problems. Hamiltonian problems. Some packing and covering problems for graphs. Metric problems on graphs. Set transformation algorithms. Search trees of different type. Various sorting algorithms. The main ideas of the NP–theory (the theory of problem complexity).

Justification

Many problems in mathematics and its applications are of a discrete nature. Usually the number of feasible solutions to such a problem increases very rapidly with its size and therefore, it is impossible to find a required solution by searching all alternatives, even with the fastest computers. Accordingly, it is imperative to seek efficient algorithms for solving discrete problems. This course will be very useful to the students studying mathematics and of particular interest to those students who are planning to pursue doctoral studies in discrete mathematics and its applications.

Objectives

This course will provide students with some of the main ideas, approaches and results that are useful in finding efficient algorithms. It will furnish the student with an excellent basis for study and research in a wide variety of mathematical areas and will provide him with skills which will be of use in mathematics and its applications.

Syllabus

Branch and bound strategy.
Dynamic programming principle.
Optimal paths in graphs (Shortest path in a graph or digraph with nonnegative or arbitrary edge-weights. k–shortest paths. Min-max paths).
Optimal trees in graphs (A spanning tree and a minimum spanning tree in a graph, and a minimum directed tree in a digraph. Min–max and dynamic min–max spanning trees. Steiner trees in graphs. Enumerating spanning trees of graphs. Description of all minimum spanning trees of a graph.).
2–coloring and odd cycles in a graph.
Depth–first search in a graph and its applications. Properties of depth–first search tree.
Graph decomposition algorithms (Finding components, edge and vertex blocks of a graph, and strongly connected components of digraphs).
Graph assembling algorithms (Ear–decompositions for connected, edge and vertex 2–connected, and 3–connected graphs).
Graph planarity algorithms.
Euler problems (Finding an Euler trail and Euler cycle in a graph or digraph, Fleury’s algorithm. Euler trail set with at most one odd trail. Labyrinth problem. De Bruijn sequences and graphs. The Chinese postman problem.)
Hamiltonian problems (Finding a Hamiltonian path and cycle in a graph. Travelling salesman problem.).
Packing and covering problems for graphs (Matching problems. Disjoint paths. Various generalizations and related problems).
Metric problems on graphs (Radius, diameter, center, and median of a graph. Optimal center location problems for weighted graphs).
Set transformation algorithms. Search trees of different type. Permutations and various sorting algorithms.
The main ideas of the NP–completeness theory.

Text

S. Even, Graph Algorithms, Computer Science Press, 1979.
N. Christofides, Graph Theory. An Algorithmic Approach, Academic Press, 1975.

Bibliography

A.V. Aho, J.E. Hopcroft, J.D. Ulman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1976.
A.V. Aho, J.E. Hopcroft, J.D. Ulman, Data Structures and Algorithms, Addison-Wesley, 1983.
D.E. Knuth, The Art of Computer Programming. Vol.1. Fundamental Algorithms, Addison-Wesley,, 1973.
D.E. Knuth, The Art of Computer Programming. Vol.3. Sorting and Searching, Addison-Wesley, 1973.

Alexander Kelmans
San Juan 1995

MATH 8006. Computers and Intractability. Theory of NP-completeness.

Three credits. Three hours of lecture per week. Prerequisite MATH 8005.

Computers, problems, algorithms, and complexity. Polynomial time algorithms and intractable problems. Provably intractable problems. NP-complete problems. Deterministic Turing machines and the class P. Nondeterministic computation and the class NP. The relation between P and NP. Polynomial transformations and NP-completeness. The Cook–Levin theorem. Basic NP-complete problems. Applying NP-completeness to approximation problems. The structure of NP. The polynomial hierarchy. The complexity of enumeration problems.

Justification

Many problems in mathematics and its applications are of a discrete nature. Usually the number of feasible solutions to such a problem increases very rapidly with the its size and therefore, it is impossible to find a required solution by searching all alternatives, even with the fastest computers. Accordingly, it is imperative to seek efficient algorithms. Unfortunately for most problems, efficient algorithms are not known, and it is not even clear whether such algorithms exist. NP-theory provides an approach for classifying problems according to their complexity (i.e. the degree of their intractability to computers). The theory considers a very rich class of problems (the so called class NP containing most “real” problems. One of the main results of the theory is the fact that there exists a “most complicated” problem in this class. The theory provides a long list of “real” problems that are most complicated. Moreover, most of the problems arising in applications turn out to be “most complicated”. In fact it is very difficult to find a nontrivial problem which can be solved efficiently. Actually the finding of such a “good” problem is a kind of discovery. Typically such results are based on intrinsic properties of the problem and contain deep and non–trivial mathematical ideas. Various “good” problems and main ideas and approaches providing efficient algorithms are discussed in the courses “Discrete Algorithms” and “Combinatorial Optimization I”. The strategy for solving a problem depends on its complexity status. This course provides students with the main ideas, approaches and results concerning the classification of problems by their compexity. This course will be of particular interest to those students who are planning to pursue doctoral studies in discrete mathematics and theoretical computer science.

Objectives

This course will furnish the students with a deeper understanding of the main problems and difficulties we face in our attempts to use computers for solving “real” problems, and with the main mathematical ideas and results that help to clarify and sometimes to overcome such difficulties.

Syllabus

Computers, Complexity, and Intractability: Problems, algorithms, and complexity. Polynomial time algorithms and intractable problems. Provably intractable problems. NP–complete problems.
The Theory of NP-Completeness: Decision problems, languages, and encoding schemes. Deterministic Turing machines and the class P. Nondeterministic computation and the class NP. The relation between P and NP. Polynomial transformations and NP-completeness. The Cook–Levin theorem.
Proving NP-Completeness Results: Basic NP-complete problems. Some techniques for proving NP-completeness.
Using NP-Completeness to Analyze Problems: Analyzing subproblems. Number problems and strong NP-completeness. Time complexity as a function of natural parameters.
NP-Hardness: Turing reducibility and NP-hard problems.
Coping with NP-Complete Problems: Performance guarantees for approximation algorithms. Applying NP-completeness to approximation problems.
Beyond NP-Completeness: The structure of NP. The polynomial hierarchy. The complexity of enumeration problems. Polynomial space completeness. Logarithmic space. Proofs of intractability and P vs. NP.

Text

M.G. Garey and D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-completeness, W.H.Freeman and Company, San Francisko, 1979.

Bibliography

S. Even, Graph Algorithms, Computer Science Press, 1979.
A.V. Aho, J.E. Hopcroft, J.D. Ulman, Data Structures and Algorithms, Addison-Wesley, 1983.

Alexander Kelmans San Juan 1995

MATH 8011. Enumerative Combinatorics I.

Three credits. Three hours of lecture per week. Prerequisites: MATH 8001, MATH 6201, MATH 6150

Review of elementary combinatorics. Outline of the main problems and approaches of enumerative combinatorics. Enumerating trees. Matrix–tree theorem. Coding of trees. Counting Euler cycles in a digraph. Counting and listing of nonisomorphic trees of different types. Generating function method in enumerative combinatorics. Enumerating graphs of different types. Pólya’s counting theory of nonisomorphic objects. Enumerating nonisomorphic graphs of different types. Principle of inclusion and exclusion. Lattices, their Möbius functions and Möbius algebras. Asymptotic results in enumerative combinatorics.

Justification

Enumerative combinatorics is an important area of discrete mathematics that concerns the problems of counting and/or listing of objects of different types. It contains many interesting ideas and results that are useful not only in itself but also in various areas of mathematics (analysis, probability, queuing theory, random structures, etc.) and in many applications (physics, chemistry, computer science, network reliability, statistics, electrical circuits, etc.). On the other hand, enumerative combinatorics uses concepts, ideas and results from different areas of mathematics (analysis, group theory, theory of posets and lattices, etc.).

This course will be very useful to the students who are planning to pursue doctoral studies in mathematics and its applications.

Objectives

The goal of this course is to make students conversant with the main results and ideas of enumerative combinatorics and some important applications. The students will become familiar with various methods and approaches (analytical, algebraic, and combinatorial) that can be used to enumerate objects of different types. This course will provide the student with ideas and skills which will be of use not only in mathematics but in various applications. Students from other branches of science or engineering who have a good background in mathematics may well find this course to be extremely useful.

Syllabus

Review of elementary combinatorics (Permutations. Combinations. Multinomial coefficient. Binomial expansion. Binomial theorem.).
Outline of main problems and approaches of enumerative combinatorics (Counting and listing. Enumeration problem of different objects and their isomorphism classes.).
Enumerating trees. Matrix–tree theorem. An algorithm for finding formulas of the number of spanning trees of decomposable graphs. Coding of trees of a complete graph and its generalizations. Counting Euler cycles in digraphs. Counting and listing of nonisomorphic trees of different types.
Generating function method in enumerative combinatorics. Enumerating graphs of different types (graphs and digraphs of given size, connected and 2–connected graphs, rooted graphs, Eulerian graphs, tournaments, orientations of a graph, etc.).
Pólya’s counting theory of nonisomorphic objects (Groups and graphs. The cycle index of a permutation group. Burnside’s theorem. Pólya’s theorem.). Enumerating nonisomorphic graphs of different types.
Principle of inclusion and exclusion. Partially ordered sets and their Möbius functions (Posets of different types. Lattices. Möbius functions and Möbius algebras. The Möbius inversion formula). Enumeration of permutations of certain types.
Asymptotic results in enumerative combinatorics.

Text

F. Harary, E.M. Palmer, Graphical Enumeration, Academic Press, New York and London, 1973.
R. Stanley, Enumerative Combinatorics, Volume I, Wadsworth and Brooks/Cole, Monterey, California, 1986.
A. Tucker, Applied Combinatorics, 3rd. ed.,Wiley, 1995.

Bibliography

I.P. Goulden and D.M. Jackson, Combinatorial Enumeration, Wiley, 1983.
D.E. Knuth, The Art of Computer Programming, Vol. I, Addison-Weseley, 1973.
F.S. Roberts, Applied Combinatorics, Prentice–Hall, 1984.
C.L. Liu, Introduction to Combinatorial Mathematics, McGraw-Hill, 1968.
A.K. Kelmans, Spanning Trees of Extended Graphs, Combinatorica 12 (1) (1992) 45–51.

Alexander Kelmans
San Juan 1995

MATH 8021. Algebraic Combinatorics I

Three credits. Three hours of lecture per week. Prerequisites: MATH 6202, Mate 8001.

Linear Codes. t-error correcting binary codes and finite fields. Cyclic codes. Perfect codes. Block designs. Latin squares. Pairwise balanced designs. Hadamard matrices. Difference sets. Symmetric designs. Finite geometries. Singer’s theorem. Transversal designs. Group divisible designs. Steiner triple systems. Kirkman triple systems. Strongly regular graphs. Association schemes. Distance-regular graphs. Distance transitivity.

Justification

Algebraic Combinatorics is an important part of discrete mathematics. It deals with algebraic structures whose symmetries are of special interest. Frequently, these structures have certain extremal properties that make them especially suitable for applications in computer and communication sciences. This course will be very useful to students who are planning to pursue doctoral studies in mathematics and its applications.

Objectives

The goal of this course is to make students conversant with the main results and ideas of algebraic combinatorics and some important applications. The students will become familiar with algebraic methods and approaches that can be used to study discrete structures as well as combinatorial methods that are helpful in obtaining and understanding a variety of algebraic results. The study of this area will equip the students to use both algebra and combinatorics in their research.

Syllabus

Different type of codes (Linear codes, Hamming codes and their duals, non linear Codes, double-error binary correcting Hamming codes). Properties of codes and their decoding. Construction of new codes from old ones. Finite fields and some applications to coding. Minimal polynomials. Irreducible polynomials. The automorphism groups of finite fields. Cyclic codes. Generator polynomial. Check polynomial. Factors of x^n-1. t-error-correcting binary codes. Perfect codes. Block designs. Latin squares. Pairwise balanced designs. Systems of distinct representatives. Hadamard matrices. Difference sets and systems. Multipliers for difference sets. Symmetric designs. Hadamard designs and matrices. The Bruck-Chowla-Ryser theorem. Finite projective geometries. Singer’s theorem. Orthogonal latin squares. Orthogonal arrays. Transversal designs. Group divisible designs. Wilson’s theorem. Steiner triple systems. Cyclic Steiner triple systems. Kirkman triple systems. t-designs. Strongly regular graphs. Direct product and Hamming graphs. d-cubes. Association schemes. Hamming’s association scheme. Johnson’s scheme. Subsets of association schemes. Distance-regular graphs. Distance transitivity.

Text

C. Godsil, Algebraic Combinatorics, Chapman and Hall, 1993.
E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin-Cummings, 1984.
F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1976.

Bibliography

V. Pless, The Theory of Error Correcting Codes, 2nd ed., Wiley, 1990.
I. Anderson, Combinatorial Designs, Wiley, 1990.
W.D. Wallis, Combinatorial Designs, M. Dekker, 1988.
A.E. Brouwer, A.M. Cohen and A. Neumaier, Distance-Regular Graphs, Springer Verlag, 1989.

MATH 8031. Combinatorial Optimization I.

Three credits. Three hours of lecture per week. Prerequisites: MATH 6881, MATH 8001.

Elements of linear and integer programming: branch and bound method and its application to combinatorial optimization problems. Network flow theory and its generalizations: statical maximal flow, feasibility theorems and combinatorial applications, minimal cost flow problems, multi–terminal maximal flows, multi–commodity flows. Matching theory and its generalizations: matchings in bipartite graphs, size and structure of maximum matchings, bipartite graphs with perfect matchings, general graphs with perfect matchings, some graph–theoretical problems related to matchings, matchings and linear programming, matching algorithms, the f–factor problem, vertex packing and covering, some generalizations of matching problems.

Justification

Optimization problems arise in various areas of mathematics as well as in applications (computer science, management science, operations research, physics, engineering, statistics, etc.). The main feature of combinatorial optimization problems is that feasible solutions are of a discrete nature, and therefore the classical methods of optimization based on “small” variations of a feasible solution cannot be applied. Typical examples are integer programming problems which are in general very difficult (NP-hard). Nevertheless efficient algorithms can be found for some natural combinatorial optimization problems. The main approaches, ideas and results along these lines will be discussed in this course. This course will be of particular interest to those students who are planning to pursue doctoral studies in Discrete Mathematics and Theoretical Computer Science.

Objectives

This course will furnish the students with the main approaches, ideas and results, that can be used to find efficient algorithms for solving some special combinatorial optimization problems or heuristic and/or approximation algorithms for certain combinatorial problem that arise in applications.

Syllabus

Elements of linear and integer programming. Branch and bound method and its application to combinatorial optimization problems.
Network flow theory and its generalizations.
1. Statical maximal flow: Networks. Flows in networks. Cuts. Maximal flow. Multiple sources and sinks. The labelling method for solving maximal flow problems. Dinitz–Tarjan’s and Karzanov’s algorithms for maximal flow problems. Flows in undirected and mixed networks. Node capacities and other extensions.
2. Feasibility theorems and combinatorial applications: Supply–demands theorems. Circulation theorem. The König–Egerváry and Menger graph theorems. Construction of a maximal independent set of admissible cells. A bottleneck assighnment problem. Unicursal graphs. Dilworth’s chain decomposition theorem for partially ordered sets. Minimal number of individuals to meet a fixed schedule of tasks. Set representatives. Matrices composed of 0’s and 1’s.
3. Minimal cost flow problems: The Hitchcock problem. The optimal assignment problem. Equivalence of Hitchcock and minimal cost flow problems. The minimal cost supply–demand problem. Maximal dynamic flow. Minimal cost circulations.
4. Multi–terminal maximal flows: Realization conditions. Equivalent networks. Network synthesis.
5. Multi–commodity flows.
Matching theory and its generalizations:
1. Matchings in bipartite graphs: The theorems of Konig and P. Hall. A bipartite matching algorithm. Matchings, flows and measures.
2. Size and structure of maximum matchings: Tutte’s and Berge’s min-max theorems. Edmonds–Gallai structure theorem.
3. Bipartite graphs with perfect matchings: Elementary graphs and their ear structure. Minimal elementary bipartite graphs. Decomposition into elementary bipartite graphs.
4. General graphs with perfect matchings: The canonical partition G. Saturated graphs. Ear structure of 1-extendable graphs. Factor-critical and bicritical graphs. Lovász theorem on ear–decompositions of factor–critical graphs.
5. Some graph-theoretical problems related to matchings: 2–matchings and 2–covers. Matchings, 2-matchings and the König property. Hamiltonian cycles and 2-matchings. The Chinese postman problem. Optimum paths, cycles, joins and cuts.
6. Matchings and linear programming: Linear programming and matchings in bigraphs. Matchings and fractional matchings. The matching and fractional matching polytopes. Chromatic index. The dimension of the perfect matching polytope.
7. Matching algorithms: The Edmonds matching algorithm. Weighted matchings. An algorithm based upon the Edmonds–Gallai theorem. A linear programming algorithm for matchings.
8. The f–factor problem: Reduction principles. A structure theory for f–factors. Realization of degree sequences.
9. Vertex packing and covering: Critical graphs. Vertex packing polytopes. Hypergraph matching. Vertex packing in claw-free graphs.
10. Some generalizations of matching problems: Optimal packing of special subgraphs of a graph. Kelmans’ min-max and structure theorems on induced stars in a graph. Packing paths, cycles, joins and cuts.

Text

M. Plummer and L. Lovász, Matching Theory, North-Holland, 1986.
L.R. Ford and D.R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, New Jersey, 1962.

Bibliography

E. L. Lawler, Combinatorial Optimization; Networks and Matroids, Holt Rinehart and Winston, New York, 1976.
A. Schrijver, Theory of Linear and Integer Programming, John Wiley and Sons, Chichester, New York, Brisbane, Toronto, Singapore, 1987.
G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, Chichester, 1988.
T.C. Hu, Integer Programming and Network Flows, Reading, Addison–Wesley Publ. Co., London–Don Mills, Ont., 1970.

Alexander Kelmans San Juan 1995

MATH 8041. Matroid Theory I.

Three credits. Three hours of lecture per week. Prerequisites: MATH 6150, MATH 8001.

Fundamental concepts and axioms of matroid theory. Duality in matroids and matroid operations. Vector representation of matroids. The matroid of a graph and graph planarity. Greedy algorithms on matroids. The union of matroids and its rank function. Efficient algorithms for some combinatorial optimization problems (packing, covering, intersection etc.) on matroids with applications to a variety of combinatorial objects (e.g. graphs, matrices, algebraic dependencies, transversals).

Justification

It is difficult to overestimate the importance of matroid theory in contemporary applied and theoretical mathematics. It provides a common basis for understanding and solving a variety of problems in a wide range of areas including graph theory, linear algebra, geometry, transversal theory, block design, combinatorial lattice theory and algebraic geometry. Matroid theory serves as a link between combinatorics and other mainstream areas of mathematics. It plays an extremely important role in combinatorial optimization where it can be used to find combinatorial structures for which the corresponding optimization problems can be solved in polynomial time. Moreover, it provides efficient procedures (described in rather general terms) for solving those problems and for designing the corresponding polynomial time algorithms. This course will be of particular interest to those students who are planning to pursue doctoral studies in either pure or applied mathematics.

This course will be of particular interest to those students who are planning to pursue doctoral studies in either pure or applied mathematics.

Objectives

This course will furnish the student with an excellent basis for study and research in a wide variety of areas in pure and applied mathematics. It will provide the student with skills which will be of use not only in theoretical mathematics but in applications as diverse as communications networks, reliability theory, computer science and optimization.

Syllabus

Fundamental concepts and axioms of matroid theory.
Independent sets and bases of a matroid.
Circuits and the rank function of a matroid.
Examples of matroids.
Duality in matroids.
Operations on matroids and submatroids (truncation, restriction, contraction, etc.).
The closure operator, closed sets = flats = subspaces, and hyperplanes of a matroid.
The lattice of a matroid.
Vector representation of matroids, the matroid of a linear subspace, special matroids.
Matroid connectivity. The matroid of circuits of a graph, circuit isomorphisms and semi-isomorphisms of graphs.
Geometrical and matroid dualities of graphs, a planarity criterion of a graph in terms of its matroid.
The greedy algorithm, the “greedy” characterization of matroids.
Minimax and dynamic minimax problems for matroids.
A description of the matroid of the minimum bases of a matroid.
The union of matroids and its rank function.
Efficient algorithms for finding a base of the union of matroids, and for covering, packing and intersection problems for matroids.

Text

D.J.A. Walsh, Matroid Theory, Academic Press, 1976.

Bibliography

J. G. Oxley, Matroid Theory, Oxford University Press, New York, 1992.
E. L. Lawles, Combinatorial Optimization Networks and Matroids, Holt Rinehart and Winston, New York, 1976.
W. T. Tutte, Introduction to the Theory of Matroids, Elsevier, New York, 1970.
A. K. Kelmans, Matroids and Combinatorial Optimization Problems, Institute of Control Sciences, Moscow, 1989.
P. D. Seymour, Decomposition of Regular Matroids, J. Combin. Theory B 28(1980) 305–359.

Alexander Kelmans
San Juan 1995

MATH 8051. Convex Polytopes I.

Three credits. Three hours of lecture per week.
Prerequisites: MATH 6150.
The basic concepts of linear and affine geometry. Convex sets and their support properties. Supporting hyperplanes. The theorems of Radon, Helly and Caratheodory. Convex polytopes and their faces. Polarity and duality in convex polytopes. Cell-complexes and Schlegel diagrams. Shelling the boundary complexes. The cubical complexes. The graph of a d-polytope and its properties. 3-polytopes and Steinitz’ theorem. Affine and projective transformations. The fundamental theorem of projective geometry. Simplicial and simple polytopes. Euler’s theorem and the Dehn-Sommerville equations. Lower bound and upper bound theorems for convex polytopes.

Justification

The theory of convex polytopes is of importance in many areas of mathematics, especially in discrete and modern applied mathematics. Convex polytopes provide the basis for convexity theory which is of great utility in analysis, geometry, optimization, and control theory. Special types of convex polytopes including transportation, knapsack and doubly stochastic polytopes have each become a subject of much fruitful research. An extremely important class of planar graphs, namely 3-connected one’s are precisely three dimensional polytopes. Thus the area of convex polytopes, lies on on the border between main stream pure mathematics and modern applied mathematics. Accordingly, this course will be of use not only to Ph. D. students in discrete mathematics and theoretical computer science but also to students of analysis and applied mathematics.

Objectives

The main goal of the course will be to prepare students for research in discrete mathematics or other areas of mathematics where these fundamental ideas are important. Of course those students from other branch of science, or even engineering who have good background in mathematics may well find the course to be extremely useful.

Syllabus

The basic concepts of linear and affine geometry; affine, convex and polyhedral sets, convex hull, affine hull and hyperplanes.
Theorems of Radon, Helly and Caratheodory. Supporting hyperplanes and support properties of convex sets. Convex polytopes and their faces, vertices, edges, subfacets and facets.
Polarity and duality in convex polytopes.
Classical examples; simplices, hypercubes, pyramids, bipyramids, prisms, r-fold pyramids, r-fold prisms, parallelotopes and cross polytopes.
Cell-complexes, diagrams and schlegel diagrams, shelling the boundary complexes, the cubical complexes.
Graph of a d-polytope and its d-connectedness. 3-polytopes and Steinitz’ theorem.
Affine and projective transformations. The fundamental theorem of projective geometry. Affine, projective and combinatorial equivalence of polytopes.
Cyclic and neighborly polytopes, simplicial and simple polytopes. Duality between classical polytopes. Combinatorial implications of duality.
Euler’s theorem and Dehn-Sommerville equations. Lower bound and Upper bound theorems for convex polytopes. A study of simple convex polytopes and the simple polytopal approach to the lower and upper bound theorems. Mc-Mullen’s condition and f-vectors of convex polytopes.

Text

A. Bronstead, An Introduction to Convex Polytopes, Springer Verlag, 1992.

Bibliography

B. Grunbaum, Convex Polytopes, Wiley, 1967.
P. McMullen and G.C. Shephard, Convex Polytopes and Upper Bound Conjecture, London Math. Soc. Series, Vol 3, Cambridge, Cambridge University Press, 1971.
Rolf Schneider, Convex Bodies: The Brünn-Minkowski Theory, Cambridge University Press, 1993.