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.
This is a hybrid seminar, both virtual and in-person, with in-person talks noted in red.
Fridays 12:00 pm - 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), Anna Pun (Baruch College), Abigail Raz (Cooper Union) Eric Rowland (Hofstra) Mingxian Zhong (Graduate Center & Lehman College).
Spring 2023 Talks
Zoom Link for Spring 2023 Virtual Talks:
https://us02web.zoom.us/j/83808060614
The link changes every semester, but the password stays the same. In person talks are specified in red.
Feb 10, 2023: Vinayak Joshi (Savitribai Phule Pune University, India)
Title : Chordal and Perfect zero-divisor graphs of posets and applications to graphs associated with algebraic structures
Abstract: In this talk, we discuss the characterizations of the perfect zero-divisor graphs and chordal zero-divisor graphs (its complement) of ordered sets. These results are applied to the zero-divisor graphs of finite reduced rings, the comaximal ideal graphs of rings, the annihilating ideal graphs, the intersection graphs of ideals of rings, and the intersection graphs of subgroups of groups. In fact, it is shown that these graphs associated with a commutative ring R with identity can be effectively studied via the zero-divisor graph of a specially constructed poset from R.
Feb 17, 2023: No Talk
Feb 24, 2023: Sheila Sundaram
Title: Schur-positivity of power sums
Abstract: We investigate the Schur-positivity of sums of power sum symmetric functions, in particular those corresponding to rectangular partitions. We show that these have a nice description in terms of the representations induced from the subgroup generated by the long cycle of the symmetric group. The number-theoretic Ramanujan sum is an important ingredient of these representations. Parts of this talk are based on recent joint work with John Shareshian.
Mar 3, 2023: Sergi Elizalde (Dartmouth University)
Title: Descents on noncrossing and nonnesting permutations
Abstract: Stirling permutations were introduced by Gessel and Stanley to give a combinatorial interpretation of certain polynomials related to Stirling numbers, which count set partitions with a given number of blocks. A natural extension of Stirling permutations are noncrossing (also called quasi-Stirling) permutations, which are in bijection with labeled rooted plane trees. Archer et al. introduced these permutations and conjectured that there are (n+1)^(n-1) such permutations of size n having n descents. In this talk we prove this conjecture, and we find the generating function for noncrossing permutations by the number of descents. We show that some of the properties of descents on usual permutations and on Stirling permutations have an analogue for noncrossing permutations. Finally, we consider a nonnesting analogue, and we show that the polynomial giving the distribution of the number of descents on nonnesting permutations is a product of an Eulerian polynomial and a Narayana polynomial. It follows that, rather unexpectedly, this polynomial is palindromic.
Mar 10, 2023: Richard Stanley (Massachusetts Institute of Technology)
2:00 pm
Title: The X-Descent Set of a Permutation
Abstract: Let $X$ be a subset of $\{(i,j) \colon 1\leq i,j \leq n,\ i\neq j\}$. The \emph{$X$-descent set} of a permutation $w = a_1 \cdots a_n$ of $1,2,\dots,n$ is defined by
$$ \mathrm{XDes}(w) = \{i \colon (a_i,a_{i+1})\in X\}. $$
If $X = \{(i,j) \colon n\geq i>j\geq 1\}$, then $\mathrm{XDes}(w) = \mathrm{Des}(w)$, the ordinary descent set, a well-studied and important statistic on permutations. We define a symmetric function $U_X$ which is a generating function for permutations $w\in S_n$ according to their $X$-descent set. We will discuss some properties of $U_X$, including connections with Hamiltonian paths in digraphs. A knowledge of symmetric functions will be helpful but not essential for understanding the talk.
Mar 17, 2023: Pawel Pralat (Toronto Metropolitan University and The Fields Institute)
in-person
Title: Semi-random process
Abstract: The semi-random graph process is a single-player game that begins with an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. During the talk, we will focus on constructing perfect matchings and Hamilton cycles but constructing a subgraph isomorphic to an arbitrary fixed graph G will be briefly discussed. We will also consider a natural generalization of the process to s-uniform hypergraphs.
Mar 24, 2023: Zachary Hamaker (University of Florida)
Title: Low degree permutation statistics
Abstract: There is a natural notion of "degree" for functions from the symmetric group to the complex numbers, which translates roughly to saying the function counts certain weighted patterns. Low degree class functions have a classical interpretation in terms of the cycle structure of permutations. I will explain how to translate between pattern counts to cycle structure using a novel symmetric function identity analogous to the Murnaghan-Nakayama identity. This relationship allows one to lift many probabilistic properties of permutation statistics to certain non-uniform distributions, and I will present some results in this direction. This is joint work with Brendon Rhoades.
Mar 31, 2023: Maria Chudnovsky (Princeton University) in person
Title: Induced subgraphs and tree decompositions
Abstract: Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph. Tree decompositions have traditionally been used in the context of forbidden graph minors; bringing them into the realm of forbidden induced subgraphs has until recently remained out of reach. Over the last couple of years we have made significant progress in this direction, exploring both the classical notion of bounded tree-width, and concepts of more structural flavor. This talk will survey some of these ideas and results.
Apr 7, 2023: Spring Break
Apr 14, 2023: J B Nation (University of Hawaii)
Title: The maximum size of deletion error correcting codes
Abstract: What is the largest size of a length n binary code that can correct t deletion errors? This talk will explain deletion error correcting codes and report some recent progress on this still-open question by various members of the coding theory community.
Apr 21, 2023: Csaba Biro (University of Louisville)
Title: Improved bounds on the on-line chain partitioning of posets
Abstract: Dilworth's Theorem states that the minimum number of chains required to partition a poset into chains is the size of a maximum antichain, i.e. the width of the poset. Things get trickier, if one wants do the chain partitioning in an on-line manner. In this setting, two players play a game: one player is building a poset, revealing one point in each turn, and another player irrevocably assigns the new point into a chain. In his seminal paper, Kierstead proved in 1981, that if the width of the poset is bounded, an on-line chain partitioning algorithm exists into a bounded number of chains. The best bound here, known as the on-line width of the poset, is still not known, and the problem of determining the on-line width has been studied for various classes of posets. In two recent papers we improved the best known lowers bounds on the on-line width of various classes of posets. Joint work with Israel R. Curbelo
Apr 28, 2023: No Talk
May 5, 2023: Hermie Monterde (University of Manitoba)
Title: Quantum walks on graphs: an overview
Abstract: How does quantum information travel across a network? To make sense of this question, we need the concept of a (continuous-time) quantum walk (CTQW). In this talk, I will introduce this concept and discuss some types of quantum phenomena that are of interest to both physicists and mathematicians, such as perfect state transfer and pretty good state transfer. Our focus is to highlight the role of (spectral and algebraic) graph theory in the study of quantum walks and discuss some open problems in the area.
_________________________________________________________
Previous Speakers
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