researchseminars.org

Leslie Hogben (Iowa State University and and American Institute of Mathematics)
2020-08-28 16:00 - 17:00 UTC | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/1/
Title: Zero forcing, propagation time, and throttling on a graph (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/1/)
by Leslie Hogben (Iowa State University and and American Institute of Mathematics) as part of NY Combinatorics Seminar

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.

Sandra Kingan (Brooklyn College, CUNY)
2020-09-11 16:00 - 17:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/2/
Title: Minor preserving deletable edges in graphs (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/2/)
by Sandra Kingan (Brooklyn College, CUNY) as part of NY Combinatorics Seminar

Abstract: TBA

No Talk
2020-09-18 16:00 - 17:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/3/
by No Talk as part of NY Combinatorics Seminar

Abstract: TBA

Megan Owen (Lehman College, CUNY)
2020-09-25 16:00 - 17:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/4/
Title: Two problems on tree-based networks (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/4/)
by Megan Owen (Lehman College, CUNY) as part of NY Combinatorics Seminar

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.

Jo Ellis-Monaghan (University of Amsterdam)
2020-10-02 16:00 - 17:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/5/
Title: New Dualities From Old: Generating Geometric, Petrie, and Wilson Dualities and Trialities of Ribbon Graphs (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/5/)
by Jo Ellis-Monaghan (University of Amsterdam) as part of NY Combinatorics Seminar

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).

Jan Goedgebeur (Ghent University, Belgium)
2020-10-09 16:00 - 17:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/6/
Title: Generation algorithms for solving mathematical and chemical problems (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/6/)
by Jan Goedgebeur (Ghent University, Belgium) as part of NY Combinatorics Seminar

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).

David Offner (Carnegie Mellon University)
2020-10-16 16:00 - 17:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/7/
Title: Path and cycle decompositions of hypercube graphs (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/7/)
by David Offner (Carnegie Mellon University) as part of NY Combinatorics Seminar

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

Ambat Vijayakumar (Cochin University of Science and Technology, India)
2020-10-23 16:00 - 17:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/8/
Title: Power domination problem - A Survey (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/8/)
by Ambat Vijayakumar (Cochin University of Science and Technology, India) as part of NY Combinatorics Seminar

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.

Miodrag Iovanov (University of Iowa)
2020-10-30 16:00 - 17:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/9/
Title: On combinatorial Hopf algebras of multi-complexes (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/9/)
by Miodrag Iovanov (University of Iowa) as part of NY Combinatorics Seminar

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.

Pawel Rzazewski (Warsaw University of Technology, Poland)
2020-11-06 17:00 - 18:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/10/
Title: Quasi-polynomial-time algorithms for Independent Set and related problems in P_t-free graphs (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/10/)
by Pawel Rzazewski (Warsaw University of Technology, Poland) as part of NY Combinatorics Seminar

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 Rzążewski [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.

Ortrud Oellermann (University of Winnipeg, Canada)
2020-11-20 17:00 - 18:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/11/
by Ortrud Oellermann (University of Winnipeg, Canada) as part of NY Combinatorics Seminar

Abstract: TBA

Alejandro Morales (University of Massachusetts, Amherst)
2020-12-04 17:00 - 18:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/12/
by Alejandro Morales (University of Massachusetts, Amherst) as part of NY Combinatorics Seminar

Abstract: TBA

Lara Pudwell (Valparaiso University)
2020-12-11 17:00 - 18:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/13/
by Lara Pudwell (Valparaiso University) as part of NY Combinatorics Seminar

Abstract: TBA

Aparna Lakshmanan S. (Cochin University of Science and Technology, India)
2021-09-03 16:00 - 17:00 | https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/14/
Title: Graph Labeling Problems: From Leech Trees to Leech Graphs (https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/14/)
by Aparna Lakshmanan S. (Cochin University of Science and Technology, India) as part of NY Combinatorics Seminar

Abstract
A graph labeling is a function with some specific properties which assigns values to vertices, edges, or both. Graceful labeling, edge graceful labeling, and harmonic labeling are some of the well know graph labelings. In this talk, I will focus on a special kind of edge labeling called Leech labeling, introduced by John Leech in 1975. Let T be a tree of order n. For any edge labeling f from the edge set E to the natural numbers, the weight of a path P is the sum of the labels of the edges of P and is denoted by w(P). If the weights of the $^nC_2$ paths in T are exactly 1, 2,...,$^nC_2$, then f is called a Leech labeling and a tree which admits a Leech labeling is called a Leech tree. I will discuss some known results in Leech labeling, a new concept called Leech index, and the possibility of extending Leech labeling to general graphs. Some Leech related labeling will also be discussed. This is joint work with S. Arumugam and Seema Varghese.
