New York Combinatorics Seminar

Sponsored by the Graduate Center's Math Department and Computer Science Department

Fridays 11:45 am - 12:45 am in Room 4422

This seminar covers a wide range of topics in combinatorics and its applications.

The CUNY Graduate Center is located at 365 Fifth Avenue (at the corner of 34th Street), New York. It can be easily reached by subway using the B,D,F,N,Q,R, or 6 train.

Seminar Co-Organizers:
CUNY: Nadia Benakli (City Tech) Ezra Halleck (City Tech), Sandra Kingan (Brooklyn College), Joseph Malkevitch (York College), Kerry Ojakian (BCC), Mingxian Zhong (Lehman College),
Montclair State University: Deepak Bal, Jonathan Cutler
Hofstra University: Kira Adaricheva, Eric Rowland

Spring 2020 Talks

Feb 21, 2020: Colin Defant (Princeton University)

Title: Valid Hook Configurations and Uniquely Sorted Permutations
Abstract In his 1990 Ph.D. thesis, Julian West introduced the "stack-sorting map," a function that sends permutations to permutations. I will describe a method for computing the number of preimages of an arbitrary permutation under this map. This method, which can be applied to answer many questions about the stack-sorting map, relies on new combinatorial objects called "valid hook configurations." I will discuss a surprising connection between these objects and free probability theory. This connection will allow us to enumerate "uniquely sorted permutations," which are permutations with exactly 1 preimage under the stack-sorting map.I will also briefly discuss some bijective enumerations of pattern-avoiding valid hook configurations and uniquely sorted permutations, including recent (separate) works of Hanna Mularczyk and Maya Sankar.

Feb 28, 2020: Peter Winkler (Dartmouth College and National Museum of Mathematics)

Title: Graphs and the Gittins Index
Abstract: You're trying to settle a conjecture. You try to prove it, but without success. Should you switch to looking for a counterexample? Or: You're trying to become a millionaire, and you are examining several possible schemes. Which one should you try first? We model these situations with multiple tokens on the vertices of a graph, each of which steps to a random neighbor when prodded. You want to get some token to a specified target vertex as fast as you can. It turns out that there's a shockingly simple way to play this game optimally, based on a variation of a concept called the "Gittins index." We'll present our adaptation of a fabulous proof, due to Richard Weber, that this really works. (Joint work with Ioana Dumitriu and Prasad Tetali).

Previous Co-Organizers

Christopher Hanusa (Spring 2011 - Spring 2015)

Previous Speakers

Fall 2019
Spring 2019
Fall 2018
Spring and Summer 2018
Fall 2017
Spring 2017
Fall 2016
Spring 2016
Fall 2015
Spring 2015
Fall 2014
Spring 2014
Fall 2013
Spring 2013
Fall 2012
Spring 2012
Fall 2011
Spring 2011
Previous Talks hosted by Janos Pach