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 4, 2014: Nikolaos Apostolakis (Bronx Community College, CUNY)

Title: Proper graph embeddings, duality, and structural bijections
Abstract: A proper embedding of a graph G in a surface with boundary S, is an embedding of G in S so that all the vertices lie on the boundary of S, and the complement of G in S is a disjoint union of disks or "pinched" anulli. There is a natural notion of duality for such embeddings and we develop a combinatorial interpretation of it in terms of partitions of the oriented edges of G into walks. As an application we provide a framework for establishing "structural" bijections between certain sets of factorizations of permutations into transpositions and graphs with labeled edges and vertices. In particular we'll discuss such a bijection between factorizations of an n-cycle into a product of n+1 transpositions and labeled unicorns i.e. trees with three marked vertices. Joint work with Kerry Ojakian.

April 11, 2014: Jozef Skokan (London School of Economics)

Title: The Ramsey number of the clique and the hypercube
Abstract: The Ramsey number $r(K_s,Q_n)$ is the smallest integer $N$ such that every red-blue colouring of the edges of the complete graph on $N$ vertices contains either a red $n$-dimensional hypercube $Q_n$, or a blue clique on $s$ vertices. In 1983, Burr and Erd\H{o}s conjectured that $r(K_s,Q_n) = (s-1)(2^n - 1)+1$ for every positive integer $s$ and sufficiently large $n$. In this talk we shall sketch the proof of this conjecture and discuss some related problems. Joint work with Gonzalo Fiz Pontiveros, Simon Griffiths, Rob Morris and David Saxton (IMPA, Rio de Janeiro)