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 Diameter-Constrained 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 D-s,t-path is a path between s and t composed of at most D edges. An edge e or vertex u are called D-irrelevant if e or u does not belong to any D-s,t-path of G. In this presentation we study the problem of efficiently detecting D-irrelevant edges and vertices and also study the computational complexity of diameter-related problems in graphs. Detection and subsequent deletion of D-irrelevant edges have been shown to be fundamental in reducing the computational effort to evaluate the Source-to-terminal Diameter-Constrained 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 NP-Hard 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 Navarro-Willems 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 two-dimensional 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:

1. Johannes Fischer, Volker Heun: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays. SIAM J. Comput. 40(2): 465-492 (2011)
2. Gerth Stølting Brodal, Pooya Davoodi, S. Srinivasa Rao: On Space Efficient Two Dimensional Range Minimum Data Structures. Algorithmica 63(4):815-830 (2012)