Inducibility of rainbow graphs

Abstract

Fix $k\ge 11$ and a rainbow $k$-clique $R$. We prove that the inducibility of $R$ is $k!/(k^k-k)$. An extremal construction is a balanced recursive blow-up of $R$. This answers a question posed by Huang, that is a generalization of an old problem of Erd\H os and Sós. It remains open to determine the minimum $k$ for which our result is true. More generally, we prove that there is an absolute constant $C>0$ such that every $k$-vertex connected rainbow graph with minimum degree at least $C\log k$ has inducibility $k!/(k^k-k)$.

27 pages

References in corpus (7)

• The Clique Density Theorem
• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Rainbow triangles in three-colored graphs
• A bound on the inducibility of cycles
• Polynomial to exponential transition in Ramsey theory
• Kruskal--Katona-Type Problems via the Entropy Method
• $C_5$ is almost a fractalizer