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

About 8 years old · traced to

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

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

I(P⃗k,T⃗)=k!(k+1)k−1.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 T⃗3\vec{T}_3-free oriented graphs; its resolution is not supplied in the source.

References

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.