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

Fridays 11:45 am - 12:45 pm 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).

NY Combinatorics seminar is transitioning to a virtual format for the rest of this semester.

Mar 20, 2020: Roman Kossak (CUNY Graduate Center and BCC)

Link: Zoom Meeting https://zoom.us/j/762373554

Title: Kernels of digraphs having local finite height
Abstract: Under certain assumptions, a nonstandard model of arithmetic admits an assignment of truth values for all of its sentences, standard and nonstandard. This important result in the model theory of arithmetic was proved in 1981 by Kotlarski, Krajewski and Lachlan, with a proof employing a ``rather exotic proof-theoretic technology." In 2009, Enayat and Viser gave a much more accessible model-theoretic proof. In 2018, Schmerl isolated the graph-theoretic component of the Enayat-Visser proof, by showing that certain infinite graphs have kernels, from which the theorem can be obtained as a straightforward corollary. This story is an excellent example of how mathematics gets simplified. I will explain all basic concepts and I will outline the proof of Shmerl's result. Schmerl's paper is at: arXiv:1807.11832.

Mar 27, 2020: Manon Stipulanti (Hofstra University)

Link: Zoom Meeting https://zoom.us/j/316044795

Title: Avoiding fractional powers on the alphabet N
Abstract: Combinatorics on words is a relatively recent area of discrete mathematics, which finds its roots in the work of Axel Thue at the beginning of the 20th century. Avoidance of patterns is among the hottest topics in combinatorics on words. In this talk, I will focus on lexicographically least words on the alphabet of non-negative integers avoiding some specific patterns called fractional powers. This is joint work with Eric Rowland.

Apr 3, 2020: Jonathan David Farley (Morgan State University)

Link: Zoom Meeting https://zoom.us/j/107586626

Title: A "Challenging Question" of Björner from 1976: Every Infinite Geometric Lattice of Finite Rank Has a Matching
Abstract: It is proven that every geometric lattice of finite rank greater than 1 has a matching between the points and hyperplanes. This answers a question of Pölya Prize-winner Anders Björner from the 1981 Banff Conference on Ordered Sets, which he raised as a "challenging question" in 1976.
See this Handout.

Apr 17, 2020: Pawel Pralat (Ryerson University, Canada)

Zoom Link: https://zoom.us/j/445367382

Title: A variant of the Erdös-Rényi random graph process
Abstract: We consider a natural variant of the Erdös-Rényi inspired by the combinatorial data fusion problem that itself is connected to a number of important problems in graph theory. We will show that a phase transition occurs when the number of special vertices is roughly $n^{1/3}$, where $n$ is the number of vertices. This is joint work with Adam Logan and Mike Molloy.

Apr 24, 2020: Laura Silverstein (Brooklyn College, CUNY)

Zoom Link: https://zoom.us/j/91107809608

Title: Ehrhart tensor polynomials
Abstract: An extension of the Ehrhart polynomial to tensor valuations on lattice polytopes is introduced. In particular, we initiate the study of the Ehrhart tensor polynomial, its coefficients, and its coefficients in a certain binomial basis - an extension of the $h^*$-polynomial. We will concentrate on the matrix case providing comparisons to classical Ehrhart theory. The reciprocity results of Ehrhart and MacDonald are extended, a Pick-type theorem is given, as is a result analagous to Stanley's nonnegativity. This is joint work with Monika Ludwig (TU Wien) and, separately, with Soren Berg (Fit Analytics) and Katharina Jochemko (KTH Stockholm).

May 15, 2020: J. B. Nation (University of Hawaii)

Zoom Link: https://us02web.zoom.us/j/83348644967 Password required

Title: A simple semidistributive lattice.
Abstract: There is no finite simple semidistributive lattice. Is there an infinite one? The answer is yes, and the talk will focus on why you might care (the role of semidistributivity in lattices). This is joint work with Ralph Freese.