What the study found
The study shows that the edge version of inducibility for any graph H satisfies ρ(H,m) = Θ(m^α_f(H)), where α_f(H) is the fractional independence number of H. The authors also give additional bounds and conjectures for paths and cycles.
Why the authors say this matters
The authors indicate that this result shifts attention from the growth rate itself to the constant factor in front of m^α_f(H). They also suggest that their path and cycle results help clarify the edge-version inducibility problem for these graph families.
What the researchers tested
The researchers studied the maximum number of induced copies of a graph H in a graph with m edges, writing this quantity as ρ(H,m). They used the entropy method, and they focused especially on cycles C_k and paths P_k.
What worked and what didn't
They prove the general asymptotic form ρ(H,m) = Θ(m^α_f(H)). For cycles, they conjecture that for any k ≥ 5, ρ(C_k,m) = (1+o(1))(m/k)^(k/2), with the bound achieved by the blow up of C_k; for even cycles, they establish an upper bound with an extra constant factor, and for odd cycles, an upper bound with an extra factor depending on k. For paths, they prove ρ(P_{2l},m) ≤ m^l / [2(l-1)^(l-1)] and ρ(P_{2l+1},m) ≤ m^(l+1) / [4l^l], and they also conjecture the asymptotic value of ρ(P_k,m).
What to keep in mind
The abstract does not provide full proofs of the cycle and path conjectures, only stated conjectures and upper bounds. It also does not describe limitations beyond the scope of cycles and paths, so the available summary is limited to those graph families.
Key points
- For any graph H, the edge-version inducibility grows as Θ(m^α_f(H)).
- The exponent in that growth is the fractional independence number of H.
- For cycles C_k with k ≥ 5, the authors conjecture an asymptotic formula involving (m/k)^(k/2).
- For even cycles, the paper establishes an upper bound with an extra constant factor.
- For paths, the paper proves explicit upper bounds for P_{2l} and P_{2l+1}.
Disclosure
- Research title:
- Edge version of graph inducibility is determined by fractional independence number
- Authors:
- Yichen Wang, Xiamiao Zhao, Mei Lu
- Institutions:
- Tsinghua University
- Publication date:
- 2026-04-23
- DOI:
- 10.37236/14422
- OpenAlex record:
- View
- Image credit:
- Photo by Sergey Meshkov on Pexels · Pexels License
Get the weekly research newsletter
Stay current with peer-reviewed research without reading academic papers — one filtered digest, every Friday.