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;VALUE=DATE-TIME:20200828T160000Z
DTEND;VALUE=DATE-TIME:20200828T170000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/1
DESCRIPTION:Title: Zero forcing\, propagation time\, and throttling on a g
raph\nby Leslie Hogben (Iowa State University and and American Institute o
f Mathematics) as part of NY Combinatorics Seminar\n\n\nAbstract\nZero for
cing is an iterative process that repeatedly applies a color change rule t
o color blue all the vertices of a (simple) graph G\, and the minimum numb
er 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 mul
tiplicity of an eigenvalue of matrices having off-diagonal nonzero pattern
described by the edges of the graph and in other applications. Variants f
or positive semidefinite matrices and skew symmetric matrices described by
G have also been studied. In addition to determining the zero forcing num
ber\, 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 t
alk will give an overview of these related areas.\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sandra Kingan (Brooklyn College\, CUNY)
DTSTART;VALUE=DATE-TIME:20200911T160000Z
DTEND;VALUE=DATE-TIME:20200911T170000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/2
DESCRIPTION:Title: Minor preserving deletable edges in graphs\nby Sandra K
ingan (Brooklyn College\, CUNY) as part of NY Combinatorics Seminar\n\nAbs
tract: TBA\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:No Talk
DTSTART;VALUE=DATE-TIME:20200918T160000Z
DTEND;VALUE=DATE-TIME:20200918T170000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/3
DESCRIPTION:by No Talk as part of NY Combinatorics Seminar\n\nAbstract: TB
A\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Megan Owen (Lehman College\, CUNY)
DTSTART;VALUE=DATE-TIME:20200925T160000Z
DTEND;VALUE=DATE-TIME:20200925T170000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/4
DESCRIPTION:Title: Two problems on tree-based networks\nby Megan Owen (Leh
man College\, CUNY) as part of NY Combinatorics Seminar\n\n\nAbstract\nWhe
n DNA is only passed from parents to offspring\, evolutionary histories ca
n be modelled by a phylogenetic tree. However\, for some organisms\, like
bacteria\, the evolutionary process is more complex\, and their evolutiona
ry history should be modelled with a directed acyclic graph (DAG)\, or phy
logenetic network. We study two problems on tree-based networks\, which ar
e a sub-class of phylogenetic networks built by adding arcs only between e
dges 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 sho
wed that determining if a network is tree-based can be decided in polynomi
al time via a reduction to 2SAT. We show that it is NP-hard to determine i
f a network is based on a specific tree by reduction from 3-Dimensional Ma
tching (3DM). We also show that a maximum tree covering a phylogenetic net
work 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 (Hun
ter College) and our Research Experience for Undergraduates (REU) students
from Fall 2015 and Fall 2017.\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jo Ellis-Monaghan (University of Amsterdam)
DTSTART;VALUE=DATE-TIME:20201002T160000Z
DTEND;VALUE=DATE-TIME:20201002T170000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/5
DESCRIPTION:Title: New Dualities From Old: Generating Geometric\, Petrie\,
and Wilson Dualities and Trialities of Ribbon Graphs\nby Jo Ellis-Monagha
n (University of Amsterdam) as part of NY Combinatorics Seminar\n\n\nAbstr
act\nWe develop tools to identify and generate new surface embeddings of g
raphs with various forms of self-duality including geometric duality\, Pet
rie duality\, Wilson duality\, and both forms of triality (which is like d
uality\, but of order three instead of two). Previous work typically focus
ed on regular maps (special\, highly symmetric\, embedded graphs)\, but th
e 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 grap
hs with some form of self-duality or self-triality to the study of one-ver
tex 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. Thi
s is joint work with Lowell Abrams (George Washington University).\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Jan Goedgebeur (Ghent University\, Belgium)
DTSTART;VALUE=DATE-TIME:20201009T160000Z
DTEND;VALUE=DATE-TIME:20201009T170000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/6
DESCRIPTION:Title: Generation algorithms for solving mathematical and chem
ical problems\nby Jan Goedgebeur (Ghent University\, Belgium) as part of N
Y Combinatorics Seminar\n\n\nAbstract\nComputers are often used in combina
torics to determine if combinatorial objects with given structural or extr
emal properties exist as these existence problems are often too complex to
solve by hand. This is done by designing and implementing generation algo
rithms which construct combinatorial objects from a given class (typically
avoiding the generation of isomorphic copies) and analysing the resulting
graphs.\n\nIn this talk we will give an introduction to the exhaustive is
omorphism-free generation of graphs. We will also give concrete examples o
f how this has helped to gain new insights and solve problems in mathemati
cs and chemistry.\n\nApplications in mathematics include the generation of
cubic graphs and snarks. We will present a new algorithm for the efficien
t generation of all non-isomorphic cubic graphs and show how this algorith
m can be extended to generate snarks efficiently. A snark is a cyclically
4-edge-connected cubic graph with chromatic index 4. Snarks are of interes
t since for a lot of conjectures it can be proven that if the conjecture i
s false\, the smallest possible counterexamples will be snarks. Our algori
thm enabled us to generate all snarks up to 36 vertices\, which was imposs
ible with previous methods. This new list of snarks allowed us to find cou
nterexamples to several published open conjectures.\n\nAn application of g
raph 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 al
l fullerenes up to 400 vertices\, which enabled us to prove that the small
est counterexample to the spiral conjecture has 380 vertices.\n\nThis talk
is based on joint work with Gunnar Brinkmann (Ghent University) and Brend
an McKay (Australian National University).\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Offner (Carnegie Mellon University)
DTSTART;VALUE=DATE-TIME:20201016T160000Z
DTEND;VALUE=DATE-TIME:20201016T170000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/7
DESCRIPTION:Title: Path and cycle decompositions of hypercube graphs\nby D
avid Offner (Carnegie Mellon University) as part of NY Combinatorics Semin
ar\n\n\nAbstract\nGiven a subgraph H of an n-dimensional hypercube Q_n\, i
s it possible to partition the edges of the hypercube into edge-disjoint c
opies of H? The answer is known in certain cases\, such as when H is a pat
h and n is odd\, and for paths and cycles that are not too long relative t
o n when n is even. It is conjectured that a hypercube of even dimension c
an be decomposed into any path satisfying certain necessary divisibility c
onditions. This talk will summarize what is known about edge-decomposition
s of the hypercube\, and describe some recent progress toward decomposing
hypercubes of even dimension into long paths and cycles. Joint work with M
aria Axenovich and Casey Tompkins\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ambat Vijayakumar (Cochin University of Science and Technology\, I
ndia)
DTSTART;VALUE=DATE-TIME:20201023T160000Z
DTEND;VALUE=DATE-TIME:20201023T170000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/8
DESCRIPTION:Title: Power domination problem - A Survey\nby Ambat Vijayakum
ar (Cochin University of Science and Technology\, India) as part of NY Com
binatorics Seminar\n\n\nAbstract\nThe notion of power domination problem i
n graphs is motivated by the problem of placing Phasor Measurement Units (
PMU) in an electric power system. This problem is viewed as a graph theore
tic problem by Haynes et al. in 2002. The power domination problem in grap
hs consists of finding a minimum set of vertices S that monitors the entir
e graph following the two "monitoring rules" - domination and propagation
rules. The domination rule allows a vertex v in S to monitor itself and al
l its neighbours. After applying the domination rule on every vertex of S\
, if a monitored vertex u has all its neighbours monitored except one neig
hbour w\, then the propagation rule permits the vertex u to moniotor w. If
every vertex is monitored after the repeated application of the propagati
on rule\, we call S a power dominating set (PDS) of G. The minimum cardina
lity of a PDS of G is called the power domination number of the graph. Pow
er domination can be viewed as a variation of domination in which there is
an additional propagational behaviour of monitored vertices. Later in 201
2\, as a generalization of domination and power domination\, Chang et al.
introduced the notion of k-power domination by adding the possibility of p
ropagating up to k vertices. In this talk\, we shall give a short survey o
n the power domination problem in graphs\, including the recent works of S
eema Varghese and Seethu Varghese.\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Miodrag Iovanov (University of Iowa)
DTSTART;VALUE=DATE-TIME:20201030T160000Z
DTEND;VALUE=DATE-TIME:20201030T170000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/9
DESCRIPTION:Title: On combinatorial Hopf algebras of multi-complexes\nby M
iodrag Iovanov (University of Iowa) as part of NY Combinatorics Seminar\n\
n\nAbstract\nA fruitful idea in combinatorics is to consider the totality
of objects of a certain type\, and encode natural operations on these obje
cts in operations of some algebra with coefficients in a field of characte
ristic 0. We introduce a general class of combinatorial objects\, which we
call multi-complexes\, which simultaneously generalizes graphs\, multigra
phs\, hypergraphs and simplicial and delta complexes. We introduce a natur
al algebra of multi-complexes which is defined as the algebra which has a
formal basis C of all isomorphism types of multi-complexes\, and multiplic
ation is to take the disjoint union. This is a Hopf algebra with an operat
ion encoding the dissasembly information for such objects\, and extends an
d generalizes the Hopf algebra of graphs. Such Hopf algebras are connected
\, graded commutative and cocommutative\, and by general results of Cartie
r-Kostant-Milnor-Moore\, are just a polynomial algebra. However\, it comes
with additional structure which encodes combinatorial information\, and t
he main goal is to describe its structure in a way relating to combinatori
cs. Such structures have been of high interest in literature\, both intrin
sically and due to applications to combinatorial problems.\n\nWe give a so
lution to the problem in this generality and find an explicit basis B of t
he space of primitives\, and which is of combinatorial relevance: it is su
ch that each multi-complex is a polynomial with non-negative integer coeff
icients of the elements of B\, and each element of B is a polynomial with
integer coefficients in C. The coefficients appearing in all these polynom
ials are\, up to signs\, numbers counting multiplicities of sub-multi-comp
lexes in a multi-complex. Using this\, we also solve the antipode formula
problem\, and find the cancellation and grouping free formula for the anti
pode. Such formulas are usually very difficult to obtain\, and constitute
a main question for such algebras.\n\nThe main method is to use certain Mo
bius type formulas for posets of sub-objects of multi-complexes. As exampl
es\, we will explicitly illustrate how our results specialize to the formu
las for graphs and simplicial complexes\, or how they specialize to result
s in all of the above mentioned particular cases. Time permitting\, I will
show relations to applications of these results to the graph reconstructi
on conjectures\, and rederiving some results in the literature on these qu
estions.\n
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pawel Rzazewski (Warsaw University of Technology\, Poland)
DTSTART;VALUE=DATE-TIME:20201106T170000Z
DTEND;VALUE=DATE-TIME:20201106T180000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/10
DESCRIPTION:by Pawel Rzazewski (Warsaw University of Technology\, Poland)
as part of NY Combinatorics Seminar\n\nInteractive livestream: https://us0
2web.zoom.us/j/82681226374\nPassword hint: nycs\nAbstract: TBA\n
URL:https://us02web.zoom.us/j/82681226374
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ortrud Oellermann (University of Winnipeg\, Canada)
DTSTART;VALUE=DATE-TIME:20201120T170000Z
DTEND;VALUE=DATE-TIME:20201120T180000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/11
DESCRIPTION:by Ortrud Oellermann (University of Winnipeg\, Canada) as part
of NY Combinatorics Seminar\n\nInteractive livestream: https://us02web.zo
om.us/j/82681226374\nPassword hint: nycs\nAbstract: TBA\n
URL:https://us02web.zoom.us/j/82681226374
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alejandro Morales (University of Massachusetts\, Amherst)
DTSTART;VALUE=DATE-TIME:20201204T170000Z
DTEND;VALUE=DATE-TIME:20201204T180000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/12
DESCRIPTION:by Alejandro Morales (University of Massachusetts\, Amherst) a
s part of NY Combinatorics Seminar\n\nInteractive livestream: https://us02
web.zoom.us/j/82681226374\nPassword hint: nycs\nAbstract: TBA\n
URL:https://us02web.zoom.us/j/82681226374
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lara Pudwell (Valparaiso University)
DTSTART;VALUE=DATE-TIME:20201211T170000Z
DTEND;VALUE=DATE-TIME:20201211T180000Z
DTSTAMP;VALUE=DATE-TIME:20201101T013029Z
UID:NewYorkCombinatoricsSeminar/13
DESCRIPTION:by Lara Pudwell (Valparaiso University) as part of NY Combinat
orics Seminar\n\nInteractive livestream: https://us02web.zoom.us/j/8268122
6374\nPassword hint: nycs\nAbstract: TBA\n
URL:https://us02web.zoom.us/j/82681226374
END:VEVENT
END:VCALENDAR