***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Martin Loebl (Charles U., Prague)
Thursday 14th March, 3:00 in Fine Hall 224.
Title: Cut-obstacles and robust ear decompositions
A directed cycle double cover (DCDC) of a graph G is a family of
cycles of G, each provided with an orientation, such that every
edge of G is covered by exactly two directed cycles traversing
the edge in the opposite directions.
Cut-type objects called ``bridges'' are obviously obstructions to
the existence of a directed cycle double cover in a graph. Jaeger
conjectured in his strengthening of the Szekeres-Seymour Cycle Double
Cover Conjecture that bridges are actually the only obstructions.
We study potential obstructions to extending a given set of
orientations of edges in a mixed graph that contains both unoriented
and oriented edges towards a DCDC. We are surprisingly able to
characterise such obstructions for small edge-sets. The bridgeless
graphs that can be decomposed into such small sets form a restricted
class of the cubic bridgeless graphs, but we show that the existence
of subsequent constructions of DCDCs avoiding a single cut-type
obstruction in this restricted class of graphs encompasses the general
Jaeger's conjecture. This leads us to introduce new notions of (1) cut
obstacles in mixed graphs and of (2) reductions of robust networks.
We show that Jaeger's conjecture would follow if a certain subset
of robust networks admits a reduction which avoids creating a cut
obstacle in each of its consecutive steps. This adds the problem of
characterising well-reducible robust networks to the relatives of
the DCDC.
This speaker was supported by the H2020 MSCA RISE grant CoSP GA
No. 823748.
----------------------------------
Next week: spring recess. Week after: David Harris
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)