MATH 100 / COSC 149.9 and COSC 49.02

(Topics in Probability)

The Shape of Large Random Systems

Instructor: Prof. Peter Winkler (peter.winkler at dartmouth.edu)

Abstract | Classes | Staff | Textbooks | Grading | News and current assignment | Past assignments | Exams | Honor Code


News

CLASSROOM Not known yet, will be announced here.

Abstract

Large random structures occur frequently in mathematics, computer science, and statistical physics --- these days, also in medicine, astronomy, and the social sciences. In this course we will be especially interested in systems that consist of a large number of simple, small components, that interact via a few rules (possibly none at all). Theoretically, a huge variety of things could happen; for example, all of the molecules of air in the classroom might suddenly find themselves in the left-hand half of the room.

In practice, such unlikely behaviors are never seen. Indeed, one configuration of a large random system tends to look a lot like any other. For example, if you flip a fair coin 1,000 times, the good old Law of Large Numbers tells you that, with high probability, you will record about 500 heads. Here's a more shocking example that we will prove in class: two countably infinite random graphs will be isomorphic with probability one!

In class we'll examine some powerful tools for dealing with random structures, and determining what they look like. The tools include expectations and moments, the Central Limit Theorem, and Large Deviation Principles; the systems include sequences, graphs, permutations, and in one case a random surface.

Prerequisites: The mathematical sophistication of a beginning math graduate student or advanced undergraduate math math major, or the same for theory and algorithms in computer science. A basic acquaintance with probability, as encountered in MATH 20 or COSC 70, will be assumed; check with the instructor if you're not sure about whether your background is sufficient for this course. There will be daily (small) assignments, and in-class exams including a final. You will see some proofs in class and occasionally be asked to prove something not too complex. You will not be required to write computer programs, but doing so will sometimes provide an alternative way to do an assignment.

Here is a rough weekly syllabus:

1. Random sequences, random subsets, Law of Large Numbers, Central Limit Theorem

2. Random systems, random graphs, Erdos and Renyi

3. Expectations; rirst moment method; second moment; new progress

4. The 0-1 Law, Fagin's proof and the Rado graph

5. Limit structures: subgraph frequencies, graphons, Razborov's scalloped triangle

6. Chatterjee & Varadhan's Large Deviations Principle; Radin and Sadun's landscape

7. Permutations and permutation patterns

8. Permutons and their Large Deviations Principle

9. Ulam's problem and the shape of random Young diagrams

Classes

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

Staff

Instructor:
Prof. Pete Winkler -- Kemeny Hall 231
Office Hours: TBA. email: peter.winkler at dartmouth.edu
TA:
Jamie Schmidt
email: James.A.Schmidt.GR at dartmouth.edu

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 15 and Monday, May 6. Let your instructor know in advance if you antipate a conflict. The final exam will be held on the assigned day and time for "9L" slot classes.

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 (e.g., on account of COVID quarantine), let the instructor know, and you will be able to email a PDF of your homework to the instructor and the TA. Late homeworks will be checked off but not graded.

Assignments

Due Wednesday March 27: You flip 100 times a coin that lands heads with probability 50\%. How many of the 2^100 possible results have precisely 51 heads? How many have 51? Which outcome is more likely?

Honor Code

Students are encouraged 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.