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. Talks are posted on our YouTube channel @NYCombinatorics

Fridays 12:00 pm - 1:00 pm ET  (Eastern Time)

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 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)

Title: Representation of convex geometries of convex dimension 3 by spheres

Abstract: In 1984 at the Banff meeting on ordered sets, P. Fishburn and W. Trotter raised the question of whether any 3-dimensional partial order can be represented as the inclusion order of disks on the plane. Generalizations were further considered by G. Brightwell and P. Winkler in 1989, with the problem receiving much attention from order and combinatorics specialists. After partial results by several authors, S. Felsner, P. Fishburn and W. Trotter achieved a negative result (1999): there exists n such that the order n^3 is not representable as a sphere order in any k- dimensional space. The case of ellipsoids was attempted but remained open.  The current work, a collaboration with two students, N. Nevo and A. Agarwal, tackles a similar question for representation of convex geometries of convex dimension 3 by disks on the plane. Convex geometries are closure systems with the anti-exchange axiom and as such they form lattices, thus, they are also posets. Still, poset dimension is quite different from convex dimension. However, we were able to construct a convex geometry of convex dimension 3 that could utilize the negative result of S. Felsner, P. Fishburn and W. Trotter concerning posets. On the positive side, we also use a result of J. Kincses (2015) to prove that every finite poset is an ellipsoid order, resolving the open question.

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:  Deepak Bal (Montclair State University),  Anna Pun (Baruch College), and Zoran Sunik (Hofstra University)
Location: Hofstra University
Time: 10:30 am - 3:30 pm ET
Website: https://sites.google.com/view/nycd2024
Please encourage your students to present posters in the poster session.

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

Title: Local structure of graphs of large K_r-free chromatic number

Abstract: For every r>=2, the K_r-free chromatic number of a graph G, denoted by χ_r(G), is the minimum size of a partition of the set of vertices of G into parts each of which induces a K_r-free graph. In this setting, the K_2-free chromatic number is the usual chromatic number. Following Gyárfás (1987), we say that a hereditary class of graphs is χ-bounded if there exists a function which provides an upper bound for the (usual) chromatic number of each graph of the class in terms of the graph’s clique number. Generalizing the notion of χ-boundedness, we say that a hereditary class of graphs is χ_r-bounded if there exists a function which provides an upper bound for the K_r-free chromatic number of each graph of the class in terms of the graph’s clique number. With an emphasis on a natural generalization of the Gyárfás-Sumner conjecture for χ_r-bounded classes of graphs and on polynomial χ-boundedness, I will discuss some recent developments on χ_r-boundedness and related open problems. This is based on joint work with Mathieu Rundström and Sophie Spirkl.

Apr 26: No talk (CUNY Spring Break)

May 3, 2024: Jeremy Quail (University of Vermont) (virtual)

Title: Positroid envelope classes

Abstract: Postnikov developed a combinatorial decomposition of the Grassmannian using a class of ordered matroids, called positroids. Positroids are matroids realizable by real matrices with all nonnegative maximal minors. They partition the ordered matroids into equivalence classes, called positroid envelope classes. We prove that every positroid envelope class contains a graphic matroid. We show that a positroid is graphic if and only if it is the unique matroid contained in its envelope class. Finally, we characterize the ternary positroids and their corresponding envelope classes.

May 10, 2024: Calum Buchanan  (University of Vermont) (virtual)

Title: A lower bound on saturation numbers and its effectiveness on certain trees

Abstract: The saturation number sat(n, H) of a graph H and positive integer n is the minimum size of an n-vertex graph which does not contain a subgraph isomorphic to H but to which the addition of any edge creates such a subgraph. Erdős, Hajnal, and Moon first studied saturation numbers of complete graphs, and Cameron and Puleo introduced a general lower bound on sat(n, H). In this talk, we present another lower bound on sat(n, H) and a strengthening of this bound when H is triangle-free. Demonstrating its effectiveness, we determine the saturation numbers of diameter-3 trees up to an additive constant; these are double stars Ss,t on s+t vertices whose centers have degrees s and t. Faudree, Faudree, Gould, and Jacobson showed that sat(n, St,t) = (t-1)n/2 + O(1). We show that sat(n, Ss,t) = (st+s)n/(2t+4) + O(1) when s < t. We will also discuss bounds on the saturation numbers of diameter-4 caterpillars. This talk is based on joint work with Puck Rombach.

May 28 - 31: New York Graph Theory Workshop
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