Sponsored by the Graduate Center's Math Department and Computer Science Department

Fridays 11:45 am - 12:45 am in Room 4419

This seminar covers a wide range of topics in combinatorics and its applications.

The CUNY Graduate Center is located at 365 Fifth Avenue (at the corner of 34th Street), New York. It can be easily reached by subway using the B,D,F,N,Q,R, or 6 train.

Seminar Co-Organizers:
CUNY: Ezra Halleck (City Tech), Sandra Kingan (Brooklyn College), Joseph Malkevitch (York College), Kerry Ojakian (BCC)
Montclair State University: Deepak Bal, Jonathan Cutler
Hofstra University: Kira Adaricheva

Fall 2017 Talks

Sep 8, 2017: Kate Moore (Dartmouth College)

Title: Permutations in Time Series and Dynamical Systems

Abstract: Given a time series, we can extract a collection of permutations of a fixed length by sliding a window across our data and recording the relative order of the values in the window. It is known that distribution of permutations that appear conveys information about the complexity of the time series; one commonly studied measure is permutation entropy. Interestingly, in the specific case when a time series is defined by iterating a piecewise monotone map of the interval, there are forbidden permutations. Moreover, the number of allowed permutations encodes the system's topological entropy, a measure of complexity that is itself closely related to the permutation structure of periodic points.

Using permutation-based measures of entropy in time series analysis as motivation, I will talk about some interesting problems that arise at this intersection of combinatorics, dynamics and time series analysis.

Oct 6, 2017: Andy Wilson (University of Pennsylvania)

Title: Lattice paths inside shapes

Abstract: Counting lattice paths inside two-dimensional shapes is one of the most classical problems in combinatorics. In this talk, I will explain how adding wrinkles to this problem, such as decorating or labeling the lattice paths, yields surprising connections between combinatorics and areas such as knot theory and symmetric function theory. Perhaps the most recent example of this phenomenon is Carlsson and Mellit's proof of the Shuffle Conjecture, a longstanding conjecture in the theory of Macdonald polynomials. I will discuss this result along with other similar results and conjectures.

Oct 20, 2017: Zoran Sunic (Hofstra University)
(rescheduled from Sep 29 since CUNY is closed that day)

Title: Biased Infinity Laplacian Boundary Problem on finite graphs

Abstract: We provide an algorithm, running in polynomial time in the number of vertices, computing the unique solution to the Biased Infinity Laplacian Boundary Problem on finite graphs.

The problem is, on the one hand, motivated by problems in auction theory, and on the other, it forms a basis for a numerical method for certain partial differential equations. We will discuss neither of these in depth. The following probabilistic/graph theoretic interpretation suffices for our purposes.

Let G be a finite graph with boundary B (any subset of vertices) and boundary condition g: B -> R (any real-valued function defined on the boundary). We may think of g as the pay-off function for a random-turn two-player zero-sum game played on G as follows. In the beginning a token is placed at a non-boundary vertex. At every step one of the players randomly (decided by a biased coin) gets the right to move and then chooses (not randomly!) a neighboring vertex to which the token is moved. The game ends when the token reaches a boundary vertex, say b, at which point Player I wins the amount g(b) from Player II.

The solution p to the BILBP is the value of the game, i.e., function p: V(G) -> R such that, for every vertex v in V(G), p(v) is the expected pay-off for Player I under optimal strategy by both players when the game starts with the token at v.

The algorithm is based on an adjusted (biased) notion of a slope of a function on a path in a graph.

This is a joint work with Yuval Peres (Microsoft Research).

Oct 21, 2017: Discrete Math Day Fall 2017 at Queens College

Oct 27, 2017: Reuven Hodges (Northeastern University)

Title: A closed non-iterative formula for straightening fillings of Young diagrams

Abstract: Young diagrams are fundamental combinatorial objects in representation theory and algebraic geometry. Many constructions that rely on these objects depend on variations of a straightening process, due to Alfred Young, that expresses a filling of a Young diagram as a sum of semistandard tableaux subject to certain relations. It has been a long-standing open problem to give a non-iterative, closed formula for this straightening process.

In this talk I will give such a formula, as well as a simple combinatorial description of the coefficients that arise. Moreover, an interpretation of these coefficients in terms of paths in a directed graph will be explored. I will end by discussing a surprising application of this formula towards finding multiplicities of irreducible representations in certain plethysms.

Nov 11, 2017: Graph Theory Day 74 at Pace University

Dec 8, 2017: Kerry Ojakian (BCC, CUNY)

Title: Extremal cop-win graphs

Abstract: The game of cops and robber is a two player game, played on a graph, between a cop and a robber. First the cop chooses a vertex, then the robber chooses a vertex; then play alternates. On a turn, a player may move to an adjacent vertex or remain still. A graph is cop-win if the cop can guarantee a win. For a cop-win graph, the capture time is the number of moves required by one cop to catch the robber. We consider graphs that are extremal (or almost extremal) with respect to capture time, i.e. their capture time is as large as possible relative to their order. We reprove an old result characterizing such extremal graphs (our proof avoids the use of a computer search) and prove a new result, characterizing almost extremal graphs. Our new approach involves associating graphs to vectors (i.e. finite lists of integers) and then partially determining which vectors can be realized by some graph. We leave fully characterizing these vectors as an open question. This is joint work with David Offner.

Dec 22, 2017: Eric Rowland (Hofstra University)

Title: Binomial coefficients and k-regular sequences

Abstract: Sequences satisfying linear recurrences with constant coefficients are a staple of combinatorics. The nth term s(n) of such a sequence is a linear combination of terms s(m) for integers m that are close to n in absolute value. In 1992 Allouche and Shallit introduced the class of k-regular sequences, in which s(n) is a linear combination of s(m) for integers m that are close to n in base k. Like its classical counterpart, this class of sequences has significant descriptive power. We discuss a recent appearance of p-regular sequences in the enumeration of binomial coefficients with respect to the highest power of p dividing each.