Pippinger's inducibility conjecture for cycles

Let CkC_k denote the cycle on kk vertices. For a graph HH, its induced density is the number of induced copies of HH divided by (GH)\binom{|G|}{|H|}; write I(H;n)I(H;n) for the maximum induced density of HH over graphs GG on nn vertices, and call limnI(H;n)\lim_{n\to\infty} I(H;n) the inducibility of HH. Pippinger's conjecture. For k5k\ge 5, the inducibility of the cycle CkC_k is

k!kkk.\frac{k!}{k^k-k}.

This conjecture, posed by Pippinger and Golumbic in 1975, concerns the extremal induced density of fixed cycles. Apart from the case resolved in the paper, the problem remains open; see the cited work for results on the inducibility of other graphs.

Sources & referencesView supporting material

Primary source

Natasha Morrison and Alex Scott, “Maximising the number of induced cycles in a graph”, arXiv:1603.02960 (2017).

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.