New York Combinatorics Seminar Graduate Center, CUNY Fridays 11:30 am - 12:30 am Room 4419 This seminar covers a wide range of topics in combinatorics and its applications to other disciplines, especially computer science. The CUNY Graduate Center is located at 365 Fifth Avenue (at the corner of 34th Street), New York. It can be easily approached by subway, using the B,D,F,N,Q,R, or 6 trains. Seminar organizers are Jonathan Cutler, Ezra Halleck, Christopher Hanusa, Sandra Kingan, and Kerry Ojakian. Spring 2014 Talks January 31, 2014: Mikhail Mazin (Kansas State University) Title: Affine Permutations and Parking Functions Abstract: The goal of this project is to bring together and generalize two different combinatorial constructions: Haglund's zeta map and its rational slope generalizations on one side, and the Pak-Stanley labeling of regions of an extended Shi arrangement on the other. To achieve it we introduce a new construction. We consider the subset in the affine symmetric group consisting of affine permutations with no inversions of height m and define two maps from this subset to the set of the rational slope parking functions. In this talk I will introduce all three constructions involved: Haglund's zeta map, Pak-Stanley labeling, and our new construction, and explain how they are related. This is based on a joint work in progress with Eugene Gorsky and Monica Vazirani. March 7, 2014: Evgeny Gorsky (Columbia University) Title: Sommers region and parking functions Abstract: Given a pair of coprime integers (m,n), Sommers defined a certain region in R^{n-1} and proved that it is isometric to the m-dilation of the fundamental alcove in the affine hyperplane arrangement. I will review his construction and show an explicit bijection between the alcoves in the Sommers region and m/n rational parking functions. The talk is based on a joint work with Mikhail Mazin and Monica Vazirani. March 14, 2014: Po-Shen Loh (Carnegie Mellon University) Title: Maximizing the number of independent sets of a fixed size Abstract: Let $i_t(G)$ be the number of independent sets of size $t$ in a graph $G$. Engbers and Galvin asked how large $i_t(G)$ could be in graphs with minimum degree at least $\delta$. They further conjectured that when $n\geq 2\delta$ and $t\geq 3$, $i_t(G)$ is maximized by the complete bipartite graph $K_{\delta, n-\delta}$. We prove this conjecture. Joint work with Wenying Gan and Benny Sudakov. April 7, 2014 (tentative): Nikos Apostolakis Previous Speakers