Thursday, February 28, 2019 3:00 PM
Lisa Sauermann (Stanford)

Abstract: Given a fixed graph H and a (large) integer n, what are the n-vertex graphs with the maximum number of induced copies of H? In this talk, we discuss this question for random Cayley graphs of an abelian group. More generally, we also discuss the case where H is a graph obtained from a random Cayley graph Ĥ by deleting a small number of vertices. We prove that in this case almost surely all graphs on a given number of vertices that maximize the number of induced copies of H are balanced iterated blow-ups of the original Cayley graph Ĥ (and interestingly, not of the graph H itself). Joint work with Jacob Fox and Fan Wei.