New York Combinatorics Seminar

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

Fridays Noon - 1:00 pm (Online)

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 2020 Talks

The zoom link is https://us02web.zoom.us/j/82681226374
Email any one of the co-organizers for the password

August 28, 2020: Leslie Hogben (Iowa State University and and American Institute of Mathematics)

Title: Zero forcing, propagation time, and throttling on a graph
Abstract: Zero forcing is an iterative process that repeatedly applies a color change rule to color blue all the vertices of a (simple) graph G, and the minimum number of initially blue vertices needed to do so is the zero forcing number, Z(G). The zero forcing number arose as an upper bound for the maximum multiplicity of an eigenvalue of matrices having off-diagonal nonzero pattern described by the edges of the graph and in other applications. Variants for positive semidefinite matrices and skew symmetric matrices described by G have also been studied. In addition to determining the zero forcing number, the propagation time (number of rounds needed to color all vertices blue), and throttling (which minimizes a combination of resources used to accomplish a task and time needed to accomplish it), are studied. This talk will give an overview of these related areas.
Slides

Sep 4, 2020: Ananya Christman (Middlebury College)

Title: Maximizing Revenue for Online Dial a Ride
Abstract: In the Online Dial-a-Ride problem (OLDARP) a server (driver) receives requests for rides where each request has a source and destination. Since the problem is online, the requests arrive over time and the earliest a request may be served is at its arrival time. We consider a variant of this problem where each request also has a priority, which represents the importance of the request, and there is a time limit within with requests must be served; the goal is to serve requests within the time limit so as to maximize the total priority. There are many real world applications of OLDARP related to the delivery of passengers and goods. In this talk, I will first discuss competitive analysis, the standard framework for analyzing online algorithms. I will then present an algorithm for OLDARP and analyze its performance using competitive analysis, Specifically, I will show that our algorithm is 5-competitive, which means that it is guaranteed to earn at least 1/5 of the priority earned by an optimal offline algorithm.
Slides

Sep 11, 2020: Sandra Kingan (Brooklyn College, CUNY)

Title: Minor preserving deletable edges in graphs
Abstract: A 3-connected graph is minimally 3-connected if removal of any edge destroys 3-connectivity. Halin proved that if G is a minimally 3-connected graph with n > 7 vertices, then the number of edges is at most 3n-9. We extend this result to a larger class of graphs. Suppose G and H are simple 3-connected graphs and G has a proper H-minor. We say G is H-critical if removal of any edge either destroys 3-connectivity or the H-minor. We will prove that if G is H-critical, then one of three possibilities must occur: G/f is H-critical for some edge f; G/f\e is H-critical for some pair of edges e, f incident to a vertex of degree 3; or G-w is H-critical for some degree 3 vertex w. Moreover, if G is H-critical, then |E(G)| is at most |E(H)|+3[|V(G|)-|V(H)|]. This is joint work with Joao Costalonga.
Slides

Sep 18, 2020: No talk (Rosh Hashanah)

Sep 25, 2020: Megan Owen (Lehman College, CUNY)

Title: Two problems on tree-based networks
Abstract When DNA is only passed from parents to offspring, evolutionary histories can be modelled by a phylogenetic tree. However, for some organisms, like bacteria, the evolutionary process is more complex, and their evolutionary history should be modelled with a directed acyclic graph (DAG), or phylogenetic network. We study two problems on tree-based networks, which are a sub-class of phylogenetic networks built by adding arcs only between edges of a base tree. Tree-based networks were defined by Francis and Steel to answer the question: how tree-like is evolution? Francis and Steel showed that determining if a network is tree-based can be decided in polynomial time via a reduction to 2SAT. We show that it is NP-hard to determine if a network is based on a specific tree by reduction from 3-Dimensional Matching (3DM). We also show that a maximum tree covering a phylogenetic network can be found in polynomial time by reducing the problem to a minimum-cost maximum-flow problem. This is joint work with Katherine St. John (Hunter College) and our Research Experience for Undergraduates (REU) students from Fall 2015 and Fall 2017.

Oct 2, 2020: Jo Ellis-Monaghan (University of Amsterdam, Netherlands)

Title: New Dualities From Old: Generating Geometric, Petrie, and Wilson Dualities and Trialities of Ribbon Graphs
Abstract We develop tools to identify and generate new surface embeddings of graphs with various forms of self-duality including geometric duality, Petrie duality, Wilson duality, and both forms of triality (which is like duality, but of order three instead of two). Previous work typically focused on regular maps (special, highly symmetric, embedded graphs), but the methods presented here apply to general embedded graphs. In contrast to Wilson’s very large self-trial map of type {9,9}_9 we show that there are self-trial graphs on as few as three edges. We reduce the search for graphs with some form of self-duality or self-triality to the study of one-vertex ribbon graphs. Our results include a fast algorithm that will find all graphs with any of the various forms of self-duality or self-triality in the orbit of a graph that is isomorphic to any twisted dual of itself. This is joint work with Lowell Abrams (George Washington University).

Oct 9, 2020: Jan Goedgebeur (Ghent University, Belgium)

Title: Generation algorithms for solving mathematical and chemical problems
Abstract Computers are often used in combinatorics to determine if combinatorial objects with given structural or extremal properties exist as these existence problems are often too complex to solve by hand. This is done by designing and implementing generation algorithms which construct combinatorial objects from a given class (typically avoiding the generation of isomorphic copies) and analysing the resulting graphs.

In this talk we will give an introduction to the exhaustive isomorphism-free generation of graphs. We will also give concrete examples of how this has helped to gain new insights and solve problems in mathematics and chemistry.

Applications in mathematics include the generation of cubic graphs and snarks. We will present a new algorithm for the efficient generation of all non-isomorphic cubic graphs and show how this algorithm can be extended to generate snarks efficiently. A snark is a cyclically 4-edge-connected cubic graph with chromatic index 4. Snarks are of interest since for a lot of conjectures it can be proven that if the conjecture is false, the smallest possible counterexamples will be snarks. Our algorithm enabled us to generate all snarks up to 36 vertices, which was impossible with previous methods. This new list of snarks allowed us to find counterexamples to several published open conjectures.

An application of graph enumeration in chemistry is the generation of the Nobel Prize winning fullerenes (cubic plane graphs where all faces are pentagons or hexagons). We will sketch a new algorithm for the generation of all non-isomorphic fullerenes. Our implementation of this algorithm allowed us to generate all fullerenes up to 400 vertices, which enabled us to prove that the smallest counterexample to the spiral conjecture has 380 vertices. This talk is based on joint work with Gunnar Brinkmann (Ghent University) and Brendan McKay (Australian National University).

Oct 16, 2020: David Offner

Title:
Abstract

Oct 23, 2020: Ambat Vijayakumar (Cochin University of Science and Technology, India)

Title: Power domination problem - A Survey
Abstract The notion of power domination problem in graphs is motivated by the problem of placing Phasor Measurement Units (PMU) in an electric power system. This problem is viewed as a graph theoretic problem by Haynes et al. in 2002. The power domination problem in graphs consists of finding a minimum set of vertices S that monitors the entire graph following the two "monitoring rules" - domination and propagation rules. The domination rule allows a vertex v in S to monitor itself and all its neighbours. After applying the domination rule on every vertex of S, if a monitored vertex u has all its neighbours monitored except one neighbour w, then the propagation rule permits the vertex u to moniotor w. If every vertex is monitored after the repeated application of the propagation rule, we call S a power dominating set (PDS) of G. The minimum cardinality of a PDS of G is called the power domination number of the graph. Power domination can be viewed as a variation of domination in which there is an additional propagational behaviour of monitored vertices. Later in 2012, as a generalization of domination and power domination, Chang et al. introduced the notion of k-power domination by adding the possibility of propagating up to k vertices. In this talk, we shall give a short survey on the power domination problem in graphs, including the recent works of Seema Varghese and Seethu Varghese.

Oct 30, 2020: Miodrag Iovanov (University of Iowa)

Title: On combinatorial Hopf algebras of multi-complexes
Abstract A fruitful idea in combinatorics is to consider the totality of objects of a certain type, and encode natural operations on these objects in operations of some algebra with coefficients in a field of characteristic 0. We introduce a general class of combinatorial objects, which we call multi-complexes, which simultaneously generalizes graphs, multigraphs, hypergraphs and simplicial and delta complexes. We introduce a natural algebra of multi-complexes which is defined as the algebra which has a formal basis C of all isomorphism types of multi-complexes, and multiplication is to take the disjoint union. This is a Hopf algebra with an operation encoding the dissasembly information for such objects, and extends and generalizes the Hopf algebra of graphs. Such Hopf algebras are connected, graded commutative and cocommutative, and by general results of Cartier-Kostant-Milnor-Moore, are just a polynomial algebra. However, it comes with additional structure which encodes combinatorial information, and the main goal is to describe its structure in a way relating to combinatorics. Such structures have been of high interest in literature, both intrinsically and due to applications to combinatorial problems.

We give a solution to the problem in this generality and find an explicit basis B of the space of primitives, and which is of combinatorial relevance: it is such that each multi-complex is a polynomial with non-negative integer coefficients of the elements of B, and each element of B is a polynomial with integer coefficients in C. The coefficients appearing in all these polynomials are, up to signs, numbers counting multiplicities of sub-multi-complexes in a multi-complex. Using this, we also solve the antipode formula problem, and find the cancellation and grouping free formula for the antipode. Such formulas are usually very difficult to obtain, and constitute a main question for such algebras.

The main method is to use certain Mobius type formulas for posets of sub-objects of multi-complexes. As examples, we will explicitly illustrate how our results specialize to the formulas for graphs and simplicial complexes, or how they specialize to results in all of the above mentioned particular cases. Time permitting, I will show relations to applications of these results to the graph reconstruction conjectures, and rederiving some results in the literature on these questions.

Nov 6, 2020: Pawel Rzazewski (Warsaw University of Technology, Poland)

Title:
Abstract

Nov 20, 2020: Ortrud Oellermann (University of Winnipeg, Canada)

Title:
Abstract

Nov 26, 2020: No talk (Thanksgiving Break)

Dec 4, 2020: Alejandro Morales (University of Massachusetts, Amherst)

Title:
Abstract

Dec 11, 2020: Lara Pudwell (Valparaiso University)

Title:
Abstract Title:
Abstract


Previous Co-Organizers

Christopher Hanusa (Spring 2011 - Spring 2015)

Previous Speakers

Spring 2020
Fall 2019
Spring 2019
Fall 2018
Spring and Summer 2018
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