Forcing densities $\sigma(m,f)$ for induced subgraphs of given sizes: existence of the limit and the remaining $r=3,4$ cases of the $1/r$ conjecture

For fixed integers $m$ and $f$, let $S_n(m,f)$ be the set of edge counts $e$ such that every $n$-vertex graph with $e$ edges contains an induced subgraph on $m$ vertices with exactly $f$ edges, and let $\sigma(m,f)$ denote the limsup of $|S_n(m,f)|/\binom{n}{2}$. Erdős, Füredi, Rothschild and Sós (1999) determined the coarse behavior of $\sigma$ (exactly five pairs attain $\sigma=1$; all others satisfy $\sigma\le 2/3$) and left several questions open. Subsequent work resolved one of them: He, Ma and Zhao (preprint 2021, published 2025) proved $\sigma(m,f)\le 1/2$ outside the five exceptional pairs, with infinitely many pairs attaining $1/2$, answering the question of whether $\sigma(m,f)>1/2$ for only finitely many pairs, and they proved the conjectured equality $\sigma(m,f)=1/r$ for $r=2$ and all $r\ge 5$. The surviving open core is: (i) whether $\lim_{n\to\infty}|S_n(m,f)|/\binom{n}{2}$ exists for every fixed pair $(m,f)$ (known only where $\sigma=0$ and in the solved $1/r$ families); and (ii) the remaining cases $r=3$ and $r=4$ of the conjecture $\sigma(m,f)=1/r$ for pairs with $f=\binom{a}{2}=\binom{m}{2}-\binom{b}{2}=c(m-c)$.

Background

An induced subgraph of a graph is obtained by keeping a subset of the vertices and all edges whose both ends lie in that subset. A basic theme of extremal graph theory asks which global edge counts force the appearance of a given local configuration. Turán's theorem is the prototype: writing $t_p(n)$ for the number of edges of the balanced complete $p$-partite graph on $n$ vertices (the graph whose vertex set is split into $p$ nearly equal parts, with all edges between different parts and none within a part), every $n$-vertex graph with more than $t_{m-1}(n)$ edges contains a complete graph $K_m$ on $m$ vertices. The paper "Induced subgraphs of given sizes" by Erdős, Füredi, Rothschild and Sós (Discrete Mathematics, 1999, in the Paul Erdős memorial collection), introduced the induced analogue of a 1963 problem of Erdős recounted in that paper: rather than forbidding one fixed subgraph, one forbids every induced subgraph with a prescribed number of vertices and a prescribed number of edges.

Write $(n,e)\to(m,f)$ if every $n$-vertex graph with $e$ edges contains an induced subgraph on $m$ vertices with exactly $f$ edges; put $S_n(m,f)=\{e:(n,e)\to(m,f)\}$ and define the forcing density

$$\sigma(m,f)=\limsup_{n\to\infty}\frac{|S_n(m,f)|}{\binom{n}{2}}.$$

Since $S_n(m,f)$ never contains both $0$ and $\binom{n}{2}$, one has $0\le\sigma(m,f)\le 1$. The source paper established: the symmetry $\sigma(m,f)=\sigma\!\left(m,\binom{m}{2}-f\right)$, where the complement of a graph has the same vertices and exactly the edges absent from it; the extremal values $\sigma(m,0)=\sigma\!\left(m,\binom{m}{2}\right)=\frac{1}{m-1}$, a Turán-theorem computation; $\sigma(m,f)=0$ for all $1\le f\le m-2$; and $\sigma=1$ for the five pairs $(2,0)$, $(2,1)$, $(4,3)$, $(5,4)$, $(5,6)$, which form the set $A$. Their Theorem 1 shows these are exactly the pairs with $\sigma(m,f)>\frac{2}{3}$; every other pair satisfies $\sigma(m,f)\le\frac{2}{3}$. Their Theorem 3 concerns pairs $(m,f)$ admitting positive integers $a,b,c$ with $f=\binom{a}{2}=\binom{m}{2}-\binom{b}{2}=c(m-c)$: if $r\ge 2$ is the smallest integer such that $f=\sum_{i=1}^{r+1}\binom{x_i}{2}$ with integers $x_i\ge 1$ satisfying $\sum_i x_i=m$, then $\sigma(m,f)\ge\frac{1}{r}$, with equality for $r\ge 9$. The upper bound comes from graphs that are vertex-disjoint unions of at most $r$ cliques (a clique being a set of pairwise adjacent vertices): by the minimality of $r$, no choice of $m$ vertices in such a graph spans exactly $f$ edges, so these graphs avoid $(m,f)$, and their achievable edge counts are governed by the clique-partition spectrum $C(n,p)=\{\sum_{i=1}^{p}\binom{n_i}{2}:n_i\ge 0,\ \sum_i n_i=n\}$ taken at $p=r$, using an interval-covering property of $C(n,p)$ for large $p$ that the source paper cited as a private communication. The same paper proved that for all sufficiently large $m$, $\sigma(m,f)=0$ throughout the range $23m<f<c\,m^{3/2}$ for an absolute constant $c>0$, so most pairs have vanishing density.

Twenty years later He, Ma and Zhao (preprint 2021, published 2025) proved: every $(m,f)\notin A$ satisfies $\sigma(m,f)\le\frac{1}{2}$, while infinitely many pairs attain $\sigma(m,f)=\frac{1}{2}$, so the threshold $\frac{1}{2}$ is sharp and the pairs with $\sigma(m,f)>\frac{1}{2}$ are exactly the five pairs of $A$; and, for the pairs of Theorem 3, the equality $\sigma(m,f)=\frac{1}{r}$ holds whenever $r=2$ or $r\ge 5$, via elementary number-theoretic arguments for $r\ge 7$ and analytic, circle-method-type arguments for $r\ge 5$ (the circle method being a classical analytic-number-theory technique for counting representations of integers as sums of values of prescribed forms) applied to clique-partition spectra. They also showed that for these solved families the limit $\lim_{n\to\infty}|S_n(m,f)|/\binom{n}{2}$ exists and equals the same value, and gave a sufficient condition (their Lemma 5.1) for the limit to exist in general. In parallel, Axenovich and Weber introduced the stronger notion of an absolutely avoidable pair $(m,f)$, one for which $S_n(m,f)$ is empty for all large $n$ rather than merely of vanishing density, and proved that infinitely many such pairs exist, for example $(m,\binom{m}{2}/2)$ for $m$ in an explicit infinite set. Adjacent lines extend the framework to $r$-uniform hypergraphs (hypergraphs whose edges are $r$-element vertex sets; Weber; Axenovich, Balogh, Clemen and Weber) and to finite affine and projective spaces (Kovács and Nagy; Héger and Nagy), without touching the graph-case questions stated below.

Problem Statement

For fixed integers $m\ge 2$ and $0\le f\le\binom{m}{2}$, write $S_n(m,f)$ for the set of integers $e$ such that every $n$-vertex graph with $e$ edges contains an induced subgraph on $m$ vertices spanning exactly $f$ edges, and $\sigma(m,f)=\limsup_{n\to\infty}|S_n(m,f)|/\binom{n}{2}$. The problem left open by Erdős, Füredi, Rothschild and Sós and still unresolved after the subsequent literature is to complete the quantitative theory of these forcing densities. It has two linked components. (1) Limit existence: prove or disprove that the limit $\lim_{n\to\infty}|S_n(m,f)|/\binom{n}{2}$ exists for every fixed pair $(m,f)$, so that the limsup defining $\sigma(m,f)$ is a genuine limit; this is currently known only for pairs with $\sigma(m,f)=0$ and for the Theorem-3 pairs with $r=2$ or $r\ge 5$. (2) Exact values for clique-partition pairs: for pairs $(m,f)$ admitting positive integers $a,b,c$ with $f=\binom{a}{2}=\binom{m}{2}-\binom{b}{2}=c(m-c)$, where $r\ge 2$ is the smallest integer such that $f=\sum_{i=1}^{r+1}\binom{x_i}{2}$ holds for integers $x_i\ge 1$ with $\sum_i x_i=m$, prove or disprove that $\sigma(m,f)=\frac{1}{r}$ in the remaining cases $r=3$ and $r=4$; the lower bound $\sigma(m,f)\ge\frac{1}{r}$ holds for all such pairs by Theorem 3 of the source paper, and equality is known for $r=2$ and all $r\ge 5$, so the open content is whether the matching upper bound $\sigma(m,f)\le\frac{1}{r}$ also holds when $r=3$ or $r=4$ (note that the extremal pair $(m,0)$ has $r=m-1$, so its instances $(4,0)$ with $r=3$ and $(5,0)$ with $r=4$ are already settled by the known value $\sigma(m,0)=\frac{1}{m-1}$). The two components share one objective, the exact asymptotic behavior of the edge-count sets $S_n(m,f)$, and they constrain one another: the exact values of component (2) feed the limit question of component (1).

References

1. Paul Erdős, Zoltán Füredi, Bruce L. Rothschild, Vera T. Sós, "Induced subgraphs of given sizes", Discrete Mathematics 200 (1999), 61-77. DOI: 10.1016/S0012-365X(98)00387-2, https://doi.org/10.1016/S0012-365X(98)00387-2
2. Jialin He, Jie Ma, Lilu Zhao, "Improvements on Induced Subgraphs of Given Sizes", Communications in Mathematics and Statistics 13 (2025), no. 5, 1199-1218 (published online 10 October 2023). DOI: 10.1007/s40304-023-00355-5, https://doi.org/10.1007/s40304-023-00355-5; preprint arXiv:2101.03898, https://arxiv.org/abs/2101.03898
3. Maria Axenovich, Lea Weber, "Absolutely avoidable order-size pairs for induced subgraphs", Journal of Combinatorics 15 (2024), no. 1, Article 2, 41-57. DOI: 10.4310/joc.2024.v15.n1.a2, https://doi.org/10.4310/joc.2024.v15.n1.a2; preprint arXiv:2106.14908, https://arxiv.org/abs/2106.14908
4. Lea Weber, "Absolutely avoidable order-size pairs in hypergraphs", Journal of Combinatorics 15 (2024), no. 2, Article 3, 179-195. DOI: 10.4310/joc.2024.v15.n2.a3, https://doi.org/10.4310/joc.2024.v15.n2.a3; preprint arXiv:2205.15197, https://arxiv.org/abs/2205.15197
5. Maria Axenovich, József Balogh, Felix Christian Clemen, Lea Weber, "Unavoidable order-size pairs in hypergraphs - positive forcing density", Combinatorial Theory 3 (2023), no. 3. DOI: 10.5070/c63362798, https://doi.org/10.5070/c63362798; preprint arXiv:2208.06626, https://arxiv.org/abs/2208.06626
6. Yair Caro, Josef Lauri, Christina Zarb, "The feasibility problem for line graphs", Discrete Applied Mathematics 324 (2023), 167-180. DOI: 10.1016/j.dam.2022.09.019, https://doi.org/10.1016/j.dam.2022.09.019; preprint arXiv:2107.13806, https://arxiv.org/abs/2107.13806
7. Yair Caro, Matthew Cassar, Josef Lauri, Christina Zarb, "The Feasibility Problem - the family F(G) of all induced G-free graphs", preprint (2023), arXiv:2311.01082, https://arxiv.org/abs/2311.01082
8. Benedek Kovács, Zoltán Lóránt Nagy, "Avoiding intersections of given size in finite affine spaces AG(n,2)", preprint (2023), arXiv:2305.05632, https://arxiv.org/abs/2305.05632; EuroComb 2023 version: DOI: 10.5817/cz.muni.eurocomb23-093
9. Tamás Héger, Zoltán Lóránt Nagy, "Avoiding secants of given size in finite projective planes", Journal of Combinatorial Designs 33 (2024), no. 3, 83-93. DOI: 10.1002/jcd.21968, https://doi.org/10.1002/jcd.21968; preprint arXiv:2409.14213, https://arxiv.org/abs/2409.14213
10. Maria Axenovich, Domagoj Bradač, Lior Gishboliner, Dhruv Mubayi, Lea Weber, "Large cliques or cocliques in hypergraphs with forbidden order-size pairs", Combinatorics, Probability and Computing 33 (2024), no. 3, 286-299. DOI: 10.1017/s0963548323000433, https://doi.org/10.1017/s0963548323000433; preprint arXiv:2305.01531, https://arxiv.org/abs/2305.01531
11. Benedek Kovács, "Code-based [3,1]-avoiders in finite affine spaces AG(n,2)", Linear Algebra and its Applications 751 (2026), 1-17. DOI: 10.1016/j.laa.2026.07.018, https://doi.org/10.1016/j.laa.2026.07.018; preprint arXiv:2505.24072, https://arxiv.org/abs/2505.24072