Subgraph densities in a surface
arXiv:2003.13777 · doi:10.1017/S0963548321000560
Abstract
Given a fixed graph that embeds in a surface , what is the maximum number of copies of in an -vertex graph that embeds in ? We show that the answer is , where is a graph invariant called the `flap-number' of , which is independent of . This simultaneously answers two open problems posed by Eppstein (1993). When is a complete graph we give more precise answers.
arXiv commentv4: referee's comments implemented. v3: proof of the main theorem fully rewritten, fixes a serious error in the previous version found by Kevin Hendrey
References in corpus (14)
- The Clique Density Theorem
- Counting copies of a fixed subgraph in -free graphs
- On the maximum number of cliques in a graph
- Rank-width and Tree-width of H-minor-free Graphs
- Irreducible triangulations of low genus surfaces
- Generating irreducible triangulations of surfaces
- A unified approach to structural limits, and limits of graphs with bounded tree-depth
- The maximum number of cliques in a graph embedded in a surface
- Irreducible Triangulations are Small
- Number of cliques in graphs with a forbidden subdivision
- Tree densities in sparse graph classes
- The maximum number of copies in -free graphs
- Homomorphism counts in robustly sparse graphs
- On paths, stars and wyes in trees