New York Combinatorics Seminar

Graduate Center, CUNY

Fridays 11:00 am - 12:00 am Room C196.06
(turn right at the security desk and enter the library, go all the way to the back and downstairs, C196.06 is at the end of the large room)

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 2016 Talks

March 18, 2016: Roman Kossak (Bronx Community College and CUNY Graduate Center )

Title: On some uses of nonstandard models in combinatorics

Abstract: Model theoretic techniques can be sometimes used to streamline combinatorial arguments. I will show how it works in a proof of a version of Ramsey's theorem. Then I will discuss a remarkable result, due to Jim Schmerl who showed that a certain open question about automorphism groups of nonstandard models of arithmetic is equivalent Hedetniemi's conjecture concerning chromatic numbers of products of finite digraphs.

April 1, 2016: Monika Heinig (Stevens Institute of Technology)

Title: Reliability models associated with the edge domination number

Abstract

April 8, 2016: Dave Offner (Westminster College)

Title: Characterizing Cop-Win Graphs and Their Properties Using a Corner Ranking Procedure

Abstract: Cops and Robber is a two-player vertex pursuit game played on graphs. Some number of cops and a robber occupy vertices of a graph, and take turns moving between adjacent vertices. If a cop ever occupies the same vertex as the robber, the robber is caught. If one cop is sufficient to catch the robber on a given graph, the graph is called cop-win, and the maximum number of moves required to catch the robber is called the capture time. In this talk we introduce a simple “corner ranking” procedure that assigns a rank to every vertex in a graph. The results of this procedure can be used to determine many properties of the graph, for example, if it is cop-win, and if so, what the capture time is. We show how corner rank can be used to describe optimal strategies for the cop and robber, and to characterize those cop-win graphs with a given number of vertices which have maximum capture time. Though cop-win graphs and their capture time have previously been characterized, in many cases corner rank gives more streamlined proofs, and allows us to extend known results.

Date: May 6, 2016: Bela Bajnok (Gettysburg College)

Title: S.A.C.^2: Some Addictive Conjectures about Sumsets in Additive Combinatorics

Abstract: The central concept in additive combinatorics is that of a sumset. In our setting, we are given a finite abelian group, and we seek subsets whose sumset possesses some desired properties. For example, we look for a subset of fixed size whose h-fold sumset (the collection of h-term sums with terms from our subset) is as small as possible; or, we look for subsets as large as possible whose h-fold sumset is not the entire group. We can also consider variations where sums must have distinct terms or when we can subtract as well as add elements. These types of questions, some of which have been answered but many have not been, provide for great sources of intrigue for mathematicians young and old alike.

Date: May 13, 2016: Christopher R. H. Hanusa (Queens College, CUNY)

Title: A q-Queens Problem

Abstract: The n-Queens Problem asks in how many ways you can place n queens on an n x n chessboard so that no two attack each other. There has been no formula for the answer to this question... until now! We develop a mathematical theory to address the more general question “In how many ways can you place q chess pieces on a polygonal chessboard so that no two pieces attack each other?” The theory is geometrical and combinatorial in nature and involves counting lattice points that avoid certain hyperplanes.


Previous Speakers

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