Iterated blow-up conjecture for inducibility of directed paths

About 8 years old · traced to

Let P⃗k\vec{P}_k be the directed path on kk vertices, and let C⃗k+1\vec{C}_{k+1} be the directed cycle on k+1k+1 vertices. For an oriented graph GG, write dP⃗k(G)d_{\vec{P}_k}(G) for the induced density of P⃗k\vec{P}_k, and let I(P⃗k)I(\vec{P}_k) be the limiting maximum of this density over all oriented graphs. An iterated balanced blow-up of C⃗k+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 P⃗k\vec{P}_k over all oriented graphs on nn vertices is maximized by an iterated balanced blow-up of C⃗k+1\vec{C}_{k+1}. Consequently,

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

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

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.