New York Combinatorics Seminar
Graduate Center, CUNY
Fridays 11:30 am  12:30 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, Christopher Hanusa, Sandra Kingan, and Kerry Ojakian.
Spring 2013 Talks
February 15, 2013: Yared Nigussie (Columbia University)
Title: Algorithmic aspects of finite dualities
Abstract
March 15, 2013: Simon M. Smith (New York City College of Technology, CUNY)
Title: Open problems and unsolved conjectures: symmetry breaking of infinite graphs
Abstract: Symmetry breaking involves colouring the elements of a combinatorial structure so that the resulting structure has no nontrivial symmetries. In this talk I'll give an introduction to symmetry breaking, with a particular focus on infinite graphs. I'll also discuss a number of research directions that are opening up. Along the way I'll highlight some of the interesting open questions and conjectures that are being worked upon. Many of these problems relate to very deep problems in group theory, but I'll try to make the group theory as accessible as possible.
March 29, 2013: Spring Break
April 5, 2013: Louis Petingi (College of Staten Island, CUNY)
Title: Efficient evaluation of a DiameterConstrained reliability measure for some families of graphs
Abstract: Given an undirected graph G=(V,E), two distinguished vertices s and t of G, and a diameter bound D, a Ds,tpath is a path between s and t composed of at most D edges.
An edge e or vertex u are called Dirrelevant if e or u does not belong to any Ds,tpath of G. In this presentation we study the problem of efficiently detecting Dirrelevant edges and vertices and also study the computational complexity of diameterrelated problems in graphs.
Detection and subsequent deletion of Dirrelevant edges have been shown to be fundamental in reducing the computational effort to evaluate the Sourcetoterminal DiameterConstrained reliability of a graph G, R_{s,t}(G,D), which is defined as the probability that at least a path between s and t, with at most D edges, survives after deletion of the failed edges (under the assumption that edges fail independently and nodes are perfectly reliable). Even though the computation of R_{s,t}(G,D) has been shown to be NPHard for fixed values of the diameter bound D (i.e., D is independent of the size of the graph under consideration), we show that calculation of this reliability measure can be determined in time 2^(o(D^2)) for some families of graphs, yielding an efficient determination of the reliability for small values of D.
April 26, 2013: Rishi Nath (York College, CUNY)
Title: Simultaneous Core Partitions
Abstract: Sparked by the NavarroWillems conjecture and the work of J. Anderson, the study of simultaneous core partitions has become increasingly popular over the last decade. We discuss how the subject arose, its multifarious connections with number theory, combinatorics and representation theory, recent results, and future directions.
May 3, 2012: Pooya Davoodi (Polytechnic Institute of New York University)
Title: The Encoding Complexity of Two Dimensional Range Minimum Data Structures
Abstract: On an array A[1..n] of elements from a totally ordered set, a range minimum query (RMQ) asks for the position of the minimum element in a range A[i..j]. We study the problem of encoding the ordering between the elements of A in small space, where the encoding can be used to answer every RMQ without accessing A. An encoding of optimal size 2n+o(n) bits is known for this problem [SICOMP'11]. On a twodimensional array M[1..m x 1..n], an RMQ is asked over a rectangular range M[i1..j1 x i2..j2]. It has been proved that Omega(mn log m) bits are required to encode the orderings between the elements of M [Algorithmica'12]. In this work, we prove that this lower bound is tight.
References:
 Johannes Fischer, Volker Heun: SpaceEfficient Preprocessing Schemes for Range Minimum Queries on Static Arrays. SIAM J. Comput. 40(2): 465492 (2011)
 Gerth Stølting Brodal, Pooya Davoodi, S. Srinivasa Rao: On Space Efficient Two Dimensional Range Minimum Data Structures. Algorithmica 63(4):815830 (2012)
Previous Speakers
Fall 2012
Spring 2012
Fall 2011
Spring 2011
Previous Talks hosted by Janos Pach
