**New York Combinatorics Seminar**

**New York Combinatorics Seminar**

**Fall 2021 (Virtual)**

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.

Fridays Noon - 1:00 pm ET

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), Abigail Raz (Cooper Union) Eric Rowland (Hofstra) Mingxian Zhong (Graduate Center & Lehman College).

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

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

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

**Abstract:** 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: Enumerating restricted Dyck paths with context-free grammars**

**Abstract: **I will be giving a talk on my joint paper with Robert Dougherty-Bliss, "Enumerating Restricted Dyck Paths with Context-Free Grammars." The number of Dyck paths of semilength n is famously C_n, the nth Catalan number. This fact follows after noticing that every Dyck path can be uniquely parsed according to a context-free grammar. Doron Zeilberger showed that many restricted sets of Dyck paths satisfy different, more complicated grammars, and from this derived various generating function identities. We take this further, highlighting some combinatorial results about Dyck paths obtained via grammatical proof and generalizing some of Zeilberger’s grammars to infinite families.

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

**Title: Maximal linklessly embeddable graphs**

**Abstract: **This talk is about graphs embedded in the 3-dimensional space. We study graphs which are linklessly embeddable and, in particular, graphs which are maximal with this property (maxnil graphs). Linklessly embeddable graphs can be embedded in space in such a way that no two cycles link non-trivially. We ask how many edges can a maxnil graph with N vertices have. In trying to answer this question, we show how to construct larger maxnil graphs from smaller maxnil graphs. This is joint work with Ramin Naimi and Andrei Pavelescu.

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

**Title: A graph theoretic approach for criminal investigation and network analysis**

**Abstract: **In this work we used cluster analysis to partition a connected drug trafficking network (DTN) based on the communication strength among the actors. Cluster analysis is a method used to partition a data set into several clusters such that all data points within one cluster are more similar than those belonging to separate clusters. Here we posed the following question: Given a graph with nodes (actors), edges (communications between actors), and edge weights (the number of shared actors between two actors), is it possible to partition the graph into two subgraphs using the spectral clustering method (SCM) to optimize a function “M_cut” that maximizes similarities within each cluster while simultaneously minimizing similarities between separate clusters? Further, does a combination of SCM and linkage-based refinement methods lower the cut value? This work can assist law enforcement personnel in evaluating which actors are more connected to each other, and thus help them in planning efficient disruption strategies. This work is jointly done with Katie Salas.

**Nov 26, 2021: Thanksgiving Break**

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

**Title: ****A note on the higher order Turan inequalities for k-regular partitions**

**Abstract:** Nicolas and DeSalvo and Pak proved that the partition function p(n) is log concave for n >= 25. Chen, Jia and Wang proved that p(n) satisfies the third order Turan inequality, and that the associated degree 3 Jensen polynomials are hyperbolic for n>= 94. Recently, Griffin, Ono, Rolen and Zagier proved more generally that for all d, the degree $d$ Jensen polynomials associated to p(n) are hyperbolic for sufficiently large n. In this talk, we will see that the same result holds for the k-regular partition function p_k(n) for k >= 2. In particular, for any positive integers d and k, the order d Turan inequalities hold for p_k(n) for sufficiently large n. The case when d = k = 2 proves a conjecture by Neil Sloane that p_2(n) is log concave. This is a joint work with William Craig.

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

**Title: Long cycles in Balanced Tripartite Graphs**

**Abstract: **In this talk, we will survey the relevant literature, namely degree and edge conditions for Hamiltonicity and long cycles in graphs, including bipartite and k-partite results. We will then prove that if G is a balanced tripartite graph on 3n vertices, G must contain a cycle of length at least 3n-1, provided that $e(G) \geq 3n^2-4n+5$ and $n\geq 14$. The result will be generalized to long cycles for 2-connected graphs when the minimum degree is large enough. Joint work with G. Araujo-Pardo, J. Faudree, K. Hogenson, R. Kirsch, L. Lesniak, and J. McDonald.

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

**Title: Lower Bounds on Generalized Ramsey Numbers via Color Energy**

**Abstract: **Let the generalized Ramsey number f(n,p,q) denote the least integer c such that K_n can be edge-colored with c colors such that every set of p vertices spans a clique with at least q colors. in this talk, we will discuss the method of color energy graphs, which borrows some ideas from the concept of additive energy used in additive combinatorics to find new lower bounds on generalized Ramsey numbers, and the connections between generalized Ramsey numbers and the well-known hard problem of determining extremal numbers for different bipartite graphs. Joint work with Jozsef Balogh, Emily Heath and Robert A. Krueger.

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

**Fall 2021**

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.

Fridays Noon - 1:00 pm ET

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), Abigail Raz (Cooper Union) Eric Rowland (Hofstra) Mingxian Zhong (Graduate Center & Lehman College).

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

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

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

**Abstract:** 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: Enumerating restricted Dyck paths with context-free grammars**

**Abstract: **I will be giving a talk on my joint paper with Robert Dougherty-Bliss, "Enumerating Restricted Dyck Paths with Context-Free Grammars." The number of Dyck paths of semilength n is famously C_n, the nth Catalan number. This fact follows after noticing that every Dyck path can be uniquely parsed according to a context-free grammar. Doron Zeilberger showed that many restricted sets of Dyck paths satisfy different, more complicated grammars, and from this derived various generating function identities. We take this further, highlighting some combinatorial results about Dyck paths obtained via grammatical proof and generalizing some of Zeilberger’s grammars to infinite families.

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

**Title: Maximal linklessly embeddable graphs**

**Abstract: **This talk is about graphs embedded in the 3-dimensional space. We study graphs which are linklessly embeddable and, in particular, graphs which are maximal with this property (maxnil graphs). Linklessly embeddable graphs can be embedded in space in such a way that no two cycles link non-trivially. We ask how many edges can a maxnil graph with N vertices have. In trying to answer this question, we show how to construct larger maxnil graphs from smaller maxnil graphs. This is joint work with Ramin Naimi and Andrei Pavelescu.

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

**Title: A graph theoretic approach for criminal investigation and network analysis**

**Abstract: **In this work we used cluster analysis to partition a connected drug trafficking network (DTN) based on the communication strength among the actors. Cluster analysis is a method used to partition a data set into several clusters such that all data points within one cluster are more similar than those belonging to separate clusters. Here we posed the following question: Given a graph with nodes (actors), edges (communications between actors), and edge weights (the number of shared actors between two actors), is it possible to partition the graph into two subgraphs using the spectral clustering method (SCM) to optimize a function “M_cut” that maximizes similarities within each cluster while simultaneously minimizing similarities between separate clusters? Further, does a combination of SCM and linkage-based refinement methods lower the cut value? This work can assist law enforcement personnel in evaluating which actors are more connected to each other, and thus help them in planning efficient disruption strategies. This work is jointly done with Katie Salas.

**Nov 26, 2021: Thanksgiving Break**

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

**Title: ****A note on the higher order Turan inequalities for k-regular partitions**

**Abstract:** Nicolas and DeSalvo and Pak proved that the partition function p(n) is log concave for n >= 25. Chen, Jia and Wang proved that p(n) satisfies the third order Turan inequality, and that the associated degree 3 Jensen polynomials are hyperbolic for n>= 94. Recently, Griffin, Ono, Rolen and Zagier proved more generally that for all d, the degree $d$ Jensen polynomials associated to p(n) are hyperbolic for sufficiently large n. In this talk, we will see that the same result holds for the k-regular partition function p_k(n) for k >= 2. In particular, for any positive integers d and k, the order d Turan inequalities hold for p_k(n) for sufficiently large n. The case when d = k = 2 proves a conjecture by Neil Sloane that p_2(n) is log concave. This is a joint work with William Craig.

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

**Title: Long cycles in Balanced Tripartite Graphs**

**Abstract: **In this talk, we will survey the relevant literature, namely degree and edge conditions for Hamiltonicity and long cycles in graphs, including bipartite and k-partite results. We will then prove that if G is a balanced tripartite graph on 3n vertices, G must contain a cycle of length at least 3n-1, provided that $e(G) \geq 3n^2-4n+5$ and $n\geq 14$. The result will be generalized to long cycles for 2-connected graphs when the minimum degree is large enough. Joint work with G. Araujo-Pardo, J. Faudree, K. Hogenson, R. Kirsch, L. Lesniak, and J. McDonald.

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

**Title: Lower Bounds on Generalized Ramsey Numbers via Color Energy**

**Abstract: **Let the generalized Ramsey number f(n,p,q) denote the least integer c such that K_n can be edge-colored with c colors such that every set of p vertices spans a clique with at least q colors. in this talk, we will discuss the method of color energy graphs, which borrows some ideas from the concept of additive energy used in additive combinatorics to find new lower bounds on generalized Ramsey numbers, and the connections between generalized Ramsey numbers and the well-known hard problem of determining extremal numbers for different bipartite graphs. Joint work with Jozsef Balogh, Emily Heath and Robert A. Krueger.

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