Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.03544 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918045399646208 |
|---|---|
| author | Reed, Bruce |
| author_facet | Reed, Bruce |
| contents | One way to certify that a graph does not contain an induced cycle of length six is to provide a partition of its vertex set into (i) a stable set, and (ii) a graph containing no stable set of size three and no induced matching of size two. We show that almost every graph which does not contain a cycle of length six as an induced subgraph has such a certificate. We obtain similar characterizations of the structure of almost all graphs which contain no induced cycle of length $k$ for all even $k$ exceeding six. (Similar results were obtained for $k=3$ by Erdos, Kleitman, and Rothschild in 1976, for $k =4,5$ by Promel and Steger in 1991 and for odd $k$ exceeding 5 by Balogh and Butterfield in 2009.) We prove that a simiiar theorem for all $H$ holds up to the deletion of a set of $o(|V(G)|)$ vertices and ask for which $H$ the characterization holds fully. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03544 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Global Structure of a Typical Graph Without $H$ as an Induced Subgraph when $H$ is a Cycle Reed, Bruce Combinatorics One way to certify that a graph does not contain an induced cycle of length six is to provide a partition of its vertex set into (i) a stable set, and (ii) a graph containing no stable set of size three and no induced matching of size two. We show that almost every graph which does not contain a cycle of length six as an induced subgraph has such a certificate. We obtain similar characterizations of the structure of almost all graphs which contain no induced cycle of length $k$ for all even $k$ exceeding six. (Similar results were obtained for $k=3$ by Erdos, Kleitman, and Rothschild in 1976, for $k =4,5$ by Promel and Steger in 1991 and for odd $k$ exceeding 5 by Balogh and Butterfield in 2009.) We prove that a simiiar theorem for all $H$ holds up to the deletion of a set of $o(|V(G)|)$ vertices and ask for which $H$ the characterization holds fully. |
| title | The Global Structure of a Typical Graph Without $H$ as an Induced Subgraph when $H$ is a Cycle |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.03544 |