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. The seminar went virtual during the pandemic. Talks are posted on our YouTube channel https://youtube.com/@NYCombinatorics
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 Kn or Kn,n 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 fd(G,v). Since 2008, many authors have explored fd(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 fp(G,v). We will discuss how far apart fd(G,v) and fp(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) (in-person)
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:
Abstract:
Apr: 18: No talk (CUNY Spring Break)
Apr 25: Joshua Sussan (Medgar Evers College) (in-person)
Title:
Abstract:
May 2: Herman Chau (University of Washington)
Title:
Abstract:
May 9: Christopher Hanusa (Queens College, CUNY) (in-person)
Title:
Abstract:
_________________________________________________________
Previous Speakers
Fall 2024
Spring 2024
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