2018/01/03 by Raphael Yuster, Yuster, Raphael · 1 citation
Computer Science · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1801.01047
openalex publication_date 2018/01/03 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
Let H be a graph on h vertices. The number of induced copies of H in a\ngraph G is denoted by iH(G). Let iH(n) denote the maximum of iH(G)\ntaken over all graphs G with n vertices.\n Let f(n,h) = \Πih ai where \∑i=1h ai = n and the ai are\nas equal as possible. Let g(n,h) = f(n,h) + \∑i=1h g(ai,h). It is\nproved that for almost all graphs H on h vertices it holds that\niH(n)=g(n,h) for all n \≤ 2\√(h). More precisely, we define an\nexplicit graph property cal Ph which, when satisfied by H, guarantees\nthat iH(n)=g(n,h) for all n \≤ 2\√(h). It is proved, in particular,\nthat a random graph on h vertices satisfies cal Ph with probability\n1-oh(1). Furthermore, all extremal n-vertex graphs yielding iH(n) in\nthe aforementioned range are determined.\n We also prove a stability result. For H \∈ cal Ph and a graph G with\nn \≤ 2\√(h) vertices satisfying iH(G) \≥ f(n,h), it must be that\nG is obtained from a balanced blowup of H by adding some edges inside the\nblowup parts.\n The em inducibility of H is iH = \limn \→ \∞\niH(n)/ binomnh. It is known that iH \≥ h!/(hh-h) for all graphs H\nand that a random graph H satisfies almost surely that iH \≤ h3\log\nhh!/(hh-h). We improve upon this upper bound almost matching the lower\nbound. It is shown that a graph H which satisfies cal Ph has iH\n=(1+O(h^-h1/3))h!/(hh-h).\n