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, 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: Monochromatic covers and partitions of (pseudo)random graphs

Abstract: Suppose the edges of a graph are colored with r colors. How many monochromatic cycles (or trees) are needed to partition (or cover) the vertex set? These types of questions have been addressed by many authors in the case where the graph is the complete graph. For example in 1991, Erdos, Gyarfas, and Pyber proved that $O(r^2\log r)$ monochromatic cycles suffice to partition the vertex set of any r-edge-colored complete graph. In this talk we will discuss some new results of this flavor in which the host graph is (pseudo)random. This is joint work with Louis DeBiasio.

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

Title: Immersion of 2-regular digraphs

Abstract: A 2-regular digraph is a directed graph with indegree and outdegree equal to 2. We define a surface embedding for this class of graphs, namely that the local rotation of edges at each vertex is in-out-in-out. Equipped with this embedding, the graph immersion operation acts as our containment operation; this is analogous to the graph minor operation for undirected graphs. In particular, it is also the case that there are finite lists of immersion minimal obstructions to embedding 2-regular digraphs on various surfaces. The complete list of minimal obstructions for the plane and the projective plane have been found, and work on the torus has been started. This is a joint work with Archdeacon, DeVos, and Mohar.

December 11, 2015: Yared Nigussie (Columbia University)

Title: Finite strucutres for graph minor ideals of bounded tree-width

Abstract: A finite structure theorem for every ‘Friedman ideals of finite trees” was found recently by extending a theorem of Robertson, Seymour and Thomas from 1993. In this talk, we show how we can further extend the theorem so that it also works for graph minor ideals of bounded tree-width. A couple of open problem about the unbounded tree-width case will be presented.

December 18, 2015: Kira Adaricheva (Nazarbayev University, Astana, Kazakhstan)

Title: Applications of a new algorithm of implicational basis retrieval in bio-medical studies

Abstract: The new algorithm of implicational basis (D-basis) retrieval was presented at this seminar in December 2013. Since then we worked with the groups of medical doctors and bioinformatics specialists to test it on the data related to survival data and treatment data of cancer patients. We present results of this on-going project.