Random Graphs -- Spring 2012

Room wwh317, Tuesday 5-6:50

Final Exam

There will be take home final exam for all students taking the course for credit. It will be handed out during our last class which is Tuesday, May 1. It will be a limited time exam, though students may determine when they will take it. Of course, any discussion of the exam problems -- unless the students have already submitted the exams -- is absolutely prohibited.

The exam will be THREE HOURS LONG. It will have eight questions of varying lengths. It is not a particularly long exam, and you may well finish with time to spare.

Previous information about a scheduled exam should be ignored.

Special rules: The exam must be returned by Monday, May 7 noon. It may be taken at any time period before that but it must be a continuous time period for the three hours. (e.g., one can do it 2:30-5:30 a.m. Thursday morning.)

The text, The Probabilistic Method, may be used. Notes may be used. Everything that is on the website for the course, including assignments and solutions and scribenotes may be used. Your own notes, if they are on the computer, may be used. You may NOT look for other papers, results, Wikis or whatever. As this is a timed exam, it is suggested that you familiarize yourself with the material (at least, where it is!) in the various notes available before you take the exam.

Please supply your own (large!) pad of paper for writing the solutions. Submit separate problems on separate sheets.

As a general rule I avoid tricky problems -- the questions test mostly a basic understanding of the course. Problems marked with a (*) are more difficult, those with a (-) have short answers, if you see them! More information on the exam will be placed HERE as the date approaches.

Basic Information

Text: The Probabilistic Method, Noga Alon and Joel Spencer, John Wiley & Sons, 3rd Edition. This course could be called The Probabilistic Method or The Erdos Method or, my favorite, Erdos Magic. We will study a variety of random structures with particular emphasis on Random Graphs. We will analyze various algorithms on those structures. We will use random structures to prove the existence of combinatorial objects (this is, more specifically, the Erdos Magic) such as colorings, tournaments, and simultaneous roundoffs. We give methods (2nd moment method, Janson's Inequality, ...) that allow us to estimate and/or bound probabilities, particularly very small probabilities. (A basic knowledge of probability -- expectation, variance, binomial distribution and the like, would be helpful but is not required.) (Also, a prior acquaintance with Discrete Mathematics - graphs, trees, colorings, ... - would be helpful but is not required.) A common theme throughout the course is asymptotic estimation. There will be plenty of big-Ohs, little-ohs, Thetas and Omegas.

Assignments

Generally there will be assignments every week. They will be put online on Tuesday and due at the start of class the following Tuesday. Hard copy is always acceptible. Electronic copy can be sent to (Make sure your name is clearly indicated!) s2303307@cs.nyu.edu

The language of preference for the course is LaTeX but all forms of TeX are accepted. Please clarify which form of TeX is being used. Please send both the .tex and the .pdf files.

A special note: Working together on the assignments is encouraged. However, everyone must hand in their separate assignment and it should be written in cribe

Scribe

Scribe postings will be here. Click here scribelist for the list of scribes with dates. To volunteer: send your name, email and date requested to Prof. Spencer at spencer@cims.nyu.edu

February -1 (thanks Krzysztof!) pdf

February 7 (thanks George!) jpg jpg jpg jpg jpg jpg jpg jpg jpg jpg

February 14 (thanks Nate!) pdf

February 21 (thanks Brian!) jpg jpg jpg jpg jpg jpg jpg

March 6 (thanks Krzysztof!) pdf

March 26 (thanks Jeong!) pdf

April 3 (thanks Feng!) pdf

April 17 (thanks Nimrod!) pdf tex ps April 24 (thanks Krzysztof!) pdf

May 1 (thanks Arjun!) pdf

Assignments

Assignment 1 due January 31, in class postscript LaTeX pdf

Assignment 2 due February 7, in class postscript LaTeX pdf

Assignment 3 due February 14, in class (NOTE: Problem 2 NOT to be handed in) postscript LaTeX pdf

Assignment 4 due February 21, in class postscript LaTeX pdf

Assignment 5 due February 28, in class postscript LaTeX pdf

Assignment 6 due March 6, in class postscript LaTeX pdf

Assignment 7 due March 20, in class postscript LaTeX pdf

Assignment 8 due March 27, in class postscript LaTeX pdf

Assignment 9 due April 3, in class postscript LaTeX pdf

Assignment 10 due April 10, in class postscript LaTeX pdf

Assignment 11 due April 17, in class postscript LaTeX pdf

Assignment 12 due April 24, in class postscript LaTeX pdf

Assignment 13 due May 1, in class postscript LaTeX pdf

Solutions