On the exact maximum induced density of almost all graphs and their inducibility
On the exact maximum induced density of almost all graphs and their inducibility
复制标题
关于几乎所有图的精确最大诱导密度及其诱导性
DOI：
10.1016/j.jctb.2018.09.005
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. Yuster
中科院分区：
文献类型：
--
作者：
R. Yuster
设H是一个顶点数为h的图。图G中H的导出拷贝数记为iH（G）。设iH（n）表示在所有n阶图G上取的iH（G）的最大值.设f（n，h）= ∑ i h ai其中∑ i= 1 h ai = n且ai尽可能相等.设g（n，h）= f（n，h）+∑ i= 1hg（ai，h）.证明了对几乎所有的h阶图H，对所有n≤ 2 h，iH（n）= g（n，h）成立.更精确地说，我们定义了一个显式的图性质Ph，当H满足该性质时，保证对所有n≤ 2 h，iH（n）= g（n，h）。特别地，证明了在h个顶点上的随机图以概率1− o h（1）满足Ph。进一步，确定了所有在上述范围内产生iH（n）的n-顶点极图.我们还证明了一个稳定的结果。对H∈ Ph，n≤ 2 h个顶点的图G满足iH（G）≥ f（n，h），则G必须是由H的平衡爆破通过在爆破部分内增加一些边而得到的. H的诱导数为iH = lim n→∞ <$iH（n）/（nh）.已知i H≥ h！/（h h− h），且随机图H几乎必然满足i H≤ h 3 log <$h h！/（h h− h）。我们改进了这个上界几乎匹配的下界。证明了满足Ph的图H有i H=（1+ O（h-h 1/3））h！/（h h− h）。
Let H be a graph on h vertices. The number of induced copies of H in a graph G is denoted by i H (G). Let i H (n) denote the maximum of i H (G) taken over all graphs G with n vertices. Let f (n, h)= Π i h a i where∑ i= 1 h a i= n and the a i are as equal as possible. Let g (n, h)= f (n, h)+∑ i= 1 h g (a i, h). It is proved that for almost all graphs H on h vertices it holds that i H (n)= g (n, h) for all n≤ 2 h. More precisely, we define an explicit graph property P h which, when satisfied by H, guarantees that i H (n)= g (n, h) for all n≤ 2 h. It is proved, in particular, that a random graph on h vertices satisfies P h with probability 1− o h (1). Furthermore, all extremal n-vertex graphs yielding i H (n) in the aforementioned range are determined. We also prove a stability result. For H∈ P h and a graph G with n≤ 2 h vertices satisfying i H (G)≥ f (n, h), it must be that G is obtained from a balanced blowup of H by adding some edges inside the blowup parts. The inducibility of H is i H= lim n→∞ i H (n)/(n h). It is known that i H≥ h!/(h h− h) for all graphs H and that a random graph H satisfies almost surely that i H≤ h 3 log h h!/(h h− h). We improve upon this upper bound almost matching the lower bound. It is shown that a graph H which satisfies P h has i H=(1+ O (h− h 1/3)) h!/(h h− h).