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 PakStanley 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, PakStanley 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^{n1} and proved that it is isometric to the mdilation 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: PoShen 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 ncycle 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 redblue 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) = (s1)(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 semialgebraicity in geometry
Abstract
Friday April 25, 2014 is New York Area Theory Day
May 2, 2014 Peter Maceli (Columbia University)
Title: Coloring Graphs with Forbidden Induced Subgraphs
Abstract
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 bandlimited, in the sense that their Fourier transform matrices are mostly zero matrices, and provide some simple techniques for demonstrating that a given statistic is bandlimited. These techniques allow polynomialtime computation of the Fourier transform of bandlimited 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 stacksortable 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
