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 (Carnegie Mellon University)

Title: Path and cycle decompositions of hypercube graphs
Abstract Given a subgraph H of an n-dimensional hypercube Q_n, is it possible to partition the edges of the hypercube into edge-disjoint copies of H? The answer is known in certain cases, such as when H is a path and n is odd, and for paths and cycles that are not too long relative to n when n is even. It is conjectured that a hypercube of even dimension can be decomposed into any path satisfying certain necessary divisibility conditions. This talk will summarize what is known about edge-decompositions of the hypercube, and describe some recent progress toward decomposing hypercubes of even dimension into long paths and cycles. Joint work with Maria Axenovich and Casey Tompkins

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: Quasi-polynomial-time algorithms for Independent Set and related problems in P_t-free graphs
Abstract The complexity of the Independent Set problem in P_t-free graphs, i.e., graphs that do not contain a path on t vertices as an induced subgraph, is one of the main open problems concerning algorithms for restricted graph classes. The problem is known to be polynomial-time-solvable for t <= 6. Unfortunately the proof is fine-tailored for this class of graphs and our current algorithmic toolbox seems insufficient to provide a polynomial-time algorithm for P_t-free graphs, for every fixed t. In the recent breakthrough, Gartland and Lokshtanov [FOCS 2020] gave a quasi-polynomial-time algorithm for the problem in P_t-free graphs: their algorithm runs in time n^O(log^3n), where t is assumed to be a constant. Inspired by their ideas, Pilipczuk, Pilipczuk, and Rzazewski [accepted to SOSA 2021] showed an arguably simpler algorithm with an improved running time bound of n^O(log^2 n). During the talk I will present the simplified algorithm and discuss very recent extensions of this approach to different problems, including 3-Coloring and Feedback Vertex Set. Joint work with Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk.

Nov 13, 2020: Carol Zamfirescu (Ghent University, Belgium)

Title: Mind the gap: Missing cycle lengths in the cycle spectra of polyhedral graphs
Abstract The cycle spectrum of a graph G is the set of lengths of cycles in G. In this talk, we discuss two recent conjectures of Merker on gaps in the cycle spectra of planar 3-connected graphs. We will present answers to both conjectures -- one due to the speaker, the other due to Cui and Lo -- and give an overview of the proofs.

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

Title: The threshold dimension and threshold strong dimension of a graph.
Abstract Let G be a connected graph and u,v and w vertices of G. Then w is said to resolve u and v if the distance from u to w does not equal the distance from v to w. If there is either a shortest u-w path that contains v or a shortest v-w path that contains u, then we say that w strongly resolves u and v. A set W of vertices of G is a resolving set (strong resolving set), if every pair of vertices of G is resolved (respectively, strongly resolved) by some vertex of W. A smallest resolving set (strong resolving set) of a graph is called a basis (respectively, a strong basis) and its cardinality, the metric dimension (respectively, the strong dimension) of G. The threshold dimension (respectively, threshold strong dimension) of a graph G, is the smallest metric dimension (respectively, strong dimension) among all graphs having G as a spanning subgraph. Graphs that are not spanning subgraphs of graphs with smaller metric dimension (or smaller strong dimension) are irreducible relative to the metric dimension (respectively, strong dimension). We present geometric characterizations for both the threshold dimension and threshold strong dimension of a graph and demonstrate the utility of these characterizations. We highlight some similarities and differences between these two invariants and show that they are not equal. We describe several bounds for these two invariants and discuss the existence of irreducible structures of a given order and dimension (strong dimension). [This is collaborative work of two research groups: Group 1: Lucas Mol, Matthew Murphy, Ortrud Oellermann; Group 2: Nadia Benakli, Novi Bong, Shonda Dueck, Linda Eroh, Beth Novick and Ortrud Oellermann.]

Nov 26, 2020: No talk (Thanksgiving Break)

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

Title: Refinements and symmetries for volumes of flow polytopes
Abstract Flow polytopes are an important class of polytopes in combinatorics whose lattice points and volumes have interesting properties and relations. The Chan--Robbins--Yuen (CRY) polytope is a flow polytope with normalized volume equal to the product of consecutive Catalan numbers. Zeilberger proved this by evaluating the Morris constant term identity, but no combinatorial proof is known. There is a refinement of this formula that splits the largest Catalan number into Narayana numbers, which Mészáros gave an interpretation as the volume of a collection of flow polytopes. We introduce a new refinement of the Morris identity with combinatorial interpretations both in terms of lattice points and volumes of flow polytopes. Our results generalize Mészáros's construction and a recent flow polytope interpretation of the Morris identity by Corteel--Kim--Mészáros. We prove the product formula of our refinement following the strategy of the Baldoni--Vergne proof of the Morris identity with a recurrence approach. This is joint work with William Shi.

Dec 11, 2020: Lara Pudwell (Valparaiso University)

Title: Packing in restricted permutations
Abstract Permutation Q contains permutation P as a pattern if Q has a subsequence whose digits appear in the same relative order as the digits of P. Permutations which have no copies of P are called P-avoiding permutations, and pattern-avoiding permutations have a variety of connections to fields such as computer science, algebraic geometry, and biomathematics. In this talk, instead of avoiding a pattern, we will consider the opposite question of containing as many copies of a pattern as possible. In particular, let P be a permutation pattern and let S be a set of permutations. A permutation in S is P-optimal if it contains at least as many copies of P as any other member of S of the same length. We will focus on the structure of P-optimal permutations for some well-known sets of permutations such as when S is a classical pattern class and when S is the set of alternating permutations. We will end with the case of packing 123 permutation patterns into alternating permutations, which leads to a surprising connection with electron configurations in physical chemistry.