News

The classroom in which we will meet has not been determined yet, and may depend on enrollment. The time slot was 9L last time, and may be 9L again.

For those of you who are brushing up on probability using Grinstead and Snell, a set of answers that are "mostly correct" to the exercises therein was sent to me by Charles Grinstead and can be found here.

Abstract

Permutations are everywhere, it seems, in mathematics and computer science, and even in the social sciences. In many cases, for instance, when you are interested in sorting, it is natural to think of the set of permutations on a set of n elements as a probability space. Suppose you have information about some job candidates that suggests some are better than others, but nothing directly comparing x and y. What is the probability that x is better than y? Does it necessarily go up if you get a new letter saying x is better than z?

Suppose you wish to sort a set of data, but comparisons are expensive. Which pair of elements, if compared, would give you the most information?

This course will take you to the world of partial orders, linear extensions, permutahedra, permutation patterns, sorting algorithms, exact and approximate counting problems, random walk, and limit structures. You will need to have taken at least a basic course in probability (such as MATH 20) and seen enough mathematics or theoretical computer science to be comfortable with abstract concepts and logical reasoning.

There will be a homework assignment due at the beginning of each class, usually just one problem. You may consult with your colleagues or AI on homework provided they are suitably credited, but neither will be available during exams. You will not be required to write computer programs, but writing and running a program will sometimes provide an alternative way to do an assignment.

Here is a rough weekly syllabus:

1. The probability space of permutations: fixed points, cycles

2. Partial orders and linear extensions: permutahedron, convex subsets

3. Probability and sorting: correlation, XYZ inequality

4. The 1/3-2/3 conjecture and its successors

5. MCMC and approximate counting of linear extensions

6. #P hardness and exact counting of linear extensions

7. Sorting algoithms: quicksort, merging, filing

8. Stack-sorting, permutation patterns, Marcus-Tardos Theorem

9. Permutations generated by random walk

10. Limit structures, permutons

Classes

Room: TBA
Lectures: tentatively, 9L slot: Monday, Wednesday and Friday 8:50 - 9:55.
Classroom: TBA.
X-hour: Thursdays 9:05 - 9:55, tentatively. Will be used only when so announced in class.

Staff

Instructor:

Prof. Pete Winkler -- Kemeny Hall 231
Office Hours: Mon 2-3, Thu 10:30-11:30. email: peter.winkler at dartmouth.edu

TA:

Jamie Schmidt
email: James.A.Schmidt.GR at dartmouth.edu

Textbooks

There is no official textbook for the course.

If you need to brush up on elementary probability, we suggest Grinstead and Snell's Introduction to Probability, which is available online here at Dartmouth.

Grading

Your grade will be based on homework, class participation (attendance is expected!), midterms, and a final exam.

Exams

There will be in-class exams on Monday, April 13 and Monday, May 4. Let your instructor know in advance if you antipate a conflict. The final exam will be held on the assigned day and time for the course's time slot.

Homework

Homework will be assigned at each class period, due on paper at the beginning of the next class. If you can't make it to class let the instructor know, and email a PDF of your homework to the instructor and the TA. Late homeworks will be checked off but not graded.

Assignments

Due Wednesday April 1: Let a permutation of {1,2,...,n} be chosen uniformly at random. For n large, what is the probability that it contains a cycle of length greater than n/2?

Honor Code

Students are permitted to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you employ generative AI, e.g. ChatGPT, say so, and say how you verified that what it told you is correct.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Notification to Student re Recording

(1) Consent to recording of course meetings and office hours that are open to multiple students. By enrolling in this course, a) I affirm my understanding that the instructor may record meetings of this course and any associated meetings open to multiple students and the instructor, including but not limited to scheduled and ad hoc office hours and other consultations, within any digital platform, including those used to offer remote instruction for this course. b) I further affirm that the instructor owns the copyright to their instructional materials, of which these recordings constitute a part, and my distribution of any of these recordings in whole or in part to any person or entity other than other members of the class without prior written consent of the instructor may be subject to discipline by Dartmouth up to and including separation from Dartmouth. (2) Requirement of consent to one-on-one recordings: By enrolling in this course, I hereby affirm that I will not make a recording in any medium of any one-on-one meeting with the instructor or another member of the class or group of members of the class without obtaining the prior written consent of all those participating, and I understand that if I violate this prohibition, I will be subject to discipline by Dartmouth up to and including separation from Dartmouth, as well as any other civil or criminal penalties under applicable law. I understand that an exception to this consent applies to accommodations approved by SAS for a student's disability, and that one or more students in a class may record class lectures, discussions, lab sessions, and review sessions and take pictures of essential information, and/or be provided class notes for personal study use only.

If you have questions, please contact the Office of the Dean of the Faculty of Arts and Sciences.

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations that might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Center is located at 318 Wilson Hall, ext. 6-9900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.