The inducibility of Turán graphs

Xizhi Liu, Jie Ma, Tianming Zhu · 2026

Read The inducibility of Turán graphs by Xizhi Liu, Jie Ma, Tianming Zhu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10548.txt.

Introduction

Xizhi Liu, Jie Ma, and Tianming Zhu study a core question in extremal graph theory. Given a small graph F, they ask how many copies of F a large graph can hold as induced subgraphs. The inducibility of F is the best share such copies can reach as the host graph grows. Turán graphs, built from balanced complete parts, are the test case here.

The paper works out the inducibility for this family of graphs. The result adds exact values to a problem where few are known. Such values show which host shapes pack the most copies of a pattern. The work will interest readers in combinatorics who study how local patterns fill large networks.

Catalog record

CREATORXizhi Liu, Jie Ma, Tianming Zhu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-10548

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The inducibility of Turán graphs Xizhi Liu, Jie Ma, Tianming Zhu Abstract Let I ⁡ ( F , n ) I(F,n) denote the maximum number of induced copies of a graph F F in an n n -vertex graph. The inducibility of F F , defined as i ⁡ ( F ) = lim n → ∞ I ⁡ ( F , n ) / ( n v ⁡ ( F ) ) i(F)=\lim_{n\to\infty}{I(F,n)}/{\tbinom{n}{v(F)}} , is a central problem in extremal graph theory. In this work, we investigate the inducibility of Turán graphs F F . This topic has been extensively studied in the literature, including works of Pippenger–Golumbic [ 27 ] , Brown–Sidorenko [ 7 ] , Bollobás–Egawa–Harris–Jin [ 5 ] , Mubayi, Reiher, and the first author [ 23 ] , and Yuster [ 32 ] . Broadly speaking, these results resolve or asymptotically resolve the problem when the part sizes of F F are either sufficiently large or sufficiently small (at most four). We complete this picture by proving that for every Turán graph F F and sufficiently large n n , the value I ⁡ ( F , n ) I(F,n) is attained uniquely by the m m -partite Turán graph on n n vertices, where m m is given explicitly in terms of the number of parts and vertices of F F . This confirms a conjecture of Bollobás–Egawa–Harris–Jin [ 5 ] from 1995, and we also establish the corresponding stability theorem. Moreover, we prove an asymptotic analogue for I k + 1 ​ ( F , n ) I_{k+1}(F,n) , the maximum number of induced copies of F F in an n n -vertex K k + 1 K_{k+1} -free graph, thereby completely resolving a recent problem of Yuster [ 32 ] . Finally, our results extend to a broader class of complete multipartite graphs in which the largest and smallest part sizes differ by at most on the order of the square root of the smallest part size. 1 Introduction A fundamental problem in extremal graph theory is to determine the maximum number of induced copies of a given graph F among all n -vertex graphs. Formally, given two graphs F and G , let I(F,G) denote the number of induced copies of F in G , that is, the number of subsets S\subseteq V(G) of size v(F) such that the induced subgraph G[S] is isomorphic to F . Here, v(F) denotes the number of vertices of F . For every positive integer n , let \displaystyle I(F,n)\coloneqq\max\left\{I(F,G)\colon v(G)=n\right\}. The inducibility of F is then defined as \displaystyle i(F)\coloneqq\lim_{n\to\infty}{I(F,n)}/{\tbinom{n}{v(F)}}. A systematic study of the inducibility problem for graphs was initiated in a foundational work of Pippenger–Golumbic [ 27 ] , in which they established several general properties of inducibility and determined the inducibility of complete bipartite graphs with part sizes differing by at most one. Determining I(F,n) (or even i(F) ) is rather difficult in general. For example, the inducibility of the path on four vertices remains wide open (see, e.g., [ 10 , 9 ] ). For small graphs, bounds on the inducibility of graphs on 4 , 5 , and 6 vertices have been obtained in several works, including Exoo [ 10 ] , Hirst [ 18 ] , Even-Zohar–Linial [ 9 ] , Pikhurko–Sliačan–Tyros [ 26 ] , and Bodnár et al. [ 4 ] , some of which employ the computer-assisted flag algebra machinery of Razborov [ 28 ] . A particularly interesting result obtained by Balogh–Hu–Lidickỳ–Pfender [ 2 ] is the determination of the inducibility of the 5 -cycle C_{5} , which confirms a special case of an old conjecture of Pippenger–Golumbic [ 27 ] on the inducibility of cycles. This conjecture remains open for longer cycles, and improved upper bounds were obtained in [ 17 , 19 ] . For general graphs, results of Yuster [ 31 ] and Fox–Huang–Lee [ 11 ] imply that for almost all graphs F , \displaystyle i(F)=\frac{v(F)!}{v(F)^{v(F)}-v(F)}, where the lower bound construction arises from nested blowups of F itself. Answering a question of Bollobás–Egawa–Harris–Jin [ 5 ] asymptotically, Hatami–Hirst–Norine [ 15 ] established that if F is a sufficiently large balanced blowup of some graph K , then the extremal graph for I(F,n) is essentially a blowup of K . Extending the results [ 24 , 20 , 12 ] on the edge-statistic conjecture of Alon–Hefetz–Krivelevich–Tyomkyn [ 1 ] , Ueltzen [ 30 ] recently classified all graphs with high inducibility. In this work, we focus on the case where F is a complete multipartite graph, and more specifically, an almost balanced complete multipartite graph. This class of graphs has already been studied extensively since the work of Pippenger–Golumbic [ 27 ] . Throughout this work, for positive integers a_{1},\ldots,a_{r} , let K_{a_{1},\ldots,a_{r}} denote the complete r -partite graph with part sizes a_{1},\ldots,a_{r} . For positive integers \ell\geq r , the Turán graph T_{r}(\ell) denotes the complete r -partite graph on \ell vertices in which the largest and smallest part sizes differ by at most one. The cases \ell=r and r=1 correspond to the complete graph on r vertices and the empty graph on \ell vertices, respectively; both are trivial cases in the inducibility problem. So, we assume for the remainder of this work that \ell\geq r+1 and r\geq 2 . Results of Pippenger–Golumbic [ 27 ] (also Bollobás–Nara–Tachibana [ 6 ] ) show that for bipartite Turán graphs F , the value of I(F,n) is attained by bipartite Turán graphs T_{2}(n) . Using Zykov symmetrization [ 33 ] together with additional arguments, Brown–Sidorenko [ 7 ] showed that for every complete multipartite graph F , an extremal graph for I(F,n) can always be chosen from the class of complete multipartite graphs; moreover, if F is complete bipartite, then the number of parts can be taken to be at most two. Nevertheless, determining the number of parts and the ratios of part sizes in the extremal construction for a complete multipartite graph F remains difficult in general. Consequently, the inducibility of complete multipartite graphs is still largely open. The family of Turán graphs T_{r}(\ell) has received substantial attention in the literature. Refining an asymptotic result of Brown–Sidorenko [ 7 ] for the balanced complete r -partite graph K_{r}(t):=T_{r}(rt) , Bollobás–Egawa–Harris–Jin [ 5 ] proved that when t\geq(1+o(1))\ln r , the r -partite Turán graph T_{r}(n) is the unique extremal graph, whereas this is not the case if t<\frac{\ln(r+1)}{r\ln(1+1/r)} . In the last section of [ 5 ] , they remarked that (with f(n,K_{r}(t)) below corresponding to I(K_{r}(t),n) in our notation): One may also venture the conjecture that for every pair (r,t) , r\geq 4 , t\geq 2 , if n is sufficiently large then for some s\geq 0 , T_{r+s}(n) is the unique extremal graph for f(n,K_{r}(t)) . This conjecture has been open for three decades. There has been recent progress on the case when F is a Turán graph with each part of small size. Mubayi, Reiher, and the first author [ 23 , Theorem 1.13] determined the inducibility when F is a Turán graph in which all but one part have size one. This result was extended very recently

Read the complete text