BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Leslie Hogben (Iowa State University and and American Institute of
  Mathematics)
DTSTART:20200828T160000Z
DTEND:20200828T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/1
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/1/">Zero forcing\, propagation time\, and throttling on a 
 graph</a>\nby Leslie Hogben (Iowa State University and and American Instit
 ute of Mathematics) as part of NY Combinatorics Seminar\n\n\nAbstract\nZer
 o forcing is an iterative process that repeatedly applies a color change r
 ule 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 num
 ber\, Z(G). The zero forcing number arose as an upper bound for the maximu
 m multiplicity of an eigenvalue of matrices having off-diagonal nonzero pa
 ttern described by the edges of the graph and in other applications. Varia
 nts for positive semidefinite matrices and skew symmetric matrices describ
 ed by G have also been studied. In addition to determining the zero forcin
 g number\, the propagation time (number of rounds needed to color all vert
 ices blue)\, and throttling (which minimizes a combination of resources us
 ed to accomplish a task and time needed to accomplish it)\, are studied. T
 his talk will give an overview of these related areas.\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sandra Kingan (Brooklyn College\, CUNY)
DTSTART:20200911T160000Z
DTEND:20200911T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/2
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/2/">Minor preserving deletable edges in graphs</a>\nby San
 dra Kingan (Brooklyn College\, CUNY) as part of NY Combinatorics Seminar\n
 \nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:No Talk
DTSTART:20200918T160000Z
DTEND:20200918T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/3
DESCRIPTION:by No Talk as part of NY Combinatorics Seminar\n\nAbstract: TB
 A\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Megan Owen (Lehman College\, CUNY)
DTSTART:20200925T160000Z
DTEND:20200925T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/4
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/4/">Two problems on tree-based networks</a>\nby Megan Owen
  (Lehman College\, CUNY) as part of NY Combinatorics Seminar\n\n\nAbstract
 \nWhen DNA is only passed from parents to offspring\, evolutionary histori
 es can be modelled by a phylogenetic tree. However\, for some organisms\, 
 like bacteria\, the evolutionary process is more complex\, and their evolu
 tionary history should be modelled with a directed acyclic graph (DAG)\, o
 r phylogenetic network. We study two problems on tree-based networks\, whi
 ch are a sub-class of phylogenetic networks built by adding arcs only betw
 een 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 Stee
 l showed that determining if a network is tree-based can be decided in pol
 ynomial time via a reduction to 2SAT. We show that it is NP-hard to determ
 ine if a network is based on a specific tree by reduction from 3-Dimension
 al Matching (3DM). We also show that a maximum tree covering a phylogeneti
 c network can be found in polynomial time by reducing the problem to a min
 imum-cost maximum-flow problem. This is joint work with Katherine St. John
  (Hunter College) and our Research Experience for Undergraduates (REU) stu
 dents from Fall 2015 and Fall 2017.\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jo Ellis-Monaghan (University of Amsterdam)
DTSTART:20201002T160000Z
DTEND:20201002T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/5
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/5/">New Dualities From Old: Generating Geometric\, Petrie\
 , and Wilson Dualities and Trialities of Ribbon Graphs</a>\nby Jo Ellis-Mo
 naghan (University of Amsterdam) as part of NY Combinatorics Seminar\n\n\n
 Abstract\nWe 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 l
 ike duality\, but of order three instead of two). Previous work typically 
 focused on regular maps (special\, highly symmetric\, embedded graphs)\, b
 ut the methods presented here apply to general embedded graphs. In contras
 t to Wilson's very large self-trial map of type {9\,9}_9 we show that ther
 e 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 on
 e-vertex ribbon graphs. Our results include a fast algorithm that will fin
 d all graphs with any of the various forms of self-duality or self-trialit
 y 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).\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Goedgebeur (Ghent University\, Belgium)
DTSTART:20201009T160000Z
DTEND:20201009T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/6
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/6/">Generation algorithms for solving mathematical and che
 mical problems</a>\nby Jan Goedgebeur (Ghent University\, Belgium) as part
  of NY Combinatorics Seminar\n\n\nAbstract\nComputers are often used in co
 mbinatorics to determine if combinatorial objects with given structural or
  extremal properties exist as these existence problems are often too compl
 ex to solve by hand. This is done by designing and implementing generation
  algorithms which construct combinatorial objects from a given class (typi
 cally avoiding the generation of isomorphic copies) and analysing the resu
 lting graphs.\n\nIn this talk we will give an introduction to the exhausti
 ve isomorphism-free generation of graphs. We will also give concrete examp
 les of how this has helped to gain new insights and solve problems in math
 ematics and chemistry.\n\nApplications in mathematics include the generati
 on of cubic graphs and snarks. We will present a new algorithm for the eff
 icient generation of all non-isomorphic cubic graphs and show how this alg
 orithm can be extended to generate snarks efficiently. A snark is a cyclic
 ally 4-edge-connected cubic graph with chromatic index 4. Snarks are of in
 terest since for a lot of conjectures it can be proven that if the conject
 ure is false\, the smallest possible counterexamples will be snarks. Our a
 lgorithm enabled us to generate all snarks up to 36 vertices\, which was i
 mpossible with previous methods. This new list of snarks allowed us to fin
 d counterexamples to several published open conjectures.\n\nAn application
  of graph enumeration in chemistry is the generation of the Nobel Prize wi
 nning fullerenes (cubic plane graphs where all faces are pentagons or hexa
 gons). We will sketch a new algorithm for the generation of all non-isomor
 phic fullerenes. Our implementation of this algorithm allowed us to genera
 te all fullerenes up to 400 vertices\, which enabled us to prove that the 
 smallest counterexample to the spiral conjecture has 380 vertices.\n\nThis
  talk is based on joint work with Gunnar Brinkmann (Ghent University) and 
 Brendan McKay (Australian National University).\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Offner (Carnegie Mellon University)
DTSTART:20201016T160000Z
DTEND:20201016T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/7
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/7/">Path and cycle decompositions of hypercube graphs</a>\
 nby David Offner (Carnegie Mellon University) as part of NY Combinatorics 
 Seminar\n\n\nAbstract\nGiven a subgraph H of an n-dimensional hypercube Q_
 n\, is it possible to partition the edges of the hypercube into edge-disjo
 int 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 relat
 ive to n when n is even. It is conjectured that a hypercube of even dimens
 ion can be decomposed into any path satisfying certain necessary divisibil
 ity conditions. This talk will summarize what is known about edge-decompos
 itions of the hypercube\, and describe some recent progress toward decompo
 sing hypercubes of even dimension into long paths and cycles. Joint work w
 ith Maria Axenovich and Casey Tompkins\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ambat Vijayakumar (Cochin University of Science and Technology\, I
 ndia)
DTSTART:20201023T160000Z
DTEND:20201023T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/8
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/8/">Power domination problem - A Survey</a>\nby Ambat Vija
 yakumar (Cochin University of Science and Technology\, India) as part of N
 Y Combinatorics Seminar\n\n\nAbstract\nThe notion of power domination prob
 lem in graphs is motivated by the problem of placing Phasor Measurement Un
 its (PMU) in an electric power system. This problem is viewed as a graph t
 heoretic 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 propaga
 tion rules. The domination rule allows a vertex v in S to monitor itself a
 nd 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 prop
 agation rule\, we call S a power dominating set (PDS) of G. The minimum ca
 rdinality 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 the
 re is an additional propagational behaviour of monitored vertices. Later i
 n 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 sur
 vey on the power domination problem in graphs\, including the recent works
  of Seema Varghese and Seethu Varghese.\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Miodrag Iovanov (University of Iowa)
DTSTART:20201030T160000Z
DTEND:20201030T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/9
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/9/">On combinatorial Hopf algebras of multi-complexes</a>\
 nby Miodrag Iovanov (University of Iowa) as part of NY Combinatorics Semin
 ar\n\n\nAbstract\nA fruitful idea in combinatorics is to consider the tota
 lity of objects of a certain type\, and encode natural operations on these
  objects in operations of some algebra with coefficients in a field of cha
 racteristic 0. We introduce a general class of combinatorial objects\, whi
 ch we call multi-complexes\, which simultaneously generalizes graphs\, mul
 tigraphs\, hypergraphs and simplicial and delta complexes. We introduce a 
 natural algebra of multi-complexes which is defined as the algebra which h
 as a formal basis C of all isomorphism types of multi-complexes\, and mult
 iplication is to take the disjoint union. This is a Hopf algebra with an o
 peration encoding the dissasembly information for such objects\, and exten
 ds and generalizes the Hopf algebra of graphs. Such Hopf algebras are conn
 ected\, graded commutative and cocommutative\, and by general results of C
 artier-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 combin
 atorics. Such structures have been of high interest in literature\, both i
 ntrinsically and due to applications to combinatorial problems.\n\nWe 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 po
 lynomials are\, up to signs\, numbers counting multiplicities of sub-multi
 -complexes in a multi-complex. Using this\, we also solve the antipode for
 mula problem\, and find the cancellation and grouping free formula for the
  antipode. Such formulas are usually very difficult to obtain\, and consti
 tute a main question for such algebras.\n\nThe main method is to use certa
 in Mobius type formulas for posets of sub-objects of multi-complexes. As e
 xamples\, we will explicitly illustrate how our results specialize to the 
 formulas for graphs and simplicial complexes\, or how they specialize to r
 esults in all of the above mentioned particular cases. Time permitting\, I
  will show relations to applications of these results to the graph reconst
 ruction conjectures\, and rederiving some results in the literature on the
 se questions.\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pawel Rzazewski (Warsaw University of Technology\, Poland)
DTSTART:20201106T170000Z
DTEND:20201106T180000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/10
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/10/">Quasi-polynomial-time algorithms for Independent Set 
 and related problems in P_t-free graphs</a>\nby Pawel Rzazewski (Warsaw Un
 iversity of Technology\, Poland) as part of NY Combinatorics Seminar\n\n\n
 Abstract\nThe 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 su
 bgraph\, is one of the main open problems concerning algorithms for restri
 cted graph classes. The problem is known to be polynomial-time-solvable fo
 r t <= 6. Unfortunately the proof is fine-tailored for this class of graph
 s and our current algorithmic toolbox seems insufficient to provide a poly
 nomial-time algorithm for P_t-free graphs\, for every fixed t. In the rece
 nt breakthrough\, Gartland and Lokshtanov [FOCS 2020] gave a quasi-polynom
 ial-time algorithm for the problem in P_t-free graphs: their algorithm run
 s in time n^O(log^3n)\, where t is assumed to be a constant. Inspired by t
 heir ideas\, Pilipczuk\, Pilipczuk\, and Rzążewski [accepted to SOSA 202
 1] showed an arguably simpler algorithm with an improved running time boun
 d of n^O(log^2 n).\nDuring the talk I will present the simplified algorith
 m and discuss very recent extensions of this approach to different problem
 s\, including 3-Coloring and Feedback Vertex Set.\nJoint work with Peter G
 artland\, Daniel Lokshtanov\, Marcin Pilipczuk\, Michał Pilipczuk.\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ortrud Oellermann (University of Winnipeg\, Canada)
DTSTART:20201120T170000Z
DTEND:20201120T180000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/11
DESCRIPTION:by Ortrud Oellermann (University of Winnipeg\, Canada) as part
  of NY Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alejandro Morales (University of Massachusetts\, Amherst)
DTSTART:20201204T170000Z
DTEND:20201204T180000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/12
DESCRIPTION:by Alejandro Morales (University of Massachusetts\, Amherst) a
 s part of NY Combinatorics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lara Pudwell (Valparaiso University)
DTSTART:20201211T170000Z
DTEND:20201211T180000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/13
DESCRIPTION:by Lara Pudwell (Valparaiso University) as part of NY Combinat
 orics Seminar\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Aparna Lakshmanan S. (Cochin University of Science and Technology\
 , India)
DTSTART:20210903T160000Z
DTEND:20210903T170000Z
DTSTAMP:20260422T225845Z
UID:NewYorkCombinatoricsSeminar/14
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/NewYorkCombi
 natoricsSeminar/14/">Graph Labeling Problems: From Leech Trees to Leech Gr
 aphs</a>\nby Aparna Lakshmanan S. (Cochin University of Science and Techno
 logy\, India) as part of NY Combinatorics Seminar\n\n\nAbstract\nA graph l
 abeling is a function with some specific properties which assigns values t
 o 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 labeli
 ng\, 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 o
 f 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 lab
 eling is called a Leech tree. I will discuss some known results in Leech l
 abeling\, a new concept called Leech index\, and the possibility of extend
 ing Leech labeling to general graphs. Some Leech related labeling will als
 o be discussed. This is joint work with S. Arumugam and Seema Varghese.\n
LOCATION:https://researchseminars.org/talk/NewYorkCombinatoricsSeminar/14/
END:VEVENT
END:VCALENDAR