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

Spring 2022 Talks

The zoom link is https://us02web.zoom.us/j/82872727780

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

Feb 18, 2022: Robert Donley (Queensborough Community College, CUNY)

Title:  Lattice path enumeration for semi-magic squares by Latin rectangles
Abstract: Similar to how standard Young tableaux represent paths in the Young lattice, Latin rectangles may be use to enumerate paths in the poset of semi-magic squares with entries zero or one.  The symmetries associated to determinant preserve this poset, and we completely describe the orbits, covering data, and  maximal chains for squares of size 4, 5, and 6.  The last item gives the number of Latin squares in these cases.  To calculate efficiently for size 6, we in turn identify orbits with certain equivalence classes of hypergraphs.  This work is joint with WonGeun Kim. While not required viewing for this talk,  the following video, with links to slides, gives both details for the case of size 3 and applications to Clebsch-Gordan coefficients:  https://www.youtube.com/watch?v=L87zY55VcWM

Feb 25, 2022: Rigoberto Florez (The Citadel)

Title: Some enumerations on non-decreasing Dyck paths
Abstract: A Dyck path is a lattice path in the first quadrant of the xy-plane that starts at the origin and ends on the x-axis. It consists of the same number of North-East (U) and South-East (D) steps. A pyramid is a subpath of the form $U^nD^n$. A valley is a subpath of the form $DU$. The height of a valley is the y-coordinate of its lowest point (local minimum). A Dyck path is called non-decreasing if the heights of its valleys form a non-decreasing sequence from left to right. In this talk, we count several aspects of non-decreasing Dyck paths. We count, for example, the number and weight of pyramids and numbers of primitive paths. At the end of the talk, we introduce the concept of symmetric pyramids and count them. Throughout the talk, we give connections (bijective relations) between non-decreasing Dyck paths with other objects of the combinatorics. Some examples are words, trees, and polyominoes. This is a joint work with Eva Czabarka, José L. Ramírez, and Leandro Junes.

Mar 4,2022: Anna Zamojska-Dzienio (Warsaw Institute of Technology, Poland)

Title: The construction of multipermutation solutions of the Yang-Baxter equation of level 2
Abstract: The Yang-Baxter equation is a fundamental equation occurring in integrable models in statistical mechanics and quantum field theory. Description of all possible solutions seems to be extremely difficult and therefore there were some simplifications introduced (V.G. Drinfeld 1992). We study involutive set-theoretic non-degenerate solutions of the Yang-Baxter equation of multipermutation level 2. These solutions happen to fall into two classes -- distributive ones and non-distributive ones. The distributive ones can be effectively constructed using a set of abelian groups and a matrix of constants. Using this construction, we enumerate all distributive involutive solutions up to size 14. The non-distributive solutions can be also easily constructed, using a distributive solution and a permutation. This is a joint work with Premysl Jedlicka and Agata Pilitowska.  

Mar 11, 2022: Anthony Bonato (Ryerson University, Canada)

Title:  New and Improved Bounds on the Burning Number of a Graph
Abstract: Graph burning is a simplified model for the spread of influence in a network. Associated with the process is the burning number, which quantifies the speed at which the influence spreads to every vertex. The Burning Number Conjecture claims that for every connected graph G of order n, its burning number satisfies $b(G) \le \lceil \sqrt{n} \rceil$. While the conjecture remains open, we prove the best-known bound on the burning number of G, given by $b(G) \le \sqrt{4n/3} + 1$, improving on the previously known $\sqrt{3n/2}+O(1)$ bound. 

Mar 18, 2022: Erin Meger (Wilfrid Laurier University, Canada)

Title: Distanced Eternal Domination on Graphs
Abstract: We consider a dynamic process on a graph that protects vertices from an infinite series of attacks. Eternal domination considers a dominating set of the vertices called guards; subsequently, an attack occurs and the guards must move from their present positions and guards shift to cover the attacked vertex in such a way that they remain in a dominating set.  In eternal k-domination, a set of guards seeks to protect the graph using a distance k dominating set, and can travel a distance of up to k to cover the attacked vertex.  The minimum size of a set such that the graph can be protected from attacks indefinitely is called the eternal k domination number of the graph, denoted $\gamma_{all,k}^{\infty}(G)$. In this talk, we will focus on the case where k=2, and detail the result for the case of perfect m-ary trees of depth d. For such graphs $T$: $$\gamma_{all, 2}^{\infty}(T)=1+\frac{m^d-1}{m^2-1}$$ In general, the computation of this parameter is not known for most graphs, and determining if a set is an eternal k-dominating set is a difficult problem. Other results will be discussed, and open problems towards a reduction on trees will be presented.

Mar 25, 2022: no talk

Apr 1, 2022: Corrine Yap (Rutgers University)

Title: Multicolored hypergraph Ramsey numbers
Abstract:  A central open problem in Ramsey theory is to determine the behavior of r_3(t), the minimum n such that any 2-coloring of the complete 3-uniform hypergraph on n vertices contains a monochromatic complete subgraph on t vertices. In the 1960's, Erdős, Hajnal, and Rado showed that r_3(t) is bounded between exponential and double-exponential in t, but the correct behavior remains unknown. Erdős and Hajnal surprisingly showed that the double-exponential bound is correct if we use four colors instead of two. This raises the question: how does the number of colors influence the growth of the Ramsey number? Generalizing a result of Conlon, Fox, and Rödl, we construct a family of hypergraphs with arbitrarily large tower gaps between the 2-color and q-color Ramsey numbers. We utilize results analogous to the Erdős-Hajnal stepping-up lemma, for Ramsey numbers where we relax the "monochromatic" condition to "spanning few colors." Joint work with Quentin Dubroff, António Girão, and Eoin Hurley.

Apr 8, 2022:  no talk

Apr 12, 2022: (Virtual) Discrete & Computational Geometry Day in Memory of Eli Goodman and Ricky Pollack (12:30–16:05 ET (New York time))
Organized by Springer, NYU, and CUNY
Zoom link: https://springer.zoom.us/j/6440052748

Program: 12:30 Janos Pach (Renyi Institute): Welcome & Introduction
12:40 Andreas Holmsen (KAIST): An allowable feast
13:15 Micha Sharir (Tel Aviv University): Polynomial partitioning: The hammer and some (recent algorithmic) nails
13:50 Esther Ezra (Bar Ilan University): Recent developments on intersection searching
14:25 Xavier Goaoc (Loria, Nancy): Some questions on order types
15:00 Andrew Suk (UC San Diego): Unavoidable patterns in simple topological graphs
15:35 Sylvain Cappell (Courant Institute): Mesh matrices of graphs, of simplicial complexes and of matroids and the significance of their eigenvalues 

https://users.renyi.hu/~pach/geoscape/eve.html  

Apr 15, 2022:  Holiday

Apr 22, 2022:  Holiday

Apr 29, 2022: Eunjeong Yi (Texas A&M University at Galveston)

Title: On the Maker-Breaker Resolving Game on Graphs
Abstract: A set of vertices W of a graph G is a (metric) resolving set if every vertex of G is uniquely determined by its vector of distances to W, and the minimum cardinality among all resolving sets of G is the well-known metric dimension. In this talk, we discuss a two-player game on graphs, called the Maker-Breaker resolving game (MBRG). The MBRG is played on a graph G by two players, named Resolver and Spoiler, who alternately select a vertex of G not yet chosen in the course of the game. Resolver wins the game if, at some point, the vertices chosen by him form a resolving set of G, whereas Spoiler wins if she can prevent Resolver from occupying a resolving set of G. We obtain some results on the outcome of this game played on graphs, and examine the minimum number of moves for either Resolver or Spoiler to win the game. We will also discuss a fractionalized version of this game if time allows.

May 6, 2022: Kristina Wicke (Ohio State University)

Title: On the Colless balance index for rooted binary trees
Abstract: Measures of tree balance play an important role in the analysis of phylogenetic trees. One of the oldest and most popular indices in this regard is the Colless index for rooted binary trees. In this talk, I will focus on the combinatorial properties of the Colless index, in particular its extremal values and the trees that achieve them. While the analysis of the maximum Colless index is relatively straightforward, the analysis of the minimum Colless index is much more involved. I will derive both recursive and closed expressions for the minimum value and highlight a surprising connection between the minimum Colless index and the fractal Blancmange curve. I will then fully characterize the trees that achieve this minimum value and introduce a recurrence to count them. I will end by pointing out some open problems and directions for future research.  (Based on joint work with Tomás M. Coronado, Mareike Fischer, Lina Herbst and Francesc Rosselló).

Previous Speakers

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