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

Abstract

June 11, 2018 (Monday) at 11:45 am: Riste Skrekovski (University of Ljubljana and FIS, Slovenia)

Title: Closeness and Eccentricity Centralization Measures for Two-mode Data of Prescribed Sizes

A social network is often conveniently modeled by a graph: nodes represent individual persons and edges represent the relationships between pairs of individuals. Usually, in a social network we want to measure how central is the position of the individuals, and this is done by graph functions that are called centralities. Some widely used centrality measures are the degree centrality, the betweenness centrality, the closeness centrality, the eigenvector centrality, etc. In 1979, Freeman introduced the concept of centralization of a network with given cetrality as a measure of how central its most central node is in relation to how central all the other nodes are. Thus, from every centrality measure we obtain a new measure that enables to compere most central vertices from distinct networks, or simply just to compare the networks.

In this mathematical talk, we consider the closeness and eccentricity centralization measures on bipartite networks with fixed size partitions. We find that while there is a unique extremal configuration in the case of closeness centralization (as conjectured by Everett, Sinclair, and Dankelmann in 2004), there are multiple such configurations for eccentricity centralization. In all cases, maximizing the centrality of the central node takes precedence over minimizing the centrality of non-central nodes. If the time allows, we will mention few related problems. This is joint work with Matjaz Krnc (University of Primorska, Koper, Slovenia), Jean-Sebastien Sereni (CNRS and LORIA, Strasburg, France), Zelealem B. Yilma (Carnegie Mellon University in Qatar, Dolha, Qatar)

We have two talks on Thursday July 12 - at 11:00 am and at 1:30 pm in Room 6421.

July 12, 2018 (Thursday) at 11:00 am: Criel Merino (Instituto de Matemáticas, Universidad Nacional Autonoma de Mexico, Mexico)

Title: Counting spanning trees

Abstract: Every connected graph contains a spanning subgraph that is a tree. Counting spanning trees in labelled connected graphs is a classical subject in enumerative combinatorics and a general method to compute efficiently this graph invariant was already known since the middle of the 19th century. The main theme of the talk is a list of some well-known formulas for the number of spanning trees of families of graphs, starting from Cayley's formula (n+1)^{n-1} for complete graphs. As an accompaniment, we give some generalizations of these formulas by using different refinements of the invariant that take us to abelian groups, simplicial complexes and the Tutte polynomial.

July 12, 2018 (Thursday) at 1:30 pm: Apoorva Khare (Indian Institute of Science, Bangalore, India)

(Joint with the NY Group Theory Seminar)

Title: PolyMath14: Groups with norms

Abstract: Consider the following three properties of a general group G:

1. Algebra: G is abelian and torsion-free.
2. Analysis: G is a metric space that admits a "norm", namely, a translation-invariant metric d(.,.) satisfying: d(1,g^n) = |n| d(1,g) for all g in G and integers n.
3. Geometry: G admits a length function with "saturated" subadditivity for equal arguments: l(g^2) = 2 l(g) for all g in G.