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!
|
| _version_ | 1866916496579493888 |
|---|---|
| author | Ueltzen, Richard |
| author_facet | Ueltzen, Richard |
| 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_17362 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Characterizing graphs with high inducibility Ueltzen, Richard Combinatorics 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$. |
| title | Characterizing graphs with high inducibility |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.17362 |