On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices. Issue 4 (23rd April 2021)

• Record Type: Journal Article
• Authors: Fox, Jacob; Sauermann, Lisa; Wei, Fan
• Is Part Of: Random structures & algorithms. Volume 59:Issue 4(2021)
• Page Start: 554
• Page End: 615
• Publication Date: 2021-04-23
• Subjects: Cayley graph -- induciblity -- random graph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21010
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Given a k ‐vertex graph H and an integer n, what are the n ‐vertex graphs with the maximum number of induced copies of H ? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum possible fraction of k ‐vertex subsets of an n ‐vertex graph that induce a copy of H . Huang, Lee, and the first author proved that for a random k ‐vertex graph H, almost surely the n ‐vertex graphs maximizing the number of induced copies of H are the balanced iterated blow‐ups of H . In this article, we consider the case where the graph H is obtained by deleting a small number of vertices from a random Cayley graph H ˜ of an abelian group. We prove that in this case, almost surely all n ‐vertex graphs maximizing the number of induced copies of H are balanced iterated blow‐ups of H ˜ .