The Summer Reading Seminar on Combinatorics 2007

The plan is to go over some STOC papers that contain interesting new combinatorial methods.

Organizer: Paul Horn
Time: Tuesdays, 2PM
Place: AP&M 7421

Date	Speaker	Paper
6/26/07		Organizational Meeting
7/3/07	Paul Horn	Mossel and Roch, On the submodularity of influence in social networks.
7/10/07	Ross Richardson	Vu and Tao, The condition number of a randomly perturbed matrix
7/17/07	Minming Li	Bhalgat, Hariharan, Panigrahi and Telikepalli, An O(mn) Gomory-Hu tree construction algorithm for unweighted graphs
7/24/07	No Speaker
7/31/07	Steve Butler	Fox and Sudakov, Induced Ramsey-type theorems
8/7/07	Sebi Cioaba	Krivelevich and Sudakov, Minors in expanding graphs
8/14/07	Jacques Verstraete	Product Representations of Polynomials, Abstract
8/21/07	Shoaib Jamall	Bayati, Gamarnik, Katz, Nair and Tetali, Simple deterministic approximation algorithms for counting matchings.
8/28/07	Eve Lipton	Goldberg and Jerrum, Inapproximability of the Tutte polynomial.

Here is a suggested reading list. If you are interested in presenting one of these papers, please let me (Paul) know. It is also encourged to form a group of two to prepare for presenting a paper. Fan or I will also be happy to discuss with you about the key parts of the papers.

These papers are at the front line of research and, of course, some are not so easy to read. Mainly, the goal is to dig out the good mathematics and not to be scared of the definitions etc., since you can get help from others. These papers are heavily motivated and therefore are good for guiding the research directions and looking out for new problems.

Vu and Tao, The condition number of a randomly perturbed matrix
(Ross will present this paper.)
Paper on arXiv, Slides from Tao's talk at STOC.
Mossel and Roch, On the submodularity of influence in social networks.
(Paul will do this one?)
Paper on arXiv.
Bayati, Gamarnik, Katz, Nair and Tetali, Simple deterministic approximation algorithms for counting matchings.
Paper from Tetali's website.
(Shoaib Jamall (mjamall) has expressed interest in presenting this - contact him if you're interested in working with him)
Alon, Andoni, Kaufman, Matulef, Rubinfeld and Xie, Testing k-wise and almost k-wise independence.
Paper from ACM.
Bhalgat, Hariharan, Panigrahi and Telikepalli, An O(mn) Gomory-Hu tree construction algorithm for unweighted graphs.
Paper from Telikepalli's website.
Goldberg and Jerrum, Inapproximability of the Tutte polynomial.
Paper on arXiv.
(Eve Lipton (ellipton) has expressed interest in presenting this - contact her if you are intersted in working with her)
Rodl and Schacht, Property testing in hypergraphs and the removal lemma.
Extended abstract from ACM. Full paper from Schacht's webpage.

The entirety of the STOC proceedings are available online here. If there are other papers (in or outside of STOC) which you think will be good for learning new combinatorics, further suggestions are welcome. Additionally there are new papers, one by Jacob Fox and Benny Sudakov and another by Gowers, that may be of potential interest to present; if you are interested in these contact Fan for more information.

Links:
Harmonic Analysis seminar website - Contains links with some potentially useful background to some papers.
Regularity Lemma notes - From Fall 2004 262 class; potentially useful reference for some papers.