Alspach–Mason–Pullman conjecture on path decompositions of even tournaments

Let DD be a directed graph with vertex set V(D)V(D) and edge set E(D)E(D). A path decomposition of DD is a collection of directed paths whose edge sets partition E(D)E(D). Let pn(D){\rm pn}(D) be the minimum number of paths in a path decomposition of DD. For each vertex vV(D)v\in V(D), define its excess by ex(v)=dD+(v)dD(v){\rm ex}(v)=d_D^+(v)-d_D^-(v), its positive excess by ex+(v)=max{ex(v),0}{\rm ex}^+(v)=\max\{{\rm ex}(v),0\}, and its negative excess by ex(v)=max{ex(v),0}{\rm ex}^-(v)=\max\{-{\rm ex}(v),0\}. Define

ex(D)=vV(D)ex+(v)=vV(D)ex(v)=12vV(D)ex(v).{\rm ex}(D)=\sum_{v\in V(D)}{\rm ex}^+(v)=\sum_{v\in V(D)}{\rm ex}^-(v)=\frac12\sum_{v\in V(D)}|{\rm ex}(v)|.

A tournament is an orientation of a complete graph, and it is consistent when pn(D)=ex(D){\rm pn}(D)={\rm ex}(D). Alspach–Mason–Pullman conjecture. Every tournament TT with an even number of vertices satisfies

pn(T)=ex(T).{\rm pn}(T)={\rm ex}(T).

The excess gives a general lower bound for the number of paths in a path decomposition. The conjecture asserts that this lower bound is always attained for even tournaments; the supplied source gives no resolution status.

Sources & referencesView supporting material

Primary source

Allan Lo, Viresh Patel, Jozef Skokan and John Talbot, “Decomposing tournaments into paths”, arXiv:1902.10775 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.