Math 108 - Geometric combinatorics

Winter 2023

Instructor: Nadia Lafrenière (Kemeny Hall 318, nadia.lafreniere@dartmouth.edu)
MWF 8:50 - 9:55 AM, x-hour Th 9:05-9:55 (see calendar for when we will use it). Kemeny 004
Website for the course: Canvas; https://canvas.dartmouth.edu/courses/56422
Office hours: Monday 10-11, Tuesday 1:30-2:30, and by appointment

(Copyright for the pictures: Justin W. Smith on Wikipedia, M.C. Escher).

Course Objectives

Geometric combinatorics concerns the use of techniques from geometry and topology to solve problems in combinatorics, as well as the establishment of a few theorems in combinatorics that cleverly solve problems in geometry.
The goal of this class is to introduce some notions of combinatorics and to use the techniques from it along with geometry. Similarly, to those experienced with combinatorics, the class will introduce results from geometry, and frame them in a way that we can use them to solve combinatorical problems. There will be six main areas of discussions:

Partial ordered sets (posets), lattices, Möbius function and Möbius inversion.
Hyperplane arrangements: Intersections, counting regions, graphical arrangements and chromatic polynomials.
Polytopes: f -vectors and polytopability, lattice polytopes, area and volume through Ehrhart theory.
Current developments: building cluster algebras from triangulations of polygons.
Matroids: matroids from hyperplanes arragements, oriented matroids, matroid polytopes, simplicial complexes, matroid invariants.
Tilings: Tiling with one or multiple tiles, periodic and aperiodic tilings, regular tilings and polyomino tilings. Conditions for tilings to exist.
Topological methods: Theorems from topology have been used to solve purely combinatorial problems, such as the chromatic number of Kneser graphs or discrete fair division problems.

It would be unrealistic to attempt to cover all of geometric combinatorics over the course of one quarter. Therefore, students will be invited to explore a topic of their choice throughout the term, and will present their investigation to their peers at the end of the terms.

Content’s Schedule (tentative)

This schedule is tentative, and the most up-to-date version will be posted here as it changes. The list of references for each part might change as well, but you will find most of the content taught in the references that are listed here.

Date	Content	References

January 4	What is geometric combinatorics?	[MR07]
January 6	Class is cancelled
January 9	Posets: General definitions	[EC1, §3.1, 3.3]
January 11	Lattices	[AOC, §5.3]
January 13	Möbius function & inversion	[EC1, §3.5, 3.6, 3.7, 3.8], [AOC, §5.4, 5.5]
January 16	Class is postponed, Martin Luther King day
January 18	Hyperplane arrangements: General definitions	[Sta07, Lecture 1]
January 19	Intersection poset, counting regions (x-hour)	[Sta07, Lecture 2]
January 20	Graphical arrangements, characteristic polynomial, Zaslavsky's theorem for counting regions	[Sta07, Lecture 2]
January 23	Polytopes: Notions, f-vector	[Zie07]
January 25	Lattice polytopes, Pick's theorem and idea for Ehrhart theory	[CCD, §2]
January 27	Ehrhart theorem	[CCD, §2,3]
January 30	Triangulations of a convex polygon and flips	[Wil14]
February 1	New direction: Cluster algebras from triangulations of polygons, total positivitiy and Laurent polynomials	[FR07, §4], [ST09]
February 3	Intro to matroids. Geometric lattices, graphical and oriented matroids (Lectures notes are the beautiful notes of Federico Ardila, page 1-6).	[AM07]
February 6	Matroid invariants: Characteristic polynomial, independence and broken circuit complexes, Tutte polynomial (pages 1-5 of the notes)	[AM23]
February 8	Combinatorial sequences from matroids (pages 6-10 of the notes)	[AM23], [Eur23]
February 10	Tilings: Escher tilings, the problem, tiling with multiple tiles; periodic and aperiodic tilings; Counting tilings	[AS10]
February 13	Convex tilings: Regular polygons and the fifteen pentagons
February 15	Creating tilings (Beauquier – Nivat's theorem, Conway's criterion)	[BN91, Fat20]
February 17	Topological methods: Borsuk-Ulam Theorem and Tucker's lemma	[Matousek, §2], [Lon13]
February 20	Brouwer fixed point theorem and Sperner's lemma	[Matousek, §2], [Lon13, §1]
February 22	Winning at Hex, the ham sandwich and the stolen necklace	[Gal79], [GW85], [Matousek, §3]
February 24	Kneser conjecture	[Matousek, §3.3], [Lon13, §2.1]
February 27	Class is cancelled, Feedback due for buddy's project
March 1	Student presentations
March 3	Student presentations
March 6	Student presentations
March 8	Written part of project due

Combinatorics seminar

Dartmouth hosts a combinatorics seminar on most Tuesdays, at 11 AM. You are encouraged to attend it, and talks are listed on this webpage: https://math.dartmouth.edu/~comb/.

Evaluation

The homework assignments will be available on the last day that we cover a topic, and due a week later. In each problem sets, there will be both graded and ungraded problems, and these will be clearly identified.

Evaluation	Date	Value
Homework	One per topic	30 %
Student presentations	March 1–6	20 %
Written part of final project	Due March 8	30 %
Feedback given on someone else's project	Due February 27	10 %
Interview on final project	February 13–17	10 %

Finding the right answer is not equivalent to solve a problem, and therefore your solution will be evaluated as a whole. Please, keep in mind while writing the assignments that I will not be with you when I will read it, so it must be complete.

You'll find the list of homework sets here.

Topic and problem set	Due date	Solutions
Posets and lattices	January 20	Solutions to HW 1
Hyperplane arrangements (TeX file)	January 27	Solutions to HW2
Polytopes (Tex file, picture triangulation1.png, picture triangulation2.png)	February 8	Solutions to HW3
Matroids (TeX file)	February 15
Tilings	February 22	Gallery
Topological methods (TeX file)	March 6	Solutions to HW6

Final project

Since geometric combinatorics is a wide topic, we won’t be able to cover all of it over the course of the term. To give you the opportunity to explore further, you will dig into one topic of your choice as your main assignment of the term. You will have to do both a paper and a presentation on that topic.
To maximize your learning, there will be a buddy system. Each of you will be paired with someone who will give you feedback on both the written and oral part of your presentation. Giving feedback will also be part of your assessment. You should talk regularly to your buddy about what you learn on your topic. Similarly, I will meet with each of you on the week of February 13–17 to talk about your progress. Choose a meeting time slot here. At that point, what I am hoping to see is a preliminary list of references, and I would like to hear about what you have learned so far on the topic.

The student presentations can be about any research paper in geometric combinatorics, or chosen among a list of topics. If you prefer, your project could consist in implementing an algorithm from geometric combinatorics into a programming language, writing a tutorial on how to use mathematical software to solve a combinatorial problem, or contributing to an open-source software. Students having further ideas should talk to me about the project they have.

The presentations and projects can be done in teams of two students, but the project should be bigger (longer talk and paper, or broader software project).

Extension policy

Every student is granted an automatic extension for one problem set; you however have to tell me before the submission deadline. This policy does not apply to the final project, nor to students talks, given that this would involve scheduling issues.
I might grant extensions after the automatic one based on special circumstances, but students will need to ask for it.

Textbook

There is no required textbook for the class. Instead, all notes will be written on the blackboard or given to students in printed format, and the tentative
schedule tells you what reference I’m using on what day. A list of references that I am using to design the course material follows at the end of this syllabus. The main reference for the course is at the Baker library’s reserve ([MRS07], including the chapters cited below [MR07, Sta07, Zie07]). Many references are freely available online.

Students are encouraged to use software to solve the problems. For combinatorics, SageMath [Sage] is well-developed. It is furthermore free to use, to modify and to share. You can either download it for your personal computer running Windows, MacOS or Linux, or you can use it through the department’s server at https://euclid.dartmouth.edu.

Honor Principle

Assignments serve both the purpose of fixing your ideas on a given subject and, for the evaluator, to assess the comprehension you have of the class and how the class material has been understood. None of these goals can be achieved if you hand out a solution that is taken from someone else or from a publicly available source.
Nevertheless, students are allowed to work together on problems to explore their solutions. The homework you submit must reflect your own understanding, and you thus need to write your own copy of the solution, in your own words.
More information on the Academic Honor Principle can be found on Dartmouth’s website: https://students.dartmouth.edu/judicial-affairs/policy/
academic-honor-principle

Attendance and Health policy

You are expected to attend class in person unless you have made alternative arrangements due to illness, medical reasons, or the need to isolate due to COVID-19 or other diseases. For the health and safety of our class community, please: do not attend class when you are sick, nor when you have been instructed by Student Health Services to stay home. My lectures notes are available on the course website, and I will provide the support you need to catch up on class material and submit your work. If needed, one-on-one office hours over Zoom will be offered.

Dartmouth Policies

Student Accessibility and Accommodations

Students requesting disability-related accommodations and services for this course are encouraged to schedule a meeting with me as early in the term as possible. This conversation will help to establish how your accommodations will be implemented in my course and what role Student Accessibility Services (SAS) or its Testing Center may play in assisting. In order for accommodations to be authorized, students are required to register with SAS (Getting Started with SAS webpage; student.accessibility.services@dartmouth.edu; 603-646-9900) and to request an accommodation email be sent to me in advance of the need for an accommodation. If students have questions about whether they are eligible for accommodations, they should contact
the SAS office. All inquiries and discussions will remain confidential.

Mental Health

The academic environment at Dartmouth is challenging, our terms are intensive, and classes are not the only demanding part of your life. There are a number of resources available to you on campus to support your wellness, including your undergraduate dean (http://www.dartmouth.edu/~upperde/), Counseling and Human Development (http://www.dartmouth.edu/~chd/), and the Student Wellness Center (http://www.dartmouth.edu/~healthed/). Remember, mental and physical health should be your number one priority!

Religious Observances

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me as soon as possible, preferably before the end of the second week of the term to discuss appropriate accommodations.

Financial Needs

All material for this class is aimed to be freely available, either at the library or online. If you encounter financial challenges related to this class (because of the workload for example), please let me know.

References

[AM23 ]F. Ardila-Mantilla. The geometry of geometries: matroid theory, old and new. Proceedings of the International Congress of Mathematicians 2022, 2023. Freely available at http://fardila.com/Articles/ArdilaICM.pdf.
[AOC] B. E. Sagan. Combinatorics: The Art of Counting, volume 210 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2020. Freely available at https://users.math.msu.edu/users/bsagan/Books/Aoc/GSM210.pdf.
[AS10] F. Ardila and R. P. Stanley. Tilings. The Mathematical Intelligencer, 32(4):32–43, 2010. doi:10.1007/s00283-010-9160-9. Freely available at
http://fardila.com/Articles/tilings.pdf.
[BLVS+ 99] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler. Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, second edition, 1999. doi:10.1017/CBO9780511586507. Print and electronic versions available at the Dartmouth library.
[BN91] D. Beauquier and M. Nivat. On translating one polyomino to tile the plane. Discrete Computational Geometry, 6:575–592, 1991. Freely available at https://link.springer.com/content/pdf/10.1007/BF02574705.pdf.
[CCD] M. Beck and S. Robins. Computing the continuous discretely. Undergraduate Texts in Mathematics. Springer, New York, second edition,
2015. doi:10.1007/978-1-4939-2969-6. Integer-point enumeration in polyhedra, With illustrations by David Austin. Freely available at https:
//matthbeck.github.io/papers/ccdnew.pdf.
[EC1] R. P. Stanley. Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press,
Cambridge, second edition, 2012. Freely available online at http://www-math.mit.edu/~rstan/ec/ec1.pdf.
[Eur23] C. Eur. An essence of independence: Recent works of June Huh on combinatorics and Hodge theory. To appear in the Proceedings of the Joint Math Meetings 2023. Available on the ArXiv: https://arxiv.org/abs/2211.05724.
[Fat20] R. Fathauer. Tessellations: Mathematics, Art, and Recreation (1st ed.). A K Peters/CRC Press, 2020.
[Gal79] D. Gale. The game of Hex and the Brouwer fixed-point theorem. The American Mathematical Monthly, 86(10):818–827, 1979. Freely avail-
able at https://www.maa.org/programs/maa-awards/writing-awards/the-game-of-hex-and-the-brouwer-fixed-point-theorem.
[GW85] C. H. Goldberg and D. B. West. Bisection of circle colorings. Society for Industrial and Applied Mathematics. Journal on Algebraic and Discrete Methods, 6(1):93–106, 1985. Freely available at https://faculty.math.illinois.edu/~west/pubs/bisect.pdf
[Lon13] M. de Longueville. A course in topological combinatorics. Universitext. Springer, New York, 2013.
[Matousek] J. Matoušek. Using the Borsuk-Ulam theorem. Universitext. Springer-Verlag, Berlin, 2003. Relevant chapters are freely available at https://kam.mff.cuni.cz/~matousek/akt.html
[MR07] E. Miller and V. Reiner. What is geometric combinatorics?—An overview of the graduate summer school. In Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., pages 1–17. Amer. Math. Soc., Providence, RI, 2007. doi:10.1090/pcms/013/01. Available on the ArXiv: http://arxiv.org/abs/math/0601202
[MRS07] E. Miller, V. Reiner, and B. Sturmfels, editors. Geometric combinatorics, volume 13 of IAS/Park City Mathematics Series. American Mathematical Society, Providence, RI; Institute for Advanced Study (IAS), Princeton, NJ, 2007. doi:10.1090/pcms/013. Lectures from the Graduate Summer School held in Park City, UT, 2004. Chapters are available for free (links where they are cited).
[Sage] The Sage Developers. SageMath, the Sage Mathematics Software System. http://www.sagemath.org.
[Sta07] R. P. Stanley. An introduction to hyperplane arrangements. In Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., pages 389–496. Amer. Math. Soc., Providence, RI, 2007. Freely available online at http://www-math.mit.edu/~rstan/arrangements/arr.html
[Wil14] L. K. Williams. Cluster algebras: an introduction. American Mathematical Society. Bulletin. New Series, 51(1):1–26, 2014. doi:10.1090/S0273-0979-2013-01417-4. Freely available at https://people.math.harvard.edu/~williams/papers/CA.pdf
[Wol17] N. Wolchover. Pentagon tiling proof solves century-old math problem. 2017. Freely available at https://www.quantamagazine.org/pentagon-tiling-proof-solves-century-old-math-problem-20170711/
[Zie07] G. M. Ziegler. Convex polytopes: extremal constructions and f-vector shapes. In Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., pages 617–691. Amer. Math. Soc., Providence, RI, 2007. doi:10.1090/pcms/013/10. Freely available on the ArXiv: https://arxiv.org/abs/math/0411400