What the study found
The authors show that, for any graph H, the maximum number of induced copies in a graph with m edges grows like a constant times m raised to the fractional independence number of H. For cycles and paths, they give additional bounds and conjectures about the asymptotic constant.
Why the authors say this matters
The study suggests that understanding the edge-based version of inducibility can be reduced to a power-law growth rate determined by a graph invariant called the fractional independence number. The authors also indicate that the constant factor in front of this main term is an important remaining question for cycles and paths.
What the researchers tested
The researchers studied the edge version of inducibility, where the question is how many induced copies of a graph H can appear in a graph with exactly m edges. They used the entropy method and focused especially on cycles C_k and paths P_k.
What worked and what didn't
They prove that rho(H, m) = Theta(m^{alpha_f(H)}) for any graph H, where alpha_f(H) is the fractional independence number. For cycles, they conjecture an asymptotic formula for k >= 5, prove an upper bound with an extra constant factor for even cycles, and only an upper bound with an extra factor depending on k for odd cycles. For paths, they prove rho(P_{2l}, m) <= m^l / [2(l-1)^{l-1}] and rho(P_{2l+1}, m) <= m^{l+1} / [4l^l], and they also conjecture the asymptotic value of rho(P_k, m).
What to keep in mind
The abstract does not provide full proofs or specify whether the conjectures are resolved. The paper gives exact asymptotic order for all graphs, but the sharper constant-factor behavior is only partially established for cycles and paths.
- For any graph H, the edge version of inducibility grows on the order of m raised to the fractional independence number of H.
- The paper focuses on the constant factor in front of this growth rate for cycles and paths.
- For cycles C_k with k >= 5, the authors conjecture an asymptotic formula and say the bound is achieved by the blow up of C_k.
- For even cycles, the authors establish an upper bound with an extra constant factor; for odd cycles, the extra factor depends on k.
- For paths P_{2l} and P_{2l+1}, the paper gives explicit upper bounds in terms of m and l.
- The entropy method is the main tool used in the paper.
