New York Combinatorics Seminar

This seminar is sponsored by the CUNY Graduate Center's Math Department and Computer Science Department. It covers a wide range of topics in combinatorics and its applications. 

This is a hybrid seminar, both virtual and in-person, with in-person talks noted in red.

Fridays 12:00 pm - 1:00 pm ET 

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 (alphabetically):  Kira Adaricheva (Hofstra) Deepak Bal (Montclair State) Nadia Benakli (City Tech) Jonathan Cutler (Montclair State) Ezra Halleck (City Tech), Sandra Kingan (Graduate Center & Brooklyn College), Joseph Malkevitch (Graduate Center & York College), Kerry Ojakian (BCC), Megan Owen ( Graduate Center &Lehman College), Anna Pun (Baruch College), Abigail Raz (Cooper Union) Eric Rowland (Hofstra) Mingxian Zhong (Graduate Center & Lehman College).

Spring 2024 Talks

Zoom link for virtual talks:
Password: nycs

Room for in-person talks: Graduate Center 3306 (changed from last semester)

We are returning to primarily in-person talks. Please let us know if you are in the NY area and available to give a talk on a Friday.

Feb 16:  Eric Rowland (Hofstra University) (in person)

Title: Algebraic power series and their automatic complexity
Abstract: A theorem of Christol gives a characterization of automatic sequences over a finite field: a sequence is automatic if and only if its generating series is algebraic. Since there are two representations for such a sequence -- as an automaton and as a bivariate polynomial -- a natural question is how the size of one representation relates to the size of the other. Bridy used tools from algebraic geometry to bound the size of the minimal automaton in terms of the size of the minimal polynomial. We have a new proof of Bridy's bound that works by converting algebraic sequences to diagonals of rational functions. Crucially for our interests, this approach can be adapted to work not just over a finite field but over the integers modulo a prime power. This is joint work with Manon Stipulanti and Reem Yassawi. 

Feb 23: Sepehr Hajebi (University of Waterloo) (virtual)

Title: Treewidth, Erdos-Posa and induced subgraphs
Abstract: Trees are (connected) graphs with no cycle as a subgraph. Erdos and Posa proved that for every c > 0,  graphs with no subgraph isomorphic to the disjoint union of c cycles remain proportionately close to trees, in the sense that they have bounded “treewidth.” What about graphs with no induced subgraph isomorphic to the disjoint union of c cycles? We call such graphs “c-perforated.” Complete graphs and complete bipartite graphs are 2-perforated graphs with large treewidth, and so bounded treewidth is not possibile anymore. There is also a sparse example, due to Bonamy et. al., which consists of 2-degenerate, 2-perforated graphs of unbounded treewidth. But that’s it: we prove that for every c > 1, complete bipartite graphs, and the example by Bonamy et. al. (slightly adjusted) are the only constructions of c-perforated graphs with unbounded treewidth (up to taking induced subgraphs). This is based on joint work with Bogdan Alecu, Maria Chudnovsky and Sophie Spirkl.

Mar 1: No talk

Mar 8: Chaim Goodman-Strauss (MoMath) (in person)

Title: Monotiling
Abstract: With the recent discovery of an “aperiodic monotile” we survey the status of several related decision and existence problems, in a variety of settings. For example, it remains an open question whether or not there could be decision procedure whether or not copies of a given shape may be fitted together without gaps or overlaps to form a tiling of the entire Euclidean plane (is the “monotiling problem” undecidable). Similarly it is unknown whether or not, for any N, there exists a shape in the Euclidean plane that can be fitted together to form at least N concentric rings but cannot form a complete tiling (whether or not “Heesch number” is unbounded). A typical implication is that if the monotiling problem is undecidable then Heesch number is unbounded.

Mar 15: Kira Adaricheva (Hofstra University) (in person)

Mar 22: Sudipta Mallik (Northern Arizona University) (virtual)

Title: Combinatorial aspects of the Moore-Penrose inverse

Abstract: Several matrices such as adjacency and incidence matrices can be associated with a graph. There are interesting results between the structure of a graph and the properties of the associated matrices.  A real or complex matrix has a unique generalized inverse known as the Moore-Penrose inverse. We will present combinatorial formulas of the entries of the Moore-Penrose inverses of some matrices associated with a graph. The same will be discussed for signed graphs. We will present open problems some of which are accessible to undergraduate students.

Mar 29: Holiday (Good Friday)

Apr 5: No talk

Saturday April 13: New York Combinatorics Day 2024
Keynote speakers:   
Location: Hofstra University
Please encourage your students to present posters in the poster session.

April 19: Aristotelis Chaniotis (University of Waterloo, Canada) (in person)

Apr 26: No talk (CUNY Spring Break)

May 3: TBD

May 27 - 31: New York Graph Theory Workshop
Keynote speakers: TBD
Location: CUNY Graduate Center


Previous Speakers

Fall 2023
Spring 2023
Fall 2022
Spring 2022
Fall 2021
Spring 2021
Fall 2020
Spring 2020
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