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

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

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: Nadia Benakli (City Tech) Ezra Halleck (City Tech), Sandra Kingan (Brooklyn College), Joseph Malkevitch (York College), Kerry Ojakian (BCC), Mingxian Zhong (Lehman College),
Montclair State University: Deepak Bal, Jonathan Cutler
Hofstra University: Kira Adaricheva, Eric Rowland

Fall 2019 Talks

Please note the new room number: 4422

Sep 20, 2019: Kerry Ojakian (BCC, CUNY)

Title: Bounding the k-rainbow total domination number
Abstract: A k-rainbow dominating function of a graph G is the following: a function f which assigns a subset of [k] = {1,2,…, k} to each vertex of G, such that if a vertex v is assigned the empty set, then the values assigned to v's neighbors union to [k]. A k-rainbow *total* dominating function is a function f which satisfies the following additional condition: if a vertex is assigned a singleton set {i} then for some neighbor u, we have i in f(u). In either case, the weight of f is the sum of |f(v)| as v ranges over the vertices of G. For a graph G, the k-rainbow domination number is defined as the minimum weight k-rainbow dominating function for G, and the k-rainbow *total* domination number is defined as the minimum weight k-rainbow total dominating function for G. I will present bounds on the rainbow total domination number in terms of the usual domination number, the total domination number, the rainbow domination number and the rainbow total domination number. Along with a number of partial results, I will present questions and conjectures, including a Vizing-like conjecture about graph products for the rainbow total domination number.

Oct 4, 2019: Aihua Li (Montclair State University)

Title: Interlace Polynomials of Friendship Graphs and Shell Graphs
In this presentation, properties of the interlace polynomials of friendship graphs and related butterfly graphs are provided. Friendship graphs are graphs that satisfy the Friendship Theorem given by Erdos, Renyi and Sos. An application of such polynomials in analyzing the adjacency matrixes of the ground graphs is given. Another type of graph is called shell graph. Shell graphs are constructed from cycles by adding additional cords. Iterative formulas and properties for the interlace polynomials of shell graphs are given. This is joint work with Cheyenne Petzold.

Oct 18, 2019: Deepak Bal (Montclair State University)

Title: The size Ramsey number of paths
Abstract: Given a graph H, the size Ramsey number sr(H) is the minimum m such that there exists a graph G with m edges such that in every 2-coloring of the edges G, there is a monochromatic copy of H. Let P_n be the path on n vertices. To prove that sr(P_n)>m, one must show that every graph on m edges can be 2-colored such that every monochromatic path has order less than n. We show that sr(P_n) > (3.75 - o(1))n thereby improving the previous best-known lower bound of (2.5 - o(1))n due to Dudek and Pralat. We also discuss some results concerning the r-color version of the problem. This is joint work with Louis DeBiasio.

Nov 15, 2019: Erin Meger (Ryerson University)

Title: The Iterated Local Model for Social Networks
Abstract:On-line social networks such as Facebook and Twitter are often studied through friendships between users. Adversarial relationships also play an important role in the structure of these social networks. We define the Iterated Local Model (ILM) utilizing the transitive and anti-transitive generative mechanisms within social networks. These mechanisms provide a precise analogy to the adages "the enemy of my enemy is my friend," and "friends of friends are friends." Complex networks exhibit four key properties: large scale, evolution over time, power law degree distribution, and the small world property. Densification is also observed in complex networks, where the average degree of the network increases over time. Each of these properties will be discussed for the ILM. Structural properties of the graphs generated by ILM, including the hamiltonicity and the chromatic number, will also be explored.

Dec 13, 2019: Ross Berkowitz (Yale University)

Title: Permanents of Norm 1 Matrices
Abstract: The permanent of a matrix is a classical object of study with connections to computer science and combinatorics. However unlike its twin, the determinant, permanents are notoriously difficult to compute; they are known to be #P-complete. An upper bound on the permanent was given by Leonid Gurvits who observed that if a matrix A has operator norm 1, then per(A)<= 1. Additionally, Gurvits showed the only tight cases was that of permutation matrices. Subsequently, Aaronson, Hance, and Nguyen asked when the above bound was close to tight, i.e., if A is far from a permutation matrix is it possible to have $per(A)=\Omega(1)$? In this talk we answer this question by showing that if A has operator norm 1, then either A is exceptionally close to a permutation matrix, or per(A) is exponentially small. Joint work with Patrick Devlin.