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. Date: May 20, 2016: Avinash Dalal (University of West Florida) Title: kShur Functions Abstract: The kSchur functions are the parameterless case of a more general family of symmetric functions over Q(t), conjectured to satisfy a kbranching formula given by weights on a poset of kshapes. This branching of k1Schur functions into kSchur functions was given by Lapointe, Lam, Morse and Shimozono. A concept of a k(co)charge on a ktableau was defined by Lapointe and Pinto, and they prove it is compatible with the kshape poset for standard ktableaux. This compatibility shows that their k(co)charge statistics are nonnegative only for standard ktableaux. Recently, Morse introduced a manifestly positive notion of affine k(co)charge on ktableaux 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 ktableau follows. We also extend the relation between kcharge and kcocharge for a standard ktableau of Lapointe and Pinto to any ktableau. If time permits, I will also talk about the open problems regarding kSchur functions.
Previous Speakers
Fall 2015
