Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.17362 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- For a positive integer $k$ and a graph $H$ on $k$ vertices, we are interested in the inducibility of $H$, denoted $\mathrm{ind}(H)$, which is defined as the maximum possible probability that choosing $k$ vertices uniformly at random from a large graph $G$, they induce a copy of $H$. It follows from the resolved Edge-statistics conjecture that if $H \not \in \{K_k, \bar K_k\}$, then $\mathrm{ind}(H) \leq 1 / e + o_k(1)$. Equality holds for the star graph $K_{1, k-1}$, the graph with a single edge on $k$ vertices and their complements. We prove that for all other graphs $H$, we have $\mathrm{ind}(H) \leq c + o_k(1)$ for an absolute constant $c < 1 / e$. Moreover, we explicitly characterize all graphs with inducibility bounded away from zero. Namely, we show that this is the class of graphs $H$ for which there is a set $V_0 \subseteq V(H)$ of bounded size with the property that all permutations of $V(H) \backslash V_0$ extend to an automorphism of $H$.