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.  The seminar went virtual during the pandemic.  Talks are posted on our YouTube channel @NYCombinatorics 

Fridays 12:00 pm:  1:00 pm ET (Eastern Time)

Location: 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).

Lead Organizer: Anna Pun (2024 - 2025)

Fall 2024 Talks

Zoom link for virtual talks:
https://us06web.zoom.us/j/82240946277?pwd=8S8Z1nwcktHEeFlVORujNBzSJnydpK.1

Meeting ID: 822 4094 6277
Passcode: nycs 

Room for in-person talks: Graduate Center 9116

Aug 23, 2024:  Csaba Biro (University of Louisville) (virtual)

Title: Representing interval orders
Abstract: An interval order is a poset that does not contain two incomparable chains of length 2 each. The name is motivated by the fact that these are exactly the posets that can be represented by a set of closed intervals of the real line, where disjoint intervals are comparable based on their relative locations. In this talk, we discuss some recent results on the properties of representations of interval orders. This is joint work in various collaborations with Sida Wan, Jeno Lehel, Andre Kezdy, and Caroline Boone.

Aug 30: No Talk

Sep 6, 2024: Kerry Ojakian (Bronx Community College) (in person)

Title: Burning Large p-caterpillars

Abstract: Graph Burning is a model of spread of information on a graph.  At each time step a new vertex is "burned;" also, any neighbors of already burned vertices become burned. The big open question is known as the Burning Number Conjecture: For any graph on n vertices, all the vertices can be burned in at most sqrt(n) time steps. To prove this conjecture, it suffices to prove it for trees, so we consider p-caterpillars: a tree that contains a maximal path H such that every vertex is distance at most p to H. The conjecture has been proven for 1-caterpillars and 2-caterpillars.  We prove that for any p, and sufficiently large n (depending on p) that the conjecture is true for p-caterpillars on n vertices. This is joint work with Danielle Cox and M.E. Messinger.

Sep 13, 2024: Eric Ramos (Stevens Institute of Technology) (in person)

Title: Computation of the homology groups of graph configuration spaces through quantitative representation stability

Abstract: Configuration spaces of graphs have seen an explosion of interest in recent years due to their intriguing theoretical properties, as well as their applicability to problems in physics and robotics. For instance, work of Bibby, Chan, Gaddish, and Yun has shown that the compactly supported cohomology groups of these spaces naturally appears in the study of the tropical moduli spaces of curves. Despite all of this interest, explicit computations of the homologies of these spaces are rare outside of certain special families of graphs. In this talk, we will present an approach to computing the homology groups of graph configuration spaces in certain infinite families of graphs. Our approach involves applying the principals of representation stability to reduce the computation of each family to a finite computation, which we accomplish using discrete morse theory and computer algebra. Through these computations, we come away with a number of interesting conjectures on the interplay between the combinatorics of the graph, and the behaviors of the higher homology groups of its configuration space.

Sep 20, 2024: Fan Zhou (Columbia University) (in person)

Title: Categorifying the Jacobi-Trudi identity via KLR algebras

Abstract: The Jacobi-Trudi determinant identity is a famous formula for the Schur polynomials, which are central to the study of symmetric polynomials and arise as "shadows" of simple representations of symmetric groups. A determinant can, of course, be written as an alternating sum of products of entries in the matrix; a natural question is then whether this alternating sum can be lifted, or `categorified', into a resolution such that the Euler-Frobenius characteristic of the resolution recovers this determinant identity. In other words, it is natural to wonder if this determinant identity is simply a `numerical shadow' of a deeper fact regarding modules; this type of `allegory-of-the-cave'-esque story is known as a `categorification'. In this talk we will outline a categorification of the Jacobi-Trudi determinant identity using KLR algebras. Along the way we will crucially use the interval combinatorics of Bruhat orders and the Phillip Hall theorem on Mobius functions of posets.

Sep 27, 2024: Greta Panova (University of Southern California) (in person)

Title: Computational Complexity in Algebraic Combinatorics

Abstract: Algebraic Combinatorics studies objects and quantities originating in Algebra, Representation Theory and Algebraic Geometry via combinatorial methods, finding formulas and neat interpretations. Some of its feats include the hook-length formula for the dimension of an irreducible symmetric group ($S_n$) module, or the Littlewood-Richardson rule to determine multiplicities of GL irreducibles in tensor products. Yet some natural multiplicities elude us, among them the fundamental Kronecker coefficients for the decomposition of tensor products of $S_n$ irreducibles, and the plethysm coefficients for compositions of GL modules. Answering those questions could help Geometric Complexity Theory towards establishing lower bounds for the far-reaching goal to show that P is not equal to NP. We will discuss how Computational Complexity Theory provides a theoretical framework for understanding what kind of formulas or rules we could have. As a proof of concept we show that the square of a symmetric group character could not have a combinatorial interpretation. Based on joint works with Christian Ikenmeyer and Igor Pak.

Oct 4, 2024: Holiday

Oct 11, 2024: Holiday

Oct 18, 2024: No Talk

Oct 25, 2024:  Israel Ricardo Curbelo (Kean University) (in person)

Title: On the on-line colorings of interval graphs with geometric representation

Abstract: We define an on-line coloring problem as a two-player game between Beth and Anna. The game is played in rounds. Each round, Beth presents a vertex along with all of its adjacencies. Anna, immediately and irrevocably, assigns the vertex a color that has not been assigned to any of its neighbors. The goal for Beth is to force Anna to use as many colors as possible, while the goal for Anna is to use as few colors as possible. In this talk, we focus on variants where Beth constructs interval graphs via an interval representation. In particular, we present an overview of the closely related problems restricted to unit-intervals and to proper intervals, and new strategies for Beth in these settings. This is joint work with Hannah R. Malko and Csaba Biro.

Fri Nov 8: 80th Graph Theory Day of New York
Location:  Graduate Center, 4th Floor Science Room,
Keynote Speakers:  Josh Hiller (Adelphi University) and Jinyoung Park (New York University)
Please encourage your students to present posters in the poster session.

Nov 15, 2024: Marie Kramer (Syracuse University) (in person)

Title: Graph Embeddings & Torus Obstructions
Abstract: While obstructions to embedding graphs into the plane and the real projective plane are well understood, there is no known complete list for other surfaces such as the torus or the Klein bottle. Moreover, the embeddability of planar obstructions into other surfaces has been studied: Mohar and Gagarin, Kocay, and Neilson classified such embeddings into the real projective plane and the torus, respectively. In this talk, we will discuss a similar result classifying the embeddings of the six cubic projective plane obstructions into the torus. We will show how this result helped us verify Chambers' computer assisted results regarding cubic torus obstructions with small first Betti number. Lastly, we will highlight a connection between the existence of embeddings of graphs into certain surfaces and geometric data of special torus representations found by Kennard, Wiemeler, and Wilking.

Nov 22, 2024: Rosna Paul, Graz University of Technology, Austria (virtual)

Title: A Short Primer on Graph Drawings
Abstract: In graph theory, a drawing of a graph G is a visual representation of G in the Euclidean plane where each vertex is depicted as a distinct point, and each edge is represented as a Jordan arc connecting its corresponding vertices, without passing through any other vertex. A drawing is  termed simple if any pair of edges intersect at most once-either at a common vertex or as a  proper crossing within the relative interior of the edges. When a drawing contains no crossings,  it is classified as plane. Additionally, when the Jordan arcs are restricted to straight-line segments, the drawing is known as a straight-line drawing or geometric drawing. In this talk, I will present a brief introduction to graph drawings, exploring the different classifications and properties that define this area of study. I will also highlight some of the key research questions that continue to drive progress in the field.

Nov 29, 2024: Holiday

Dec 6, 2024: Mutasim Mim (Graduate Center, CUNY)

Title: Clique complexes of strongly regular graphs and their eigenvalues
Abstract: It is known that non-isomorphic strongly regular graphs with the same parameters must be cospectral (have the same eigenvalues). In this paper, we investigate whether the spectra of higher order Laplacians associated with these graphs can distinguish them. In this direction, we study the clique complexes of strongly regular graphs, and determine the spectra of the triangle complexes of several families of strongly regular graphs including Hamming graphs and Triangular graphs. In many cases, the spectrum of the triangle complex distinguishes between strongly regular graphs with the same parameters, but we find some examples where that is not the case. This is joint work with Sebastian M. Cioaba, Krystal Guo, and Chunxu Ji.

_________________________________________________________

Previous Speakers

Spring 2024
Fall 2023
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