New York Combinatorics Seminar
Graduate Center, CUNY
Fridays 11:00 am  12:00 am Room C196.06
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 April 8, 2016: Dave Offner (Westminster College) Title: Characterizing CopWin Graphs and Their Properties Using a Corner Ranking Procedure Abstract: Cops and Robber is a twoplayer 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 copwin, 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 copwin, 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 copwin graphs with a given number of vertices which have maximum capture time. Though copwin 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 hfold sumset (the collection of hterm sums with terms from our subset) is as small as possible; or, we look for subsets as large as possible whose hfold 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 qQueens Problem Abstract: The nQueens 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
