Graduate Center, CUNY

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

This seminar covers a wide range of topics in combinatorics and its applications.

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 Deepak Bal, Jonathan Cutler, Ezra Halleck, Sandra Kingan, Joseph Malkevitch , 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.

March 17, 2017: Vladimir Bercov (Manhattan Community College)

Title: Connected dominating sets and the number of Hadwiger

Abstract: Based on the sequential decomposition of a graph G into connected dominating sets of vertices, we introduce a new invariant h(G) that does not exceed the number of Hadwiger. The new strengthening of the Hadwiger’s conjecture is: h(G) = chi(G) for all G, where chi(G) is the chromatic number. We prove this conjecture for all G with chi(G) = 4. In the special cases of independence number alpha(G) = 2, 3 we prove some lower bounds for h(G). The Nordhaus-Gaddum inequalities for the new invariant are: h(G)h(G¯) = n(G) and h(G) + h(G¯) = 6n(G)/5.

April 22, 2017 (Saturday): Graph Theory Day 73
Organized by Ezra Halleck (City Tech), Kerry Ojakian (BCC), Louis Quintas (Pace Univ.) Announcement
Website

April 28, 2017: Apoorva Khare (Stanford University)

Title: The critical exponent: a novel graph invariant

Abstract: Given a graph G, let P_G denote the cone of positive semidefinite (psd) matrices with zeros according to G. Which powers preserve psd-ness when applied entrywise to all matrices in P_G? In recent work, joint with D. Guillot and B. Rajaratnam, we show how preserving positivity relates to the geometry of the graph G. This leads us to propose a novel graph invariant: the "critical exponent" of G. Our main result shows how this combinatorial invariant resolves the problem for all chordal graphs. We also report on progress for several families of non-chordal graphs.

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

Title: 7 theorems in extremal spectral graph theory

Abstract: Theorems in extremal graph theory ask to optimize a combinatorial invariant over a fixed family of graphs. In this talk, we discuss how to prove several theorems in this area where the graph invariant in question is a function of the eigenvalues or eigenvectors of the adjacency matrix of the graph. One result we will show in this talk is a proof of a conjecture of Boots and Royle from 1991: the planar graph of maximum spectral radius (of its adjacency matrix) is the join of an edge and a path. This is joint work with Josh Tobin.