Iterated blow-up conjecture for inducibility of directed paths

Let Pk\vec{P}_k be the directed path on kk vertices, and let Ck+1\vec{C}_{k+1} be the directed cycle on k+1k+1 vertices. For an oriented graph GG, write dPk(G)d_{\vec{P}_k}(G) for the induced density of Pk\vec{P}_k, and let I(Pk)I(\vec{P}_k) be the limiting maximum of this density over all oriented graphs. An iterated balanced blow-up of Ck+1\vec{C}_{k+1} is obtained by repeatedly replacing each vertex by equally sized independent classes and orienting edges between classes according to the directed cycle.

Iterated blow-up conjecture. The number of induced copies of Pk\vec{P}_k over all oriented graphs on nn vertices is maximized by an iterated balanced blow-up of Ck+1\vec{C}_{k+1}. Consequently,

I(Pk)=k!(k+1)k11.I(\vec{P}_k)=\frac{k!}{(k+1)^{k-1}-1}.

The conjecture extends the announced result I(P3)=2/5I(\vec{P}_3)=2/5 with extremal construction an iterated blow-up of C4\vec{C}_4. It is presented as an open generalization for longer oriented paths.

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.