The extremal digraph conjecture for directed paths

Let Pk+1P_{k+1} be the directed path on k+1k+1 vertices, let ex(n,Pk+1){\rm ex}(n,\overrightarrow{P_{k+1}}) denote the maximum number of arcs in an Pk+1\overrightarrow{P_{k+1}}-free digraph of order nn, and let EX(n,Pk+1){\rm EX}(n,\overrightarrow{P_{k+1}}) be the family of extremal digraphs. For n3kn\ge 3k, let Tn,k\overrightarrow{T_{n,k}} be the corresponding kk-partite transitive tournament construction, let a(D)a(D) denote the number of arcs of a digraph DD, and let Tn,k\overrightarrow{\mathcal{T}_{n,k}} be the family of its extremal constructions.

The extremal digraph conjecture for directed paths. For every k,nNk,n\in \mathbb{N}^* with n3kn\ge 3k,

ex(n,Pk+1)=a(Tn,k),{\rm ex}(n,\overrightarrow{P_{k+1}})=a(\overrightarrow{T_{n,k}}),

and

EX(n,Pk+1)=Tn,k.{\rm EX}(n,\overrightarrow{P_{k+1}})=\overrightarrow{\mathcal{T}_{n,k}}.

The result is known for directed paths of lengths corresponding to the established cases k=2k=2 and k=3k=3, but the general assertion for all kk and n3kn\ge 3k remains open.

Sources & referencesView supporting material

Primary source

Wenling Zhou and Binlong Li, “The Turan problems of directed paths and cycles in digraphs”, arXiv:2102.10529 (2021).

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.