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 CoOrganizers 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 antiexchange axiom, is realized by the configuration of points in a ndimensional 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 followup 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 nonspatial 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 subclasses. 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 inlink, 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. 131143] and Laplacian Integral Multigraphs II [O'Connor and Saccoman, Congressus Numerantium, Vol. 223, (2015), pp. 175185], 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 NordhausGaddum 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
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 psdness 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 nonchordal 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. Previous CoOrganizers Christopher Hanusa (Spring 2011  Spring 2015)
Previous Speakers
Fall 2016
