# 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:

https://brooklyn-cuny-edu.zoom.us/j/83457468109

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

Time:

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