The Inducibility of Graphs on Four Vertices |
| |
Authors: | James Hirst |
| |
Institution: | SCHOOL OF COMPUTER SCIENCE, MCGILL UNIVERSITY, MONTREAL, CANADA |
| |
Abstract: | We consider the problem of determining the maximum induced density of a graph H in any graph on n vertices. The limit of this density as n tends to infinity is called the inducibility of H. The exact value of this quantity is known only for a handful of small graphs and a specific set of complete multipartite graphs. Answering questions of Brown–Sidorenko and Exoo, we determine the inducibility of K1, 1, 2 and the paw graph. The proof is obtained using semidefinite programming techniques based on a modern language of extremal graph theory, which we describe in full detail in an accessible setting. |
| |
Keywords: | graph inducibility extremal graph theory partially labeled graphs semidefinite programming |
|
|