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 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)

Janos Pach (EPFL and CUNY) is speaking on Thursday April 24, 2014 in the Computer Science Colloquium
Title: The unreasonable effectiveness of semi-algebraicity in geometry

Friday April 25, 2014 is New York Area Theory Day

May 2, 2014 Peter Maceli (Columbia University)

Title: Coloring Graphs with Forbidden Induced Subgraphs

June 13, 2014: Tom Denton (York University, Canada, and Google)

Title: Compressed Combinatorial Data
Abstract: Storage and retrieval of combinatorial statistics is useful in a research setting, but statistics on permutations generally require $O(n!)$ storage and comparison. Meanwhile, the Fourier transform on the symmetric group gives an alternative representation of functions on S_n, stored as matrices indexed by the partitions of n. We demonstrate that many 'interesting' permutation statistics are band-limited, in the sense that their Fourier transform matrices are mostly zero matrices, and provide some simple techniques for demonstrating that a given statistic is band-limited. These techniques allow polynomial-time computation of the Fourier transform of band-limited statistics, as well as reducing storage requirements to polynomial space. Similar methods can be used for a wide variety of combinatorial datum, including certain graph invariants, as we will demonstrate.

June 27, 2014: Henning Ulfarsson (Reykjavik University, Iceland)

Title: Guessing and proving theorems for permutation patterns
Abstract: The object of interest in the study of permutation patterns are permutations and the relative order of subsequences within them. The origins of the field go all the way back to the work of a captain in the English army in 1915. However, Knuth's 1968 description of stack-sortable permutations as those avoiding the pattern 231 was the real starting point. There are numerous natural generalizations of Knuth's work and in this talk we'll cover two: 1) Automation of theorems like Knuth's; and 2) Automating the description problem: "Given a set of permutations, can it be described by the avoidance of patterns".

Previous Speakers

Fall 2013
Spring 2013
Fall 2012
Spring 2012
Fall 2011
Spring 2011
Previous Talks hosted by Janos Pach