2025/07/02 by Bodnár, Levente, Pikhurko, Oleg · 5 citations
#05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.01596
The (κ,ℓ)-edge-inducibility problem asks for the maximum number of κ-subsets inducing exactly ℓ edges that a graph of given order n can have. Using flag algebras and stability approach, we resolve this problem for all sufficiently large n (including a description of all extremal and almost extremal graphs) in eleven new non-trivial cases when κ≤ 7. We also compute the F-inducibility constant (the asymptotically maximum density of induced copies of F in a graph of given order n) and obtain some corresponding structure results for three new graphs F with 5 vertices: the 3-edge star plus an isolated vertex, the 4-cycle plus an isolated vertex, and the 4-cycle with a pendant edge.