Mathematical Computer Science Seminar
Dhruv Mubayi
UIC
The number of induced subgraphs
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.
Monday October 6, 2025 at 3:00 PM in 1227 SEO