The inducibility of đťź” \mathbf{6} -vertex graphs

Levente Bodnár, Jun Gao, Jared León, Xizhi Liu, Oleg Pikhurko, Shumin Sun · 2026

Read The inducibility of 𝟔 \mathbf{6} -vertex graphs by Levente Bodnár, Jun Gao, Jared León, Xizhi Liu, Oleg Pikhurko, Shumin Sun (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-2606-00290.txt.

Introduction

Bodnár and co-authors map how dense a small graph can sit inside huge host graphs. The key gauge asks for the top share of a form a host can hold as a true part. Hosts grow vast in this gauge, called inducibility. Graphs with six points hold 78 forms in all, up to flips and mirror swaps.

The team works through the six-point case in a set way. Flag math gives the sharp cap in 36 of those forms. Most of those caps are fresh finds, they note. For each solved form, they sketch the shape of near-peak hosts. In 32 forms, that shape stands firm with no loose parts. They set firm guesses for 12 more forms. In those, top and floor marks sit close but not yet met.

Catalog record

CREATORLevente Bodnár, Jun Gao, Jared León, Xizhi Liu, Oleg Pikhurko, Shumin Sun
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.00290

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 𝟔 \mathbf{6} -vertex graphs Thanks: (LB, JG, OP, SS): research supported by ERC Advanced Grant 101020255. Thanks: (JL): research supported by the Warwick Mathematics Institute Centre for Doctoral Training Thanks: (XL): research supported by the Excellent Young Talents Program (Overseas) of the National Natural Science Foundation of China Levente Bodnár, Jun Gao, Jared León, Xizhi Liu, Oleg Pikhurko, Shumin Sun Abstract . The inducibility constant λ F \lambda_{F} of a graph F F is the asymptotically maximum induced density of F F in a growing sequence of graphs. This paper systematically investigates the case when F F has 6 vertices (and there are 78 cases to consider up to isomorphism and complementation). We show that flag algebras can compute the sharp upper bound on λ F \lambda_{F} in 36 cases of which, as far as the authors know, 30 are new results. In each of the solved cases, we also prove results about the structure of large (almost) extremal graphs. In particular, we establish perfect stability in all 32 cases when the extremal construction has no quasirandom parts. We also present conjectures about the value of λ F \lambda_{F} for 12 further cases (where the upper and lower bounds are very close to each other). 1. Introduction For graphs F and G with \kappa\leq n vertices respectively, let P(F,G) denote the number of \kappa -subsets of V(G) that induce a graph isomorphic to F and let p(F,G):=P(F,G)/\binom{n}{\kappa} be the (induced) density of F in G . For a given graph F , the F -inducibility problem (or the F -problem for short) asks for p(F,n) , the maximum of p(F,G) over all graphs G with n vertices. By an easy averaging argument, one can show that the limit \lambda_{F}:=\lim_{n\to\infty}p(F,n) exists; we call it the inducibility constant of F . The inducibility problem has drawn a great amount of interest since it was introduced by Pippenger and Golumbic [ 47 ] in 1975. For some sample of results, see e.g. [ 52 , 9 , 13 , 8 , 34 , 31 , 22 , 3 , 33 , 38 , 54 , 39 , 53 ] . Also, it was considered for many other types of structures: for example, oriented graphs [ 36 , 14 , 10 , 35 ] , hypercubes [ 27 , 28 , 6 ] , various tree-like structures [ 1 , 18 , 17 , 12 ] , constrained graphs (for example, triangle-free graphs [ 30 , 29 , 32 ] ), etc. Since the inducibility constant \lambda_{F} does not change if we replace F by its complement \overline{F} , it is enough to consider only one graph from each complementary pair. If F is complete partite then a result by Brown and Sidorenko [ 13 , Proposition 1] implies that, in order to determine the value of p(F,n) , it is enough to consider only complete partite graphs on [n] and the problem in the limit reduces to maximising some polynomial on the space of part ratios. Each 3 -vertex graph or its complement is complete partite, so they are covered e.g. by the above result of Brown and Sidorenko [ 13 ] . All 4 -vertex graphs F were resolved by the results in [ 9 , 23 , 13 , 34 ] except when F=P_{4} is the 4 -vertex path. The best known lower bound \lambda_{P_{4}}\geq 1173/5824=0.2014\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt is due to Even-Zohar and Linial [ 22 ] while the best known upper bound \lambda_{P_{4}}\leq 0.204513\hskip 0.9pt.\hskip 0.3pt.\hskip 0.3pt.\hskip 1.5pt comes from flag algebras. Even-Zohar and Linial [ 22 , Table 2] produced the summary of known and new results for 5 -vertex graphs F . After the publication of [ 22 ] , the values of inducibility constant for some new 5 -vertex graphs F were determined in [ 46 , 42 , 40 , 7 ] but there are still 5 (non-equivalent) remaining open cases, described in [ 7 ] . In this paper, we systematically investigate the inducibility problem for graphs on 6 vertices, using flag algebras to prove upper bounds. There are 156 non-isomorphic 6 -vertex graphs, which we group into 78 complementary pairs \{F_{i},\overline{F}_{i}\} for 0\leq i\leq 77 . (Note that, since \binom{6}{2} is odd, no 6 -vertex graph is self-complementary.) Our results are as follows; they are also summarised in Table 1 below. Using the package FlagAlgebraToolbox of Bodnár [ 5 ] , we could produce the sharp upper bound on the inducibility constant \lambda_{F} in 36 cases (out of 78 ) of which 30 cases are, as far as we can see, new results. There are three further cases where the package did not give the required sharp result but the exact value was previously known by other methods, and we include these cases in the table: F_{1} , whose inducibility constant was determined by Liu, Mubayi and Reiher [ 42 , Theorem 1.13] , the cycle case F_{51}=C_{6} , treated by Brandt, Lidický and Pfender as recorded in Brandt’s thesis [ 11 ] , and the net graph F_{43} , determined by Blumenthal and Phillips [ 4 ] . In all cases solved here, we also describe almost extremal graphs of large order n within o(n^{2}) adjacency edits. It happens in each case that, informally speaking, there is a unique limit construction. The latter statement can be formalised using the language of graphons (see Lovász’ book [ 43 ] ), where a graphon W is called F -extremal if the appropriately defined density p(F,W) is equal to its maximum possible value \lambda_{F} . Then, in all cases solved here, the extremal graphon W is unique and happens to be a step graphon (with finitely many steps). If each value of the extremal graphon W is 0 or 1 (which happens in 32 cases) then it is natural to represent constructions as blowups of a pattern B (a graph, with loops allowed). In all of these 32 cases, we prove furthermore that the so-called perfect B -stability holds using criteria from [ 46 ] (see Section 2.2 for details). This is a rather strong structural property that, in particular, implies that every large extremal graph is exactly a blowup of B . Thus in order to determine p(F,n) exactly for large n , it is enough to maximise the density of F in an n -vertex blowup of B , which amounts to maximising an explicit polynomial in integers summing up to n . We do not attempt to do this integer optimisation. However, we do determine the (unique in all solved cases) limiting vector of optimal part ratios. There are four cases, namely, i\in\{13,70,75,77\} in Table 1 , when almost extremal graphs are quasirandom balanced bipartite graphs of appropriate edge density p_{i} , and we show that every large almost optimal graph is close in the edit distance to this form. Thus, in each of these cases, the (unique) extremal graphon W consists of two parts V_{0} and V_{1} , each of measure 1/2 , with W being 0 on all pairs inside a part and p_{i} on all cross-pairs. It is unclear how to define perfect stability when

Read the complete text