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, Ezra Halleck, Christopher Hanusa, Sandra Kingan, and Kerry Ojakian.

Fall 2014 Talks

September 12, 2014: Yared Nigussie (Columbia University)

Title: A magic-tree theorem and its converse
Abstract

October 31, 2014: Kerry Ojakian (Bronx Community College, CUNY)

Title: Characterizing Cop-Win Graphs
Abstract: A graph is called cop-win, if the cop can force a win in the following game: First the cop places herself on a vertex of the graph. Then the robber places himself on a vertex. At this point they alternate turns. On a turn, a player can stay still or move to an adjacent vertex. The cop wins if she ever occupies the same vertex as the robber; otherwise the robber wins. In 1983, Nowakowski and Winkler characterized the cop-win graphs as those that have an "elimination ordering." From this characterization various corollaries can be derived. We devise a different characterization of cop-win graphs which yields stronger corollaries. This work is joint with David Offner.

November 21, 2014: Tony Jebara (Columbia University)

This talk is joint with the Applied Algebra Colloquium which starts at 11:00 am and meets in Room 3209.

Title: Graphical Modeling and Inference
Abstract: Graphical models and Markov random fields are fundamental tools in machine learning with broad application in areas such as computer vision, speech recognition, and computational biology. We can cast social networks like FaceBook and Epinions as large graphical models where nodes are individuals connected by friendship edges. We can also cast power networks as large graphical models where edges indicate electrical cables between transformer nodes.

There are two canonical forms of inference in graphical modeling: maximum a posteriori (MAP) inference, where the most likely configuration is returned; and marginal inference, where a probability distribution over a subset of variables is returned. Both problems are NP-hard when the graphical models have cycles and/or large tree-width. Since learning often reduces to MAP or marginal inference it is also NP-hard to learn general graphical models. How can we tractably solve these problems in practice? Heuristics like sum-product and max-product propagation often work reasonably but formal guarantees have so far been elusive. I will provide formal tractability guarantees by compiling MAP estimation and Bethe marginal inference into a classical problem in combinatorics: finding the maximum weight stable set (MWSS) in a graph. Whenever a graph is perfect, the MWSS problem is solvable in polynomial time. Example problems such as matchings, b-matchings, and submodular models are shown to give a perfect MWSS. By making connections to perfect graph theory, new graphical models are shown to compile into perfect graphs and therefore admit tractable inference. Applications include friendship link recommendation, label prediction in social networks, influence estimation in social networks, and failure prioritization of transformers in power networks.

December 12, 2014: Simon Smith (New York City College of Technology, CUNY)

Time: 11:30 - 12:30

Title: Products of permutation groups via graph theory
Abstract: I've recently discovered a new way of taking the product of two permutation groups which, for a variety of reasons, can be thought of as being as "natural" as the wreath product in its product action. The inspiration for the product comes from infinite graph theory, specifically from the structure of some infinite primitive graphs. My intention is to give a light, intuitive introduction to this product, using graphs and their automorphism groups. Some of the important applications of the product involve topological group theory, but even here it should be possible to gain an intuitive understanding using only graphs and their automorphisms.

December 12, 2014: Neveen Shlayan (SUNY Maritime College)

Time: 12:30 - 1:30

Title: Real-time Estimation of Transit Origin-Destination Patterns and Delays Using Low-Cost Ubiquitous Advanced Technologies
Abstract: The research utilizes Bluetooth technology to estimate origin- destination demands and station wait times for users of the New York City Subway system and possibly other public transit stations managed by transportation agencies in NY City such as PANYNJ among others. If the entrance and exit turnstiles at subway stations are equipped with Bluetooth receivers, it is possible to capture O-D information for some percentage of the riders with visible Bluetooth devices. The riders who have electronic devices such as most cell phones, iPods, and computers carry unique information in their devices’ Bluetooth MAC address. This information can be used anonymously to detect their origin and destination of riders by matching data collected at entrances and exits from the system. Assuming that visible Bluetooth devices are uniformly distributed among the riders, it is possible to estimate a transit O-D matrix for the entire system in terms of demand percentages. Moreover, other transaction data an be used in conjunction with the OD demand percentages generated from the BT sensor observations to estimate number of actual OD trips. It is valuable for the agency to estimate heavily used O-D pairs for scheduling and operations, as well as agency cost. The wait time estimation will utilize the same BT devices that will be deployed at specific locations by recording the time each individual BT enabled device remains at a given location. This process is relatively simpler than estimating OD demands because it does not require tracking of these BY enabled devices.


Previous Speakers

Spring 2014
Fall 2013
Spring 2013
Fall 2012
Spring 2012
Fall 2011
Spring 2011
Previous Talks hosted by Janos Pach