New York Combinatorics Seminar

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

Spring 2018 Talks

Feb 16, 2018: Adam Sheffer (Baruch College, CUNY)

Title: Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique

Abstract: We will discuss the maximum number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours, and as simple polygonizations) that can be embedded over a set of N points in the plane. We derive an improved upper bound for this number by relying on Kasteleyn's linear algebra technique.

More specifically, we bound the ratio between the number of spanning cycles and perfect matchings that can be embedded over a point set and the number of triangulations that can be embedded over it. The respective bounds are O(1.8181^N) for cycles and O(1.1067^N) for matchings. These imply a new upper bound of O(54.543^N) on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of N points in the plane.

Mar 2, 2018: Zajj Daugherty (City College, CUNY)

Title: Quasisymmetric power sums

Abstract: The ring of quasisymmetric functions QSym is a beautiful generalization of the classical ring of symmetric functions Sym, with many familiar bases having natural analogues. In particular, power sum symmetric functions play an important role in Sym—they satisfy many elegant combinatorial identities, and are instrumental in defining powerful inner products and homomorphisms on Sym. In this talk, I will discuss recent work building the corresponding quasisymmetric versions, and illustrate some of the parallel structure arising there. This is joint with with Cristina Ballantine, Angela Hicks, Sarah Mason, and Elizabeth Niese.

Mar 16, 2018: Brian Hopkins (Saint Peter's University)

Title: Fair Division and the Symmetric Group

Abstract: Permutations are a helpful tool for the fair division situation of two players splitting a collection of indivisible items. We will survey optimal selection procedures, which depend on what knowledge players have of each other's preferences. Various concepts from algebraic combinatorics can be applied here, including Young tableaux, Catalan numbers, and the weak Bruhat orders. This is a field with many open questions and opportunities for students.

Mar 23, 2018: Louis Quintas (Pace University)

Title: Some Random Graph Processes

Abstract: Random processes are defined on states that are graphs with movements among these graphs achieved via one-edge transformations. These processes are of interest because of their applications in chemistry, biology, and sociology and the variety of problems that come up in their study. These problems range from those that can entice students to study mathematics to questions that are current unsolved problems. Simple examples will be used to illustrate the concepts discussed.

April 14, 2018: Graph Theory Day 75 at Brooklyn College

May 4, 2018: Corina Calinescu (City Tech, CUNY)

Title: Combinatorial aspects of representations of vertex operator algebras

Abstract: The theory of vertex operator algebras provides constructions of standard modules and principal subspaces of these modules, for affine Lie algebras. These constructions have been studied in conjunction with combinatorial identities, such as the Rogers-Ramanujan identities. In this talk we discuss algebraic and combinatorial properties of principal subspaces of certain standard modules for the twisted affine Lie algebra A_2^{(2)}. This is joint work with M. Penn and C. Sadowski.

May 11, 2018: Aihua Li (Montclair State University)

Title: Zero divisor graphs of upper triangular matrix rings


July 13, 2018: Criel Merino (Instituto de Matemáticas, U.N.A.M., Mexico)

Title: Some heterochromatic theorems for matroids

Abstract: The anti-Ramsey number of Erdos, Simonovits and Sos from 1973 has become a classic invariant in Graph Theory. To extend this invariant to Matroid Theory, we use the heterochromatic number hc(H) of a non-empty hypergraph H. The heterochromatic number of H is the smallest integer k such that for every colouring of the vertices of H with exactly k colours, there is a totally multicoloured hyperedge of H.

Given a matroid M, there are several hypergraphs over the ground set of M we can consider, for example, C(M), whose hyperedges are the circuits of M, or B(M), whose hyperedges are the bases of M. We determine hc(C(M)) for general matroids and characterize the matroids with the property that hc(B(M)) equals the rank of the matroid. We also consider the case when the hyperedges are the Hamiltonian circuits of the matroid. Finally, we extend the known result about the anti-Ramsey number of 3-cycles in complete graphs to the heterochromatic number of 3-circuits in projective geometries over finite fields, and we propose a problem very similar to the famous problem on the anti-Ramsey number of the p-cycles.

Previous Co-Organizers

Christopher Hanusa (Spring 2011 - Spring 2015)

Previous Speakers

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