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 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: TBA

March 1 or 8 (tentative), 2015: Milan Bradonjic (Alcatel-Lucent)

Title: TBA

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

Title: Hypohamiltonian and Almost Hypohamiltonian Graphs
Abstract: A graph is hypohamiltonian if it is not hamiltonian but, when omitting an arbitrary vertex, it becomes hamiltonian. A problem of Sousselier from 1963 initiated the study of these graphs. The smallest hypohamiltonian graph is the famous Petersen graph on 10 vertices. Among the work concerning hypohamiltonian graphs, Chv\'{a}tal asked in 1973 whether there exist planar hypohamiltonian graphs, while Gr\"{u}nbaum conjectured that these graphs do not exist. An infinite family of such graphs was subsequently found by Thomassen, the smallest among them having order 105. In the past four decades smaller and smaller planar hypohamiltonian graphs have been found. These record-holders will be the main focus of the first part of the talk. In the second part, we present Grinberg's Criterion in the context of planar hypohamiltonian graphs and give two strengthenings of a theorem of Araya and Wiener. (One of these strengthenings is joint work with Jooyandeh, McKay, \"{O}sterg{\aa}rd, and Pettersson.) For the final part of the presentation, we call a graph G almost hypohamiltonian if G is non-hamiltonian, there exists a vertex w such that G-w is non-hamiltonian, and for any vertex v not equal to w the graph G - v is hamiltonian. We discuss connections between hypohamiltonian and almost hypohamiltonian graphs and present---motivated by an old question of Thomassen---a 4-connected almost hypohamiltonian graph.

Previous Speakers

Fall 2014
Spring 2014
Fall 2013
Spring 2013
Fall 2012
Spring 2012
Fall 2011
Spring 2011
Previous Talks hosted by Janos Pach