Dhruv Mubayi : The number of induced subgraphs

Posted by Vishesh Jain , part of the Mathematical Computer Science Seminar.

At

Oct. 6, 2025, 3 p.m.

In

1227 SEO

Abstract

We consider the following general question that encompasses some of the most celebrated theorems in Combinatorics. Given a small graph H and a large graph G with density x, what is the possible number of induced subgraphs of G that are isomorphic to H. A complete answer is known only in the case when H is a clique or a two edge star (and their complements). We will discuss some general theory around this problem and then focus on some specific H. This is joint work with Xizhi Liu and Christian Reiher.