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).
Fall 2023 Talks
Zoom link for virtual talks:
https://us02web.zoom.us/j/84195827564
The link changes every semester, but the password stays the same. In person talks are specified in red.
Sep 1, 2023: Jinyoung Park (New York University) in-person
Title: Counting homomorphisms from bipartite graphs
Abstract: We will discuss tools that can be used in finding asymptotics for the number of homomorphisms from a certain class of bipartite graphs. Counting independent sets in bipartite graphs has received a great amount of attention, and in particular, the asymptotics for the number of independent sets in the Hamming cube was given by Sapozhenko back in 1980's using the tool now called "Sapozhenko's graph container." Recently, Jenssen and Keevash characterized homomorphisms from discrete tori using various tools including graph container and algebraic properties of the torus. Our goal is to extend this framework of counting homomorphisms to more general bipartite graphs that do not exhibit such nice algebraic structures. This is joint work with Lina Li and Gwen McKinley.
Sep 8, 2023: Yashwant Borse (Savitribai Phule Pune University, India)
Title: Decompositions of the Hypercube
Abstract: An n-dimensional hypercube Q_n is the Cartesian product of n copies of the complete graph K_2. It is an n-regular, n-connected, bipartite, bipancyclic, highly symmetric graph with 2^n vertices and has dimension n. Due to such beautiful properties, the hypercube is one of the most important interconnection networks in parallel computing. A decomposition of a graph G by a graph H is a partition of the edge set of G into the copies of H. In this talk, we discuss the decomposition of the hypercube into cycles, and into connected spanning subgraphs. The problem of the existence of a decomposition of the hypercube into Hamiltonian cycles was settled in 1990. Later on, the problem was considered for smaller cycles. The existence of a decomposition of Q_n into cycles of length k is now known for k = n, 2n, 4n, 2^t, and recently for k = n2^t under certain conditions. We talk about some of these results in detail. Also, we discuss the decomposition of the hypercube Q_{mk} into m copies of a spanning, k-regular, k-connected subgraph.
Sep 15, 2023: Holiday (Rosh Hashanah)
Sep 22, 2023: Joseph Fehribach (Worcester Polytechnic Institute)
Title: Families of Kirchhoff Graphs
Abstract: Given a set of n vectors in any vector space over the rationals, suppose that k < n are linear independent. Kirchhoff graphs are vector graphs (graphs whose edges are these vectors), whose cycles represent the dependencies of these vectors and whose vertex cuts are orthogonal to these cycles. This presentation discusses how graph tiling can generate families of Kirchhoff graphs. These families are composed of prime graphs (those having no Kirchhoff subgraphs), and composite graphs (not prime), all generated by a set of fundamental Kirchhoff graphs (smallest prime Kirchhoff graphs that can generate other prime and composite graphs for our set of vectors). This work depends on the numerical construction of Kirchhoff graphs, and two specific construction algorithms will be discussed.
Sep 29, 2023: Miklós Bóna (University of Florida)
Title: An overview of the pattern avoidance problem
Abstract: We say that a permutation p contains the shorter permutation q as a pattern if p contains |q| entries, not necessarily in consecutive positions, whose pairwise relations to each other are the same as those of the entries of q. For instance, p = 3576241 contains q =231, since the first, third and fifth entries of p relate to each other as the entries of q, namely the leftmost entry is the second smallest, the middle one is the largest, and the rightmost entry is the smallest. In the first part of this talk, we will review the early results of this fascinating and rapidly growing topic, including the celebrated Marcus-Tardos theorem from 2003. That theorem shows that for any given pattern q, the number of permutations of length n that avoid q is simply exponential, that is, there exists a constant c_q so that $S_n(q)\leq c_q^n$. In the second part, we discuss some more recent developments, such recent results on the extremely tenacious pattern 1324, the disproof of old conjectures, and several open problems.
Oct 6, 2023:
Oct 13, 2023: Prateek Kumar Vishwakarma (University of Regina, Canada)
Title: Inequalities for totally nonnegative matrices: Gantmacher--Krein, Karlin, and Laplace
Abstract: A real linear combination of products of minors which is nonnegative over all totally nonnegative (TN) matrices is called a determinantal inequality for these matrices. It is referred to as multiplicative when it compares two collections of products of minors and additive otherwise. Set theoretic operations preserving the class of TN matrices naturally translate into operations preserving determinantal inequalities in this class. We introduce index-row (and index-column) operations that act directly on all determinantal inequalities for TN matrices, and yield further inequalities for these matrices. These operations assist in revealing novel additive inequalities for TN matrices embedded in the classical identities due to Laplace [Mem. Acad. Sciences Paris 1772] and Karlin (1968). In particular, for any square TN matrix A, these derived inequalities generalize -- to every ith row of A and jth column of A -- the classical Gantmacher--Krein fluctuating inequalities (1941) for i = j = 1. Furthermore, our index-row/column operations reveal additional undiscovered fluctuating inequalities for TN matrices. The introduced index-row/column operations naturally birth an algorithm that can detect certain determinantal expressions that do not form an inequality for TN matrices. However, the algorithm completely characterizes the multiplicative inequalities comparing products of pairs of minors. Moreover, the underlying index-row/column operations add that these inequalities are offshoots of certain "complementary/higher" ones. These novel results seem very natural, and in addition thoroughly describe and enrich the classification of these multiplicative inequalities due to Fallat--Gekhtman--Johnson [Adv. Appl. Math. 2003] and later Skandera [J. Algebraic Comb. 2004] (and revisited by Rhoades--Skandera [Ann. Comb. 2005, J. Algebra 2006]). This is joint work with Shaun M. Fallat.
Oct 20, 2023: Craig Larson (Virginia Commonwealth University)
Title:
Abstract:
Oct 27, 2023: Zi-xia Song (University of Central Florida)
Title:
Abstract:
Nov 3, 2023: Stoyan Dimitrov (Rutgers University) in-person
Title:
Abstract:
Nov 10, 2023: Adam Mata (Warsaw University of Technology, Poland) in-person
Title:
Abstract:
Nov 17, 2023: Thomas Karam (Oxford University, UK)
Title:
Abstract:
Saturday Nov 18, 2023: 77th Graph Theory Day of New York (in-person)
Keynote speakers: Aihua Li (Montclair State University) and Abigail Raz (Cooper Union)
Location: New York City College of Technology
Time: 10:30 am - 4:30 pm ET
Website: https://sites.google.com/view/gtd77
Please encourage your undergraduate students to present posters in the poster session.
Nov 24, 2023: Holiday (Thanksgiving weekend)
_________________________________________________________
Previous Speakers
Spring 2023
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