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, 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.

Date: May 20, 2016: Avinash Dalal (University of West Florida)

Title: k-Shur Functions

Abstract: The k-Schur functions are the parameterless case of a more general family of symmetric functions over Q(t), conjectured to satisfy a k-branching formula given by weights on a poset of k-shapes. This branching of k-1-Schur functions into k-Schur functions was given by Lapointe, Lam, Morse and Shimozono. A concept of a k-(co)charge on a k-tableau was defined by Lapointe and Pinto, and they prove it is compatible with the k-shape poset for standard k-tableaux. This compatibility shows that their k-(co)charge statistics are non-negative only for standard k-tableaux. Recently, Morse introduced a manifestly positive notion of affine k-(co)charge on k-tableaux and conjectured that it matches the statistics of Lapointe and Pinto. Here we prove her conjecture and the positivity of k-(co)charge for any k-tableau follows. We also extend the relation between k-charge and k-cocharge for a standard k-tableau of Lapointe and Pinto to any k-tableau. If time permits, I will also talk about the open problems regarding k-Schur functions.