Inducibility of rainbow graphs
Emily Cairncross, Clayton Mizgerd, Dhruv Mubayi · Mathematical Proceedings of the Cambridge Philosophical Society · 2025
Abstract We prove that there is an absolute constant $C{\,\gt\,}0$ such that every k -vertex connected rainbow graph R with minimum degree at least $C\log k$ has inducibility $k!/(k^k-k)$ . The same result holds if $k\ge 11$ , and R is a clique. This answers a question posed by Huang, that is a generalisation of an old problem of Erdös and Sós. It remains open to determine the minimum k for which this is true.