Inducibility of rainbow graphs
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.
Authors
- Clayton Mizgerd
- Emily Cairncross (ORCID: https://orcid.org/0000-0002-3821-1183)
- Dhruv Mubayi (ORCID: https://orcid.org/0000-0002-4709-8768)
Institutions
- University of Illinois Chicago (US)
Publication Details
- Journal
- Mathematical Proceedings of the Cambridge Philosophical Society
- Published
- 2025-10-02
- DOI
- https://doi.org/10.1017/s0305004125101692
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Division of Electrical, Communications and Cyber Systems