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/89584289007
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: No Talk
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: New and old results on $\alpha$-critical graphs
Abstract: A graph G is $\alpha$-critical if the removal of any edge e yields a graph with a larger independence number; that is, if $\alpha(G-e) > \alpha(G)$. These graphs are of interest in the investigation of the independence structure of a graph, and theorems date back to the 1960s. We recount some of these - and discuss some new ones. These arose from an investigation of Deming's algorithm for identifying Konig-Egervary graphs. This is joint work with Mark Kayll.
Oct 27, 2023: Zi-xia Song (University of Central Florida)
Title: Minimizing the edges of (H_1, ..., H_r)-co-critical graphs
Abstract: Given an integer r > 0 and graphs G, H_1, ... , H_r, we write G -----> (H_1, .... , H_r) if every r-coloring of the edges of G contains a monochromatic copy of H_i in color i, for some i. A non-complete graph G is (H_1, ..., H_r)-co-critical if G --/--> (H_1, .... ,H_r), but G+e -----> (H_1, ..., H_r) for every edge e in the complement of G. Motivated by Hanson and Toft's conjecture, we study the minimum number of edges over all (H_1, ..., H_r)-co-critical graphs on n vertices. In this talk we will survey the history of (H_1, ..., H_r)-co-critical graphs and discuss the main ideas of our recent results on co-critical graphs.
Nov 3, 2023: Stoyan Dimitrov (Rutgers University) in-person
Title: Three enumerative results and their applications in Theoretical Computer Science.
Abstract: Counting questions were among the first that people asked and pursued. However, enumerative combinatorics became a separate subfield of mathematics just a few decades ago. In this talk, we will discuss three enumerative results that are easy to state (yet not to obtain), and which find applications in three of the fundamental tasks in theoretical computer science: sorting, searching and random sampling. We will conclude with an exciting open problem.
Nov 10, 2023: Adam Mata (Warsaw University of Technology, Poland) in-person
Title: On maximal sublattices in convex geometries
Abstract: A convex geometry (CG) is a finite closure system with the anti-exchange property known in combinatorics. Its dual is an antimatroid. As a lattice it may be generated by permutations on a finite set. The characterization as lattices of particular digraphs is known as well. Convex geometries are included in the broader class - join semi-distributive lattices SDv, and they include a subclass D of distributive lattices. SDv also extends a subclass B of bounded lattices well-known in universal algebra. In the nineties, a series of papers studied Frattini sublattice, which is an intersection of maximal sublattices in a given lattice, and considerable progress was done for lattices in classes D and B. But not much was known about classes CG and SDv. In this talk we show some results about maximal sublattices and Frattini sublattice in these classes. In particular, there is full description of maximal sublattices in convex geometries of convex dimension 2. These are structures dual to the class of SPS lattices, for which about 50 papers were published in the last decade, recently targeting congruence lattices. This is joint work with K. Adaricheva, S. Silberger, and A. Zamojska-Dzienio.
Nov 17, 2023: Thomas Karam (Oxford University, UK)
Title: On the expressive power of mod-p linear forms on the Boolean cube.
Abstract: Let A_1,..,A_s be a sequence of dense subsets of the Boolean cube {0,1}^n and let p be a prime. We show that if s is assumed to be superpolynomial in n then we can find distinct i,j such that the two distributions of every mod-p linear form on A_i and A_j are almost positively correlated. We also prove that if s is merely assumed to be sufficiently large independently of n then we may require the two distributions to have overlap bounded below by a positive quantity depending on p only.
Saturday Nov 18, 2023: Graph Theory Day of New York (in-person)
Keynote speakers: Aihua Li (Montclair State University), Abigail Raz (Cooper Union), and Sandra Kingan (Brooklyn College and the Graduate Center, CUNY)
Location: New York City College of Technology
Time: 10:30 am - 5:00 pm ET
Website: https://sites.google.com/view/gtd77
Please encourage your 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