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.

Fridays from Noon till 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 2022 Talks

Zoom Link for Fall 2022 Virtual Talks: https://us02web.zoom.us/j/89049084611
The link changes every semester, but password stays the same. In person talks are specified in red.

Sep 16, 2022: Janos Pach (Renyi Institute Budapest and EPFL Lausanne)

Title: How many graphs are intersection graphs of geometric objects?

Abstract: Given a collection C of n geometric objects, define their intersection graph G(C) as follows. Let the vertex set of G(C) be C and connect two elements of C by an edge if and only if they have a point in common. The total number of graphs on n labeled vertices is 2^{n choose 2}. How many of them are intersection graphs of connected arcs ("strings") in the plane? Pach and Tóth proved that the answer is 2^{(3/4+o(1)){n choose 2). If we restrict our attention to intersection graphs of strings, any pair of which intersect at most k times, for a fixed k, then the number becomes 2^{o(n^2)}. On the other hand, it was shown by Pach and Solymosi that the number of segment intersection graphs on n vertices is 2^{(4+o(1))n log n}. After giving a whirlwind tour of enumeration results and methods of this kind, we present some recent results by Jacob Fox, Andrew Suk, and the speaker.

Sep 23, 2022: Joseph Briggs (Auburn University)

Title: A plethora of rainbow conjectures
Abstract:
It takes a theorem and a conjecture to make a research area. In the world of rainbow matchings, that conjecture is 50 years old, and states that any n matchings of size n in a bipartite graph contain a rainbow matching of size n-1. Drisko's theorem is a celebrated (known) counterpart: for a rainbow matching of size n (ie just 1 larger), one needs a whopping 2n-1 matchings. What's the reason for this jump from n to 2n-1? We really don't know. At least, I don't know. And yet, it seems that any variant we try to impose on Drisko's theorem appears to lead to something interesting, beautiful, and still ripe to be proven. General graphs? Scrambling the colors? Edge weights? I hope to discuss some of these in between swooning about Drisko's theorem. This is based on joint work with Ron Aharoni.

Sep 30, 2022:

Oct 7, 2022: Fan Wei (Princeton University) In-Person

Title: Graph limits and graph homomorphism densities
Abstract: Graph limits is a recently developed powerful theory in studying large (weighted) graphs from a continuous and analytical perspective. It is particular useful when studying subgraph homomorphism density, which is closely related to graph property testing, graph parameter estimation, and many central questions in extremal combinatorics. In this talk, we will show how the perspective of graph limits helps with graph homomorphism inequalities and how to make advances in a common theme in extremal combinatorics: when is the random construction close to optimal? We will also show some hardness result for proving general theorems in graph homomorphism density inequalities.

Oct 14, 2022: Ambat Vijayakumar (Cochin University of Science and Technology, India)

Title: Split graphs with four distinct eigenvalues
Abstract:
The adjacency matrix of a connected graph G is an n × n matrix A(G) = [aij], where aij = 1 if the vertices vi and vj are adjacent and aij = 0 otherwise. The spectrum of G is {λ1, ... , λn}, where λ i 's are the eigenvalues of A(G). The adjacency matrix and eigenvalues of a connected graph have been studied intensively in literature. It is a well-known fact that a graph of diameter d has at least d+ 1 eigenvalues. Let us call a graph d-extremal if it has diameter d and exactly d + 1 eigenvalues. Such graphs have been intensively studied by various authors. A graph is split if its vertex set can be partitioned into a clique and a stable set. Such a graph has diameter at most 3. We obtain a complete classification of the connected bidegreed 3-extremal split graphs. We also show how to construct certain families of non-bidegreed 3-extremal split graphs. This is a joint work with Felix Goldberg, Steve Kirkland and Anu Varghese.

Oct 21, 2022: George Nasr (University of Oregon)

Title: Matroid Valuations and Stressed Hyperplane Relaxations
Abstract:
Ehrhart polynomials and Kazhdan-Lusztig polynomials are both examples of valuations which have recently received much attention, particularly through the lens of matroid theory. In this talk, we survey results which determine formulas for these valuations in the case of paving matroids. Specifically, we discuss a generalization of the established relaxation operation on matroids and describe how it changes a matroid’s base polytope. In doing so, we will see how this new relaxation operation helps with computing valuations, especially when we focus on computing valuations for paving matroids.

Oct 28, 2022: Justin “JD” Nir (Toronto Metropolitan University) In-Person

Title: The Benevolent Turán Graph: All graphs are Turán-good
Abstract: The generalized Turán problem captures one of the fundamental problems in extremal graph theory: how many copies of H can we fit in an n-vertex graph while avoiding a forbidden graph F? One challenge of the problem is finding good candidates for extremal examples. The exception to that rule is the solution to Turán's original question, which we now call the Turán graph. If that graph contains the most copies of H among F-free graphs, we say H is F-Turán-good. Gerbner and Palmer conjectured that any graph is Kr-Turán-good for large enough r. We confirm their conjecture.

Nov 4, 2022: Manju Menon (St Paul's College, India)

Nov 11, 2022:

Nov 18, 2022: Abigail Raz (Cooper Union) In-Person

Dec 2, 2022:

Dec 9, 2022: Magda (Max) Hlavacek (University of California, Berkeley)

_________________________________________________________

Previous Speakers

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