Directed-path inducibility conjecture for transitive-tournament-free oriented graphs

Let Pk\vec{P}_k be the directed path on kk vertices, let Ck+1\vec{C}_{k+1} be the directed cycle on k+1k+1 vertices, and let T3\vec{T}_3 be the transitive tournament on three vertices. Let T\mathcal{\vec T} be the family of T3\vec{T}_3-free oriented graphs, and write I(Pk,T)I(\vec{P}_k,\mathcal{\vec T}) for the limiting maximum induced density of Pk\vec{P}_k in this family.

Transitive-tournament-free inducibility conjecture. The number of induced copies of Pk\vec{P}_k over all T3\vec{T}_3-free oriented graphs on nn vertices is maximized by a balanced blow-up of Ck+1\vec{C}_{k+1}. Consequently,

I(Pk,T)=k!(k+1)k1.I(\vec{P}_k,\mathcal{\vec T})=\frac{k!}{(k+1)^{k-1}}.

This is a restricted version of the iterated blow-up conjecture, motivated by the simpler structure of T3\vec{T}_3-free oriented graphs; its resolution is not supplied in the source.

Sources & referencesView supporting material

Primary source

Ilkyoo Choi, Bernard Lidický and Florian Pfender, “Inducibility of directed paths”, arXiv:1811.03747 (2020).

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.