Courses:

Combinatorial Theory: Introduction to Graph Theory, Extremal and Enumerative Combinatorics >> Content Detail



Study Materials



Readings

Amazon logo When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

The following textbooks are the main textbooks for the class:

Amazon logo Stanley, R. P. Enumerative Combinatorics. Vol. I and II. Cambridge, UK: Cambridge University Press, 1999. ISBN: 0521553091 (hardback: vol. I); Amazon logo 0521663512 (paperback: vol. I); Amazon logo 0521560691 (hardback: vol. II).

Amazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998. ISBN: 0387984917.

Amazon logo ———. Extremal Graph Theory. New York, NY: Dover, 2004. ISBN: 0486435962.

Amazon logo Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000. ISBN: 3540663134.

The following textbooks can be used as supplemental reading:

Amazon logo Diestel, R. Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1997. ISBN: 3540261834. (Available electronically on the Graph Theory Web site by R. Diestel).

Amazon logo Matousek, J. Lectures on Discrete Geometry (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 2002. ISBN: 0387953736.

The following readings specifically deal with problem 6 from Problem Set 1:

The original paper is here:

Burago, Ju. D., and V. A. Zalgaller. "Polyhedral embedding of a net." Vestnik Leningrad Univ 15 (1960): 66-80. (In Russian)

A recent relatively simple solution:

Maehara, H. "Acute triangulations of polygons." European J Combin 23 (2002): 45-55.

Interestingly enough, if one allows right triangles there exist plentiful literature:

Baker, B. S., E. Grosse, and C. S. Rafferty. "Nonobtuse triangulation of polygons." Discrete Comput Geom 3 (1988): 147-168.

Bern, M., and D. Eppstein. "Polynomial-size nonobtuse triangulation of polygons." Internat J Comput Geom Appl 2 (1992): 241-255; Errata 449-450.

Bern, M., S. Mitchell, and J. Ruppert. "Linear-size nonobtuse triangulation of polygons." Discrete Comput Geom 14 (1995): 411-428.

The following table lists the readings assigned for each lecture.


Lec #TopicsReadings
1Course Introduction

Ramsey Theorem
Amazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 182-189. ISBN: 0387984917.
2Additive Number Theory

Theorems of Schur and Van der Waerden
Amazon logo Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 326. ISBN: 3540663134.

Amazon logo Khinchin, A. Y. Three Pearls of Number Theory. Mineola, NY: Dover Publications, Inc., 1998, section 1. ISBN: 0486400263. (Reprint of the 1952 translation.)
3Lower Bound in Schur's Theorem

Erdös-Szekeres Theorem (Two Proofs)

2-Colorability of Multigraphs

Intersection Conditions
Amazon logo Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 230, 327, and 65-66. ISBN: 3540663134.
4More on Colorings

Greedy Algorithm

Height Functions Argument for 3-Colorings of a Rectangle

Erdös Theorem
Amazon logo Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 66-67. ISBN: 3540663134.

Luby, M., D. Randall, and A. Sinclair. "Markov Chain Algorithms for Planar Lattice Structures." FOCS 1995. (Paper)
5More on Colorings (cont.)

Erdös-Lovász Theorem

Brooks Theorem
Amazon logo Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 67. ISBN: 3540663134.

Amazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 145-149. ISBN: 0387984917.
65-Color Theorem

Vizing's Theorem
Amazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 146-154. ISBN: 0387984917.

Amazon logo ———. Extremal Graph Theory. New York, NY: Dover, 2004, pp. 221-234. ISBN: 0486435962.
7Edge Coloring of Bipartite Graphs

Heawood Formula
Amazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 154-161. ISBN: 0387984917.

Amazon logo ———. Extremal Graph Theory. New York, NY: Dover, 2004, pp. 243-254. ISBN: 0486435962.
8Glauber Dynamics

The Diameter

Explicit Calculations

Bounds on Chromatic Number via the Number of Edges, and via the Independence Number
9Chromatic Polynomial

NBC Theorem
10Acyclic Orientations

Stanley's Theorem

Two Definitions of the Tutte Polynomial
Amazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 335-339. ISBN: 0387984917.
11More on Tutte Polynomial

Special Values

External and Internal Activities

Tutte's Theorem
Amazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 345-354. ISBN: 0387984917.
12Tutte Polynomial for a Cycle

Gessel's Formula for Tutte Polynomial of a Complete Graph
Gessel, I. M. "Enumerative applications of a decomposition for graphs and digraphs." Discrete Math 139, no. 1-3 (1995): 257–271. (Paper)
13Crapo's Bijection

Medial Graph and Two Type of Cuts

Introduction to Knot Theory

Reidemeister Moves
Amazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 358-363. ISBN: 0387984917.

Korn, M., and I. Pak. Combinatorial evaluations of the Tutte polynomial. Preprint (2003) available at Research (Igor Pak Home Page). (Paper)
14Kauffman Bracket and Jones PolynomialAmazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 364-371. ISBN: 0387984917.
15Linear Algebra Methods

Oddtown Theorem

Fisher's Inequality

2-Distance Sets
Amazon logo Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, section 14. ISBN: 3540663134.
16Non-uniform Ray-Chaudhuri-Wilson Theorem

Frankl-Wilson Theorem
17Borsuk Conjecture

Kahn-Kalai Theorem
Amazon logo Aigner, M., and G. Ziegler. Proof from the BOOK. 2nd ed. New York, NY: Springer-Verlag, August 1998, pp. 83-88. ISBN: 3540636986.
18Packing with Bipartite Graphs

Testing Matrix Multiplication
19Hamiltonicity, Basic Results

Tutte's Counter Example

Length of the Longest Path in a Planar Graph
Amazon logo Diestel, R. Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1997, section 10.1. ISBN 3540261834. (Available electronically on the Graph Theory Web site by R. Diestel).
20Grinberg's Formula

Lovász and Babai Conjectures for Vertex-transitive Graphs

Dirac's Theorem
Amazon logo Bollobás, B. Extremal Graph Theory. New York, NY: Dover, 2004, pp. 143-146. ISBN: 0486435962.
21Tutte's Theorem

Every Cubic Graph Contains either no HC, or At Least Three

Examples of Hamiltonian Cycles in Cayley Graphs of Sn
22Hamiltonian Cayley Graphs of General GroupsPak, I., and R. Radoicic. "Hamiltonian paths in Cayley graphs." Preprint (2002) available at Research (Igor Pak Home Page). (Paper)
23Menger Theorem

Gallai-Milgram Theorem
Amazon logo Diestel, R. Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1997, sections 2.5, and 3.3. ISBN 3540261834. (Available electronically on the Graph Theory Web site by R. Diestel).
24Dilworth Theorem

Hall's Marriage Theorem

Erdös-Szekeres Theorem
Amazon logo Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 38-39, and 97-100. ISBN: 3540663134.
25Sperner Theorem

Two Proofs of Mantel Theorem

Graham-Kleitman Theorem
Amazon logo Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 40-41, and 45-46. ISBN: 3540663134.
26Swell Colorings

Ward-Szabo Theorem

Affine Planes
Amazon logo Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 43-45, and 161-163. ISBN: 3540663134.
27Turán's Theorem

Asymptotic Analogues
Amazon logo Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 108-111. ISBN: 0387984917.
28Pattern Avoidance

The case of S3 and Catalan Numbers

Stanley-Wilf Conjecture
29Permutation Patterns

Arratia Theorem

Furedi-Hajnal Conjecture
Arratia, R. "On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern." Electron J Combin 6, no. 1 (1999). (Paper)
30Proof by Marcus and Tardos of the Stanley-Wilf ConjectureMarcus, A., and G. Tardos. "Excluded permutation matrices and the Stanley-Wilf conjecture." J Combin Theory Ser A 107, no. 1 (2004): 153–160.
31Non-intersecting Path Principle

Gessel-Viennot Determinants

Binet-Cauchy Identity
Amazon logo Stanley, R. P. Enumerative Combinatorics. Vol. I. Cambridge, UK: Cambridge University Press, 1999, section 2.7. ISBN: 0521553091 (hardback : vol. I); 0521663512. (paperback : vol. I).
32Convex Polyomino

Narayana Numbers

MacMahon Formula
Amazon logo Stanley, R. P. Enumerative Combinatorics. Vol. II. Cambridge, UK: Cambridge University Press, 1999, pp. 378. ISBN: 0521560691 (hardback: vol. II).
33Solid Partitions

MacMahon's Theorem

Hook-content Formula
Amazon logo Stanley, R. P. Enumerative Combinatorics. Vol. II. Cambridge, UK: Cambridge University Press, 1999, section 7. ISBN: 0521560691 (hardback: vol. II).
34Hook Length FormulaPak, I. "Hook Length Formula and Geometric Combinatorics." Séminaire Lotharingien de Combinatoire 46 (2001): article B46f.
35Two Polytope TheoremPak, I. "Hook Length Formula and Geometric Combinatorics." Séminaire Lotharingien de Combinatoire 46 (2001): article B46f.
36Connection to RSK

Special Cases
Pak, I. "Hook Length Formula and Geometric Combinatorics." Séminaire Lotharingien de Combinatoire 46 (2001): article B46f.
37Duality

Number of Involutions in Sn
Pak, I. "Hook Length Formula and Geometric Combinatorics." Séminaire Lotharingien de Combinatoire 46 (2001): article B46f.
38Direct bijective Proof of the Hook Length FormulaNovelli, J. C., I. Pak, and A. V. Stoyanovsky. "A direct bijective proof of the hook-length formula." Discrete Mathematics and Theoretical Computer Science 1 (1997): 53-67.
39Introduction to Tilings

Thurston's Theorem
Thurston, W. P. "Conway's tiling groups." Amer Math Monthly 97, no. 8 (1990): 757-773.

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.