New York Combinatorics Seminar

Graduate Center, CUNY

Fridays 11:00 am - 12:00 am Room 3308

Note the room has changed

This seminar covers a wide range of topics in combinatorics and its applications to other disciplines, especially computer science.

The CUNY Graduate Center is located at 365 Fifth Avenue (at the corner of 34th Street), New York. It can be easily approached by subway, using the B,D,F,N,Q,R, or 6 trains.

Seminar organizers are Jonathan Cutler, Ezra Halleck, Christopher Hanusa, Sandra Kingan, and Kerry Ojakian.

Fall 2015 Talks

September 18, 2015: Steve Butler (Iowa State University)

Title: Aspects of the normalized Laplacian matrix

Abstract: The eigenvalues of the normalized Laplacian matrix give information about the graph the matrix is associated with, including data on expansion and mixing. But the spectrum has some various quirks, for example they cannot detect the number of edges. We will give an introduction to the matrix and establish several properties including the construction of cospectral graphs.

October 2, 2015: Michael Yatauro (Penn State Brandywine)

Title: Component Order Connectivity and Vertex Degrees

Abstract: Given a graph G, the k-component order connectivity of G is the minimum number of vertices whose removal results in an induced subgraph for which every component has order at most k-1. For this measure of connectivity, after the removal of a set of vertices, we say the induced subgraph is in an operating state if it has at least one component containing at least k vertices. Otherwise, we say it is in a failure state. Thus, the k-component order connectivity is the cardinality of a smallest set of vertices whose removal induces a failure state. In general, determining the k-component order connectivity of a graph is NP-hard. In light of this, we present conditions on the vertex degrees of G that can be used to determine lower bounds on the k-component order connectivity of G. In addition, we discuss an algorithm for generating these conditions, and we demonstrate that the resulting theorems are best possible in a certain sense (known as best monotone).

October 23, 2015: Deepak Bal (Montclair State University)

Title: TBA


November 13, 2015: Stefan Hannie (Simon Frazer University)

Title: TBA


Previous Speakers

Spring 2015
Fall 2014
Spring 2014
Fall 2013
Spring 2013
Fall 2012
Spring 2012
Fall 2011
Spring 2011
Previous Talks hosted by Janos Pach