18.315
Combinatorial Theory: Hyperplane Arrangements
Spring 2005 · Combinatorial Theory: Introduction to Graph Theory, Extremal and Enumerative Combinatorics
Topics
- Course Introduction
- Additive Number Theory
- Lower Bound in Schur’s Theorem
- More on Colorings
- More on Colorings (cont.)
- 5-Color Theorem
- Edge Coloring of Bipartite Graphs
- Glauber Dynamics
- Chromatic Polynomial
- Acyclic Orientations
- More on Tutte Polynomial
- Tutte Polynomial for a Cycle
- Crapo’s Bijection
- Kauffman Bracket and Jones Polynomial
- Linear Algebra Methods
- Non-uniform Ray-Chaudhuri-Wilson Theorem
- Borsuk Conjecture
- Packing with Bipartite Graphs
- Hamiltonicity, Basic Results
- Grinberg’s Formula
- Tutte’s Theorem
- Hamiltonian Cayley Graphs of General Groups
- Menger Theorem
- Dilworth Theorem
- Sperner Theorem
- Swell Colorings
- Turán’s Theorem
- Pattern Avoidance
- Permutation Patterns
- Proof by Marcus and Tardos of the Stanley-Wilf Conjecture
- Non-intersecting Path Principle
- Convex Polyomino
- Solid Partitions
- Hook Length Formula
- Two Polytope Theorem
- Connection to RSK
- Duality
- Direct Bijective Proof of the Hook Length Formula
- Introduction to Tilings
Readings
- Stanley, R. P. Enumerative Combinatorics. Vol. I and II. Cambridge, UK: Cambridge University Press, 1999. ISBN: 0521553091 (hardback: vol. I); 0521663512 (paperback: vol. I); 0521560691 (hardback: vol. II).
- Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998. ISBN: 0387984917.
- ———. Extremal Graph Theory. New York, NY: Dover, 2004. ISBN: 0486435962.
- Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000. ISBN: 3540663134.
- Matousek, J. Lectures on Discrete Geometry (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 2002. ISBN: 0387953736.
- Burago, Ju. D., and V. A. Zalgaller. “Polyhedral embedding of a net.” Vestnik Leningrad Univ 15 (1960): 66-80. (In Russian)
- Maehara, H. “Acute triangulations of polygons.” European J Combin 23 (2002): 45-55.
- 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.
- Ramsey Theorem Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 182-189. ISBN: 0387984917.
- Theorems of Schur and Van der Waerden Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 326. ISBN: 3540663134.
- Khinchin, A. Y. Three Pearls of Number Theory . Mineola, NY: Dover Publications, Inc., 1998, section 1. ISBN: 0486400263. (Reprint of the 1952 translation.)
- Intersection Conditions Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 230, 327, and 65-66. ISBN: 3540663134.
- Erdös Theorem 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)
- Brooks Theorem Jukna, S. Extremal Combinatorics. New York, NY: Springer-Verlag, Berlin, 2000, pp. 67. ISBN: 3540663134.
- Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 145-149. ISBN: 0387984917.
- Vizing’s Theorem Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 146-154. ISBN: 0387984917.
- ———. Extremal Graph Theory. New York, NY: Dover, 2004, pp. 221-234. ISBN: 0486435962.
- Heawood Formula Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 154-161. ISBN: 0387984917.
- ———. Extremal Graph Theory. New York, NY: Dover, 2004, pp. 243-254. ISBN: 0486435962.
- Two Definitions of the Tutte Polynomial Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 335-339. ISBN: 0387984917.
- Tutte’s Theorem Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 345-354. ISBN: 0387984917.
- 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)
- Reidemeister Moves Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 358-363. ISBN: 0387984917.
- Lec #: 14 · Topics: Kauffman Bracket and Jones Polynomial · Readings: Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 364-371. ISBN: 0387984917.
- 2-Distance Sets Jukna, S. Extremal Combinatorics . New York, NY: Springer-Verlag, Berlin, 2000, section 14. ISBN: 3540663134.
- Kahn-Kalai Theorem Aigner, M., and G. Ziegler. Proof from the BOOK. 2nd ed. New York, NY: Springer-Verlag, August 1998, pp. 83-88. ISBN: 3540636986.
- Dirac’s Theorem Bollobás, B. Extremal Graph Theory. New York, NY: Dover, 2004, pp. 143-146. ISBN: 0486435962.
- Erdös-Szekeres Theorem Jukna, S. Extremal Combinatorics . New York, NY: Springer-Verlag, Berlin, 2000, pp. 38-39, and 97-100. ISBN: 3540663134.
- Graham-Kleitman Theorem Jukna, S. Extremal Combinatorics . New York, NY: Springer-Verlag, Berlin, 2000, pp. 40-41, and 45-46. ISBN: 3540663134.
- Affine Planes Jukna, S. Extremal Combinatorics . New York, NY: Springer-Verlag, Berlin, 2000, pp. 43-45, and 161-163. ISBN: 3540663134.
- Asymptotic Analogues Bollobás, B. Modern Graph Theory (Graduate Texts in Mathematics). New York, NY: Springer-Verlag, 1998, pp. 108-111. ISBN: 0387984917.
- 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)
- Lec #: 30 · Topics: Proof by Marcus and Tardos of the Stanley-Wilf Conjecture · Readings: Marcus, A., and G. Tardos. “Excluded permutation matrices and the Stanley-Wilf conjecture.” J Combin Theory Ser A 107, no. 1 (2004): 153–160.
- Binet-Cauchy Identity 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).
- MacMahon Formula Stanley, R. P. Enumerative Combinatorics . Vol. II. Cambridge, UK: Cambridge University Press, 1999, pp. 378. ISBN: 0521560691 (hardback: vol. II).
- Hook-content Formula Stanley, R. P. Enumerative Combinatorics . Vol. II. Cambridge, UK: Cambridge University Press, 1999, section 7. ISBN: 0521560691 (hardback: vol. II).
- Lec #: 34 · Topics: Hook Length Formula · Readings: Pak, I. “Hook Length Formula and Geometric Combinatorics.” Séminaire Lotharingien de Combinatoire 46 (2001): article B46f.
- Lec #: 35 · Topics: Two Polytope Theorem · Readings: Pak, I. “Hook Length Formula and Geometric Combinatorics.” Séminaire Lotharingien de Combinatoire 46 (2001): article B46f.
- Special Cases Pak, I. “Hook Length Formula and Geometric Combinatorics.” Séminaire Lotharingien de Combinatoire 46 (2001): article B46f.
- Number of Involutions in S n Pak, I. “Hook Length Formula and Geometric Combinatorics.” Séminaire Lotharingien de Combinatoire 46 (2001): article B46f.
- Lec #: 38 · Topics: Direct bijective Proof of the Hook Length Formula · Readings: Novelli, 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.
- Thurston’s Theorem Thurston, W. P. “Conway’s tiling groups.” Amer Math Monthly 97, no. 8 (1990): 757-773.
Fall 2004
Topics
- Basic Definitions, the Intersection Poset and the Characteristic Polynomial
- Properties of the Intersection Poset and Graphical Arrangements
- Matroids and Geometric Lattices
- Broken Circuits, Modular Elements, and Supersolvability
- Finite Fields
- Random Walks on Regions
- Separating Hyperplanes
- Tutte Polynomial
Readings
- Athanasiadis, C. A. “Algebraic Combinatorics of Graph Spectra, Subspace Arrangements and Tutte Polynomials.” Ph.D. Thesis, MIT, 1996.
- ———. “Characteristic Polynomials of Subspace Arrangements and Finite Fields.” Advances in Math. 122 (1996): 193-233.
- Barcelo, H., and E. Ihrig. “Lattices of Parabolic Subgroups in Connection with Hyperplane Arrangements.” J. Algebraic Combinatorics 9 (1999): 5-24.
- Björner, A., and F. Brenti. Combinatorics of Coxeter Groups. (To appear)
- Björner, A., M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler. Oriented Matroids. 2nd ed_. Encyclopedia of Mathematics and Its Applications_ 46_._ Cambridge: Cambridge University Press, 1999.
- Blass, A., and B. Sagan. “Characteristic and Ehrhart Polynomials.” J. Algebraic Combinatorics 7 (1998): 115-126.
- Bourbaki, N. “Groupes et Algèbres de Lie.” Éléments de Mathématique , Fasc. 34. Paris: Hermann, 1968.
- Chandon, J. L., J. Lemaire, and J. Pouget. “Dénombrement des Quasi-ordres sur un Ensemble fini.” Math. Inform. Sci. Humaines 62 (1978): 61-80, 83.
- Crapo, H., and G.-C. Rota. On the Foundations of Combinatorial Theory: Combinatorial Geometries. Preliminary edition. Cambridge, MA: MIT Press, 1970.
- Fishburn, P. C. Interval Orders and Interval Graphs . New York: Wiley-Interscience, 1985.
- Greene, C. “On the Möbius Algebra of a Partially Ordered Set.” Advances in Math. 10 (1973): 177-187.
- Humphreys, J. E. Reflection Groups and Coxeter Groups. Cambridge: Cambridge University Press, 1990.
- Orlik, P., and H. Terao. Arrangements of Hyperplanes . Berlin: Springer-Verlag, 1992.
- Postnikov, A., and R. Stanley. “Deformations of Coxeter Hyperplane Arrangements.” J. Combinatorial Theory (A) 91 (2000): 544-597.
- Shi, J.-Y. “The Kazhdan-Lusztig Cells in Certain Affine Weyl Groups.” Lecture Notes in Mathematics . Vol. 1179. Berlin: Springer-Verlag, 1986.
- Stanley, R. “Modular Elements of Geometric Lattices.” Algebra Universalis 1 (1971): 214-217.
- ———. “Supersolvable Lattices.” Algebra Universalis 2 (1972): 197-217.
- ———. Enumerative Combinatorics . Vol. 1. Pacific Grove, CA: Wadsworth and Brooks/Cole, 1986. Second printing, Cambridge: Cambridge University Press, 1996.
- ———. Enumerative Combinatorics . Vol. 2. Cambridge: Cambridge University Press, 1999.
- ———. “Hyperplane Arrangements, Interval Orders, and Trees.” Proc. Nat. Acad. Sci . 93 (1996): 2620-2625.
- Terao, H. “Free Arrangements of Hyperplanes and Unitary Reflection Groups.” Proc. Japan Acac., Ser. A 56 (1980): 389-392.
- ———. “Generalized Exponents of a Free Arrangement of Hyperplanes and Shepherd[sic]-Todd-Brieskorn Formula.” Invent. Math. 63 (1981): 159-179.
- Trotter, W. T. Combinatorics and Partially Ordered Sets . Baltimore/London: The Johns Hopkins Univ. Press, 1992.
- Wine, R. L., and J. E. Freund. “On the Enumeration of Decision Patterns Involving n Means.” Ann. Math. Stat. 28: 256-259.
- The main text on hyperplane arrangements is: Orlik, P., and H. Terao. Arrangements of Hyperplanes. New York: Springer-Verlag, 1992.
Sources
- Course catalogue ↗Historical OpenCourseWare
- MIT OpenCourseWare ↗Spring 2005
- MIT OCW calendar ↗
- MIT OCW readings ↗
- MIT OCW syllabus ↗
- MIT OCW calendar ↗
- MIT OCW readings ↗
- MIT OCW syllabus ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.