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.  Since 2020, talks are posted on our YouTube channel https://youtube.com/@NYCombinatorics and previous talks are catalogued on the page Previous Semesters.

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

Location: 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).

Lead Organizer:
2024 - 2025: Anna Pun
2011 - 2024: Sandra Kingan

Spring 2025 Talks

Zoom link for virtual talks:
https://us06web.zoom.us/j/88103577657?pwd=Mmyme7DOGleqMATw2SAv8yAy89Nf8Q.1

Meeting ID: 881 0357 7657
Passcode: nycs 

Room for in-person talks: Graduate Center 9116

Feb 7:  Sandra Kingan (Brooklyn College and the Graduate Center, CUNY) (in-person)

Title: Pancyclicity of almost-planar graphs

Abstract: A non-planar graph is almost-planar if, for every edge e, either deleting or contracting e results in a planar graph. A graph with n vertices is pancyclic if it contains a cycle of every length from 3 to n and it is Hamiltonian if it contains a cycle of length n. A Hamiltonian-path is a path of length n and a graph with a Hamiltonian path between every pair of vertices is called Hamiltonian-connected. We prove that a -connected almost-planar graph is pancyclic if and only if it has a cycle of length 3. Furthermore, we prove that a 4-connected almost-planar graph is both pancyclic and Hamiltonian-connected. This is joint work with Santiago Adams.

Feb 14:  No Talk

Feb 21: Deepak Bal (Montclair State University) (in-person)

Title: Generalized Ramsey number of cycles.

Abstract: Given graphs G and H and an integer q at least 2, the generalized Ramsey number f(G,H,q)  is the minimum number of colors needed to color the edges of G such that every copy of H receives at least q different colors. In this talk, we discuss some results when G is the complete graph on n vertices or the complete bipartite graph with n vertices in each vertex class and H is a (short) cycle. The main tool we use is the new and powerful method of "conflict free hypergraph matching." This is joint work with Patrick Bennett, Emily Heath and Shira Zerbib.

Feb 28: Abigail Raz (Cooper Union) (in-person)

Title: The Path Variant of the Explorer-Director Game on Graphs

Abstract: The Explorer Director game, first introduced by Nedev and Muthukrishnan (2008), simulates a Mobile Agent exploring a ring network with an inconsistent global sense of direction. The two players, the Explorer and the Director, jointly control the movement of a token on the graph. During each turn, the Explorer calls any valid distance, d, with the aim of maximizing the number of vertices the token visits, and the Director moves the token to any vertex distance d away with the aim of minimizing the number of visited vertices. The game, on graph G with starting vertex v, ends when no new vertices could be visited assuming both players are playing optimally, and we denote the total number of visited vertices by $f_d(G,v)$. Since 2008, many authors have explored $f_d(G,v)$ for various graph families as well as analyses of complexity. In this talk, we will focus on a variation of this game focused on path lengths rather than distances. In this variant, if the token is on vertex u, the Explorer is now allowed to select any valid path length, l,  and the Director can now move the token to any vertex v, such that G contains a uv path of length l. The corresponding parameter is denoted by $f_p(G,v)$. We will discuss how far apart $f_d(G,v)$ and $f_p(G,v)$ can be for various graph families.

Mar 7:  Simon Vilmin (University of Aix-Marseille, France) (virtual)

Title: The D-base of finite closure systems

Abstract: A (finite) closure system over a ground set X is a collection of subsets of X---called closed sets---containing X and stable for intersection. Closure systems appear in a wide range of fields such as, algebra, logic, database theory, combinatorial optimization or data mining. Yet, they are usually given by implicit representations, such as  implicational bases (IBs). IBs are collections of statements A --> B, aka implications, where A and B are subsets of X. Such statements mean that whenever a closed set includes A, it must also include B. Several different IBs can encode the same closure system, therefore, several types of IBs have been studied. In particular, the D-base, which originates from the study of free lattices, has recently attracted much attention both from an applied and theoretical point of view. In this talk, we will investigate the problem of finding the D-base of a closure system from its so-called irreducible closed sets (equivalently, from binary data) through the lens of output-sensitive complexity. This talk is based on a recent contribution with Kira Adaricheva and Lhouari Nourine: https://arxiv.org/abs/2404.07037.

Mar 14: No Talk (Purim)

Fri Mar 21: New York Combinatorics Day 2025
Location:  Graduate Center, 4th Floor Science Room, 10:00 am - 3:15 pm
Keynote Speakers:  Zhanar Berikkyzy, Rishi Nath, Eric Ramos
Please encourage your students to present posters in the poster session.

Mar 28:  Parik Chalise (Johns Hopkins University)

Title:  A Proof of Gyárfás Tree Packing Conjecture

Abstract:  The tree packing conjecture (1976) asserts that any family of trees $T_1, T_2, \dots, T_{n}$, where each tree $T_k$ is on $k$ vertices, perfectly packs into the complete graph $K_n$. We settle the conjecture in the affirmative for all $n$. Our proof employs the polynomial method by identifying trees with functions in $\mathbb{Z}_n^{\mathbb{Z}_n}$. This is a joint work with Antwan Clark and Edinah Gnang.

Apr 3: Swee Hong Chan (Rutgers University)

Title: Spanning trees and continued fractions

Abstract: Consider the set of positive integers representing the number of spanning trees in simple graphs with n vertices. How quickly can this set grow as a function of n? In this talk, we discuss a proof of the exponential growth of this set, which resolves an open problem of Sedlacek from 1966. The proof uses a connection with continued fractions and advances towards Zaremba’s conjecture in number theory. This is joint work with Alex Kontorovich and Igor Pak.

Apr 11:  Zhanar Berikkyzy (Fairfield University)  (in-person) 

Title: Maximizing the number of stars in graphs with forbidden properties

Abstract: Erdos proved an upper bound on the number of edges in an n-vertex non-Hamiltonian graph with a given minimum degree and showed sharpness via two members of a particular graph family. Furedi, Kostochka, and Luo showed that these two graphs play the same role when "number of edges" is replaced by "number of t-stars," and that two members of a more general graph family maximize the number of edges among non-k-edge-Hamiltonian graphs. In this work we generalize their former result from Hamiltonicity to related properties (traceability, Hamiltonian-connectedness, k-edge Hamiltonicity, k-Hamiltonicity) and their latter result from edges to t-stars. We identify a family of extremal graphs for each property that is forbidden. This problem without the minimum degree condition was also open; here we conjecture a complete description of the extremal family for each property and prove the characterization in some cases. Finally, using a different family of extremal graphs, we find the maximum number of
t-stars in non-k-connected graphs. This is joint work with K. Hogenson, R. Kirsch, and J. McDonald. 

Apr: 18: No talk (CUNY Spring Break)

Apr 25: Joshua Sussan (Medgar Evers College) (in-person) 

Title: Cellular algebras in categorification

Abstract: We will review the definition of a cellular algebra and show that an algebra defined by Webster is an example.  Webster's algebra plays a prominent role in categorification and we will see that it comes equipped with a p-DG structure.  This allows us to categorify representations of quantum groups at prime roots of unity.

May 2: Herman Chau (University of Washington)  

May 9: Christopher Hanusa (Queens College, CUNY) (in-person) 

______________________________________________________________________