The semi-inducibility problem
Connections Workshop: Extremal Combinatorics February 06, 2025 - February 07, 2025
Location: SLMath: Eisenbud Auditorium, Online/Virtual
Primary Mathematics Subject Classification
No Primary AMS MSC
Secondary Mathematics Subject Classification
No Secondary AMS MSC
Let $H$ be a $k$-edge-coloured graph and let $n$ be a positive integer. What is the maximum number of copies of $H$ in a $k$-edge-coloured complete graph on $n$ vertices? We investigate this problem in the case of $k=2$ colours, which has close ties to the inducibility problem of Pippenger and Golumbic. We prove sharp or almost sharp results for alternating walks, for alternating cycles of length divisible by 4, and for 4-cycles of every colour pattern.
This is joint work with Abdul Basit, Daniel Horsley, André Kündgen, and Katherine Staden