On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices
On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices
复制标题
关于带有少量删除顶点的阿贝尔群随机凯莱图的可归纳问题
DOI：
10.1002/rsa.21010
复制
发表时间：
2019
影响因子：
1
通讯作者：
F. Wei
中科院分区：
文献类型：
--
作者：
J. Fox;Lisa Sauermann;F. Wei
给定一个k-顶点图H和一个整数n，具有H的最大导出副本数的n-顶点图是什么？这个问题与Pippenger和Golumbic在1975年提出的归纳问题密切相关，该问题要求n-顶点图的k-顶点子集的最大可能分数诱导H的副本。Huang，Lee和第一作者证明了对于一个随机k-顶点图H，几乎必然使H的诱导副本数最大化的n-顶点图是H的平衡迭代爆破。在本文中，我们考虑通过从阿贝尔群的随机凯莱图H ~中删除少量顶点来获得图H的情况。我们证明了在这种情况下，几乎所有使H的诱导副本数最大化的n顶点图都是H的平衡迭代爆破图。
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˜ .