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:
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
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: no talk

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
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
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, Kalamassery, India)

Title: Security in Graphs and Networks
The topological structure of a network can be described by a connected graph G = (V (G), E(G)) where V(G) is a set of nodes to be connected and E(G) is a set of direct communication links between the nodes. A physical connection between the different components of a parallel system is provided by an interconnection network. Graph theoretic parameters are used to study the efficiency and reliability of an interconnection network. In the current era, security is a desirable property for the interconnection networks. A subset S of V (G) is secure when the security condition is satisfied for every subset of S. Since the whole vertex set is a secure set, there must be one secure set of minimum cardinality. The minimum cardinality of a secure set in G is called the security number of G, s(G). R. C. Brigham defined this concept in their paper in 2007. The set S is secure dominating if it is both secure and dominating. The minimum cardinality of a secure-dominating set in G is the secure domination number of G. In this talk, let us discuss these parameters in some well-known classes of graphs and networks. Please note that the concept of secure domination used in this paper is different from the concept of secure domination in graphs that was introduced by Cockayne et al in his paper ‘Protection of Graph’.

Nov 11, 2022: no talk

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

Title: The Iterative Independent Model
Abstract: Deterministic complex networks that use iterative generation algorithms have been found to more closely mirror properties found in real world networks than the standard uniform random graph models. In this talk I will introduce a new, Iterative Independent Model (IIM), significantly generalizing previously studied models. These models use ideas from Structural Balance Theory to generate edges through a notion of cloning where ``the friend of my friend is my friend'' and anticloning where ``the enemy of my enemy is my friend.'' We found that all graphs generated in this manner have common properties such as a spectral gap bounded away from 0 and low diameter and domination number. Additionally, for any fixed graph F all IIM graphs will eventually contain an induced copy of F. Together this indicates that IIM graphs share more properties, and thus better mimic, social networks than traditional uniformly randomly generated graphs. Joint work with Erin Meger.

Dec 2, 2022: No Talk

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

Title: Subdivisions of Shellable Complexes
Abstract: In geometric, algebraic, and topological combinatorics, we often study the unimodality of combinatorial generating polynomials, which in turn follows when the polynomial has real roots. Motivated by a conjecture of Brenti and Welker on the real-rootedness of the h-polynomial of the barycentric subdivision of the boundary complex of a convex polytope, we introduce a framework for proving real-rootedness of h-polynomials for subdivisions of polytopal complexes that uses a shellibility construction and the theory of polynomials with interlacing roots. We show that any shellable cubical complex admitting a stable shelling has barycentric and edgewise (when well-defined) subdivisions with real-rooted h-polynomials. Such shellings are shown to exist for well-studied families of cubical polytopes, giving a positive answer to the conjecture of Brenti and Welker in these cases.


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