2025/10/28 by Bodnár, Levente, Pikhurko, Oleg · 1 citation
#05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.24336
For a graph H whose edges are coloured blue or red, the H-semi-inducibility problem asks for the maximum, over all graphs G of given order n, of the number of injections from the vertex set of H into the vertex set of G that send red (resp. blue) edges of H to edges (resp. non-edges) of G. We consider all possible 4-vertex non-complete graphs H and essentially resolve all remaining cases except when H is the 3-edge path coloured blue-blue-red in this order (or is equivalent to this case). Some of our proofs are computer-generated, using the flag algebra method of Razborov.