## 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 https://us02web.zoom.us/j/86136386476

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 StringsAbstract:** 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-boundednessAbstract: **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 graphAbstract:** 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)**

**Title:**

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

**Title:**

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

**Title:**

**Nov ****26****, 2021: ****Thanksgiving Break**

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

**Title:**

**Dec 10****, 2021: ****Zhanar Berikkyzy**** (****Fairfield University****)**

**Title:**

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

**Title: **

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