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 kcomponent 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 k1. 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 kcomponent order connectivity is the cardinality of a smallest set of vertices whose removal induces a failure state. In general, determining the kcomponent order connectivity of a graph is NPhard. In light of this, we present conditions on the vertex degrees of G that can be used to determine lower bounds on the kcomponent 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 redgecolored 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 2regular digraphs Abstract: A 2regular 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 inoutinout. 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 2regular 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 treewidth 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 treewidth. A couple of open problem about the unbounded treewidth case will be presented. December 18, 2015 (tentative): Kira Adaricheva (Nazarbayev University, Astana, Kazakhstan)
Previous Speakers
Spring 2015
