New York Combinatorics Seminar

Sponsored by the CUNY Graduate Center's Math Department and Computer Science Department

Fridays Noon - 1:00 pm ET
This seminar covers a wide range of topics in combinatorics and its applications.

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: CUNY: Nadia Benakli (City Tech) Ezra Halleck (City Tech), Sandra Kingan (The Graduate Center and Brooklyn College), Joseph Malkevitch (The Graduate Center and York College), Kerry Ojakian (BCC), Megan Owen (The Graduate Center and Lehman College), Mingxian Zhong (The Graduate Center and Lehman College).
Montclair State University:
Deepak Bal, Jonathan Cutler
Hofstra University: Kira Adaricheva, Eric Rowland

Fall 2021 Talks

The zoom link is

Email any one of the co-organizers for the password. It is the same as last semester.

Sep 3, 2021: Aparna Lakshmanan S. (Cochin University of Science and Technology, India)

Title: Graph Labeling Problems: From Leech Trees to Leech Graphs
Abstract: A graph labeling is a function with some specific properties which assigns values to vertices, edges, or both. Graceful labeling, edge graceful labeling, and harmonic labeling are some of the well know graph labelings. In this talk, I will focus on a special kind of edge labeling called Leech labeling, introduced by John Leech in 1975. Let T be a tree of order n. For any edge labeling f from the edge set E to the natural numbers, the weight of a path P is the sum of the labels of the edges of P and is denoted by w(P). If the weights of the $^nC_2$ paths in T are exactly 1, 2,...,$^nC_2$, then f is called a Leech labeling and a tree which admits a Leech labeling is called a Leech tree. I will discuss some known results in Leech labeling, a new concept called Leech index, and the possibility of extending Leech labeling to general graphs. Some Leech related labeling will also be discussed. This is joint work with S. Arumugam and Seema Varghese.

Sep 10: No talk

Sep 17: No Talk

Sep 24, 2021: Robert Dougherty-Bliss (Rutgers University)

Title: Combinatorial Union Busting with Stopped Strings
A factory manager purchases an experimental machine and subjects it to a testing regime. The machine is certified as soon as it consecutively passes half of its total tests. That is, the testing process produces a binary string (b(1), b(2), ...) (0 = pass, 1 = fail), and we say that the string is "stopped" at time T provided that b(k) = 0 for all k in (T/2, T]. The "stopping time" of the string is the smallest such T, if any exist, and infinity otherwise. We will show that the binary strings of length n with stopping time n are enumerated by the Narayana-Zidek-Capell numbers (OEIS A2083), then generalize our results to get an infinite family of analogous numbers not in the OEIS. We will answer and pose related questions and generalizations such as, "how likely is a random binary sequence likely to have a finite stopping time?" and "what integers have a 'stopped' binary expansion?" Joint with Charles Kenney.

Oct 1, 2021: Vaidyanathan Sivaraman (Mississippi State University)

Title: Polynomial chi-boundedness
For what graph classes can we bound the chromatic number of a graph as a polynomial function of its clique number? Such a graph class is called polynomially chi-bounded. This talk will survey graph classes which are known to be polynomially chi-bounded. Several open problems will also be mentioned.

Oct 8, 2021: Michael Barrus (University of Rhode Island)

Title: The Erdős-Gallai differences of a degree sequence
Abstract: The Erdős-Gallai criteria are a set of inequalities that characterize lists of nonnegative integers that are degree sequences of finite simple graphs. A number of graph families, including the split, threshold, and weakly threshold graphs, have degree sequence characterizations that rely on one or more of the Erdős-Gallai inequalities holding with equality or near equality. We define an Erdős-Gallai difference to be the difference of the two sides in one of the Erdős-Gallai inequalities. After briefly surveying known results on the Erdős-Gallai differences, we look at the behavior of these differences under graph complementation and in the context of two partial orders. In particular, we show that the maximum and last "principal'' Erdős-Gallai difference are shared by the degree sequences of a graph and of its complement, and they are monotone in the induced subgraph poset and in a poset introduced by S.B. Rao. As consequences, we give broader context to a few properties of split and threshold graphs. We conclude with a number of directions for further study.

Oct 15, 2021: Sophie Spirkl (University of Waterloo, Canada)

Title: Induced subgraphs and treewidth

Abstract: Treewidth, introduced by Robertson and Seymour in the graph minors series, is a fundamental measure of the complexity of a graph. While their results give an answer to the question, “what minors occur in graphs of large treewidth?,” the same question for induced subgraphs is still open. I will talk about some conjectures and recent results in this area. This is joint work with Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Pawel Rzazewski, and Kristina Vuskovic.

Oct 22 2021: Abigail Raz (Cooper Union)

Title: Perfect matchings in the random bipartite geometric graph
We consider the standard random bipartite geometric graph process in which n red vertices and n blue vertices are placed, at random, on the unit d-dimensional cube and edges are added sequentially, between vertices of different colors, in increasing order of edge-length. A natural question is to ask whether the first edge in the process that results in the minimum degree being at least one coincides, with high probability, with the first edge that creates a perfect matching. While this was already known to be false when d=2, as the thresholds are not even of the same order, we are able to positively answer it for d > 2. This is joint work with Xavier Perez-Gimenez.

Oct 29, 2021: Hailun Zheng (University of Copenhagen, Denmark)

Title: Reconstruction of simplicial polytopes
Abstract: What information do we need to know to determine the combinatorial type of a d-dimensional simplicial polytope P? Let [d/2] represent the greatest integer less than or equal to d/2. On one hand, Perles and Dancis proved that the [d/2]-skeleton of P determines the face lattice of P. On the other hand, the space of affine dependencies of vertices of P, or equivalently, the space of affine 1-stresses of P, also determines the face lattice of P. Motivated by these results, Kalai conjectured that for any 0 <= k <= [d/2], the k-skeleton of P along with the space of affine (k+1)-stresses of P uniquely determine the combinatorial type of P. In this talk, I will give a proof of this conjecture in the case k=1 and discuss a few other related conjectures. This is joint work with Isabella Novik.

Nov 5, 2021: Aj Bu (Rutgers University)


Nov 12, 2021: Elena Pavelescu (University of South Alabama)


Nov 19, 2021: Urmi Ghosh-Dastidar (New York City College of Technology, CUNY)


Nov 26, 2021: Thanksgiving Break

Dec 3, 2021: Anna Pun (University of Virginia)


Dec 10, 2021: Zhanar Berikkyzy (Fairfield University)


Dec 17, 2021: Sean English (University of Illinois at Urbana Champaign)


Previous Co-Organizers

Christopher Hanusa (Spring 2011 - Spring 2015)

Previous Speakers

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