New York Combinatorics Seminar

Graduate Center, CUNY

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

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 Co-Organizers are Kira Adaricheva, Deepak Bal, Jonathan Cutler, Ezra Halleck, Sandra Kingan, and Kerry Ojakian.

Spring 2017 Talks

Jan 27, 2017: Kira Adaricheva (Hofstra University)

Title: Representation of convex geometries by convex shapes

Abstract: The classical example of convex geometry, a closure systems with the anti-exchange axiom, is realized by the configuration of points in a n-dimensional space and convex hull operator, such examples being called an affine convex geometry. It was proved in 2005 by K. Kashiwabara et al, that every finite convex geometry is a subgeometry in some affine geometry, for some space dimension n. In 2013 G. Czedli introduced an idea to generalize from points to circles/balls in affine representations in order to make representation exact and, possibly, to reduce the dimension of representation. In particular, it was speculated that representation could be achieved in dimension 2, i.e. on the plane. In our work we disprove this hypothesis, exhibiting a property that all convex geometries of circles on the plane possess, but which fails in some convex geometries. The result generated a number of new questions about convex geometries representation, and remarkably swift response in several follow-up papers written by others, which we will survey in the talk. This is joint work with Madina Bolat, Nazarbayev University, Kazakhstan.

Feb 10, 2017: Sandra Kingan (Brooklyn College, CUNY)

Title: Some Old Conjectures and New Directions in Graph Theory

Abstract: My nearly completed book “Graphs and Networks: From Könisgsburg to Connectomes” combines classical graph theory with network science. In this talk I will discuss some of the tough old problems of graph theory and exciting new directions that arise from the study of complex networks.

Feb 24, 2017: Pawel Pralat (Ryerson University, Toronto, Canada)

Title: Modularity of complex networks models

Abstract: Modularity is designed to measure the strength of division of a network into clusters (known also as communities). Networks with high modularity have dense connections between the vertices within clusters but sparse connections between vertices of different clusters. As a result, modularity is often used in optimization methods for detecting community structure in networks, and so it is an important graph parameter from a practical point of view. Unfortunately, many existing non-spatial models of complex networks do not generate graphs with high modularity; on the other hand, spatial models naturally create clusters. We investigate this phenomenon by considering a few examples from both sub-classes. We prove precise theoretical results for the classical model of random $d$-regular graphs as well as the preferential attachment model, and contrast these results with the ones for the spatial preferential attachment (SPA) model that is a model for complex networks in which vertices are embedded in a metric space, and each vertex has a sphere of influence whose size increases if the vertex gains an in-link, and otherwise decreases with time.

Mar 3, 2017: John T. Saccoman (Seton Hall University)

Title: On a Class of Signless Laplacian Integral Multigraphs

Abstract: Of increasing interest in spectral Graph Theory has been the study of the signless Laplacian matrix. In Laplacian Integral Multigraphs [Heinig and Saccoman, Congressus Numerantium, Vol. 212, (2012), pp. 131-143] and Laplacian Integral Multigraphs II [O'Connor and Saccoman, Congressus Numerantium, Vol. 223, (2015), pp. 175-185], multigraphs that are underlying threshold and have integral Laplacian spectra were presented. We discuss these results and present a formula for the spectra of certain multigraphs of this type. In addition, we show that a subset of these graphs are also signless Laplacian integral, and discuss avenues for further research.

May 5, 2017: Michael Tait (Carnegie Mellon University)

Title:

Abstract:


Previous Co-Organizers

Christopher Hanusa (Spring 2011 - Spring 2015)

Previous Speakers

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