- This event has passed.
Atlantic Graph Theory Seminar: Viresh Patel (University of Amsterdam)
October 20, 2021 @ 3:30 pm - 4:30 pm
Title: Path decompositions of random directed graphs
In 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.
The 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.
More 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.
This is joint work with Alberto Espuny Díaz and Fabian Stroh.
Join Zoom Meeting: link