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 organizers are Jonathan Cutler, Ezra Halleck, Christopher Hanusa, Sandra Kingan, and Kerry Ojakian.

Spring 2015 Talks

January 30, 2015: Sandra Kingan (Brooklyn College, CUNY)

Title: Social Network Analysis

Abstract: Social Network Analysis is a popular application of Graph Theory. In this introductory talk I will begin by giving an overview of social network analysis and its history, after which we will review vertex similarity measures and centrality measures used by social and biological scientists. Then we will look at some connectivity results that could be applicable to networks if they were more well known. This is the first of two talks. The second will be later in the semester.

February 20 and 27, 2015: Kerry Ojakian (Bronx Community College, CUNY)

Title: An exposition of the Graph Minor Theorem

Abstract: I will give a series of 2 talks, an exposition of the celebrated Graph Minor Theorem of Robertson and Seymour. This result is arguably the deepest result in graph theory, and furthermore, has shocking corollaries. It is an important theorem to understand, even if that understanding is not complete. In 2004, after a series of 20 papers, spanning decades, Robertson and Seymour proved Wagner's Conjecture, now known as the Graph Minor Theorem. Roughly speaking, the theorem provides a simple way to characterize any appropriate class of finite graphs. In the first talk (February 20th), I will give an overview of the result and its consequences. In the second talk (February 27th) I will delve into some of the technical aspects. I will attempt to make the presentations interesting to both those who are knowledgeable of the theorem and those who have yet to be so privileged.

March 13, 2015: Yared Nigussie (Columbia University)

Title: WQO theorems versus proof systems

Abstract: In 1931 Godel's Incompleteness Theorem astonished the world by showing that in any formal system of mathematics there exist unprovable finite combinatorial theorems. Since then there is a great interest in finding meaningful concrete theorems that are unprovable in an increasingly stronger formal systems. In this talk we will give a brief historical tour and specially relate it to an area of research called ``well-quasi-ordering'' finite graphs (wqo) under certain well known `quasi-order.' We will discuss some of the dramatic results found in the mid 1980's in this area and we will attempt to understand their metamathematical meanings. It is also interesting to know how much is unknown in this area.

March 27, 2015: Henning Ulfarsson (Reykjavik University, Iceland)

Title: Pattern avoiding permutations and non-crossing subgraphs of polygons

Abstract: Joint work with Christian Bean and Murray Tannock (also at Reykjavik University). We will explain a surprising connection between independent sets arising from the study of permutations avoiding the pattern 132 and the classical problem of enumerating non-crossing subgraphs in a complete graph drawn on a regular polygon. This leads to a generalization of n-gons, where some internal edges have been doubled. These can be used to count subclasses of permutations avoiding the pattern 1324, the only principal permutation class of length 4 that remains unenumerated. No prior knowledge on permutation patterns is assumed.

April 17, 2015: Jonathan Cutler (Montclair State University)

Title: A Proof of the Roller Coaster Conjecture

Abstract

May 1, 2015: Milan Bradonjic (Bell Labs, Alcatel-Lucent)

Title: Asymptotic laws for coloring sparse random geometric graphs with constant number of colors

Abstract: We study coloring of sparse random geometric graphs, in an arbitrary but constant dimension, with a constant number of colors. We show the law of large numbers, as well as the central limit theorem type results for the maximum number of nodes that can be properly colored. This object is neither scale-invariant nor smooth, so we design the tools that with the main method of subadditivity allow us to show the law of large numbers. Additionally, by proving the Lindeberg conditions, we show that the limiting distribution is Gaussian. For the constants that appear in these results, we provide the exact value in dimension one, and upper and lower bounds in higher dimensions. This is joint work with Sem Borst.

May 15, 2015: Carol Zamfirescu (Ghent University, Belgium and Technical University of Dortmund, Germany)

Title: Hypohamiltonian and Almost Hypohamiltonian Graphs

Abstract