BEGIN:VCALENDAR
VERSION:2.0
PRODID:-// - ECPv5.3.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://aarms.math.ca
X-WR-CALDESC:Events for
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20211020T153000
DTEND;TZID=UTC:20211020T163000
DTSTAMP:20240423T054658
CREATED:20211025T003426Z
LAST-MODIFIED:20211025T003520Z
UID:6454-1634743800-1634747400@aarms.math.ca
SUMMARY:Atlantic Graph Theory Seminar: Viresh Patel (University of Amsterdam)
DESCRIPTION:Title: Path decompositions of random directed graphs \nIn this talk we consider the problem of partitioning the edges of a digraph into as few paths as possible. The minimum number of paths needed in such an edge decomposition is called the path number of the digraph. \nThe problem of determining the path number is generally NP-hard. However\, there is a simple (easy to compute) lower bound for the path number of a digraph in terms of its degree sequence\, and a conjecture of Alspach\, Pullman\, and Mason from 1976 states that this lower bound gives the correct value of the path number for any even tournament. The conjecture was recently resolved\, and in this talk I will discuss to what extent the conjecture holds for other digraphs. In particular I will discuss some of the ingredients of a recent result showing that the conjecture holds for almost all digraphs. \nMore generally we will see the conjecture holds with high probability for the random directed graph D_{n\,p} for a large range of p. In fact the proof does not use randomness in a significant way.\n\nThis is joint work with Alberto Espuny Díaz and Fabian Stroh. \nJoin Zoom Meeting: link
URL:https://aarms.math.ca/event/atlantic-graph-theory-seminar-viresh-patel-university-of-amsterdam/
LOCATION:Zoom seminar
CATEGORIES:AARMS Atlantic Graph Theory Seminar
ORGANIZER;CN="Jason%20Brown":MAILTO:jason.brown@dal.ca
END:VEVENT
END:VCALENDAR