Maximizing subgraph density in graphs of bounded degree and clique number
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916900905156608 |
|---|---|
| author | Kirsch, Rachel |
| author_facet | Kirsch, Rachel |
| contents | We asymptotically determine the maximum density of subgraphs isomorphic to $H$, where $H$ is any graph containing a dominating vertex, in graphs $G$ on $n$ vertices with bounded maximum degree and bounded clique number. That is, we asymptotically determine the constant $c=c(H,Δ,ω)$ such that ex$(n,H,\{K_{1,Δ+1},K_{ω+1}\})=(1-o_n(1))cn$ where $ω$ is sufficiently large.
Following recent interest in the corresponding parameter mex$(m,H,F)$ where where we fix the number of edges $m$ instead of the number of vertices $n$ of the graph, we determine the asymptotics of mex$(m,H,\{K_{1,1,Δ+1},K_{ω+1}\})$ when $H$ has at least two dominating vertices.
We obtain these results via a uniform proof of a common technical generalization of both, where we fix the number of $u$-cliques in the graph. This general result may be of independent interest.
Then we localize these results, proving a tight inequality involving the sizes of the locally largest cliques and complete split graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_10290 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximizing subgraph density in graphs of bounded degree and clique number Kirsch, Rachel Combinatorics 05C35 We asymptotically determine the maximum density of subgraphs isomorphic to $H$, where $H$ is any graph containing a dominating vertex, in graphs $G$ on $n$ vertices with bounded maximum degree and bounded clique number. That is, we asymptotically determine the constant $c=c(H,Δ,ω)$ such that ex$(n,H,\{K_{1,Δ+1},K_{ω+1}\})=(1-o_n(1))cn$ where $ω$ is sufficiently large. Following recent interest in the corresponding parameter mex$(m,H,F)$ where where we fix the number of edges $m$ instead of the number of vertices $n$ of the graph, we determine the asymptotics of mex$(m,H,\{K_{1,1,Δ+1},K_{ω+1}\})$ when $H$ has at least two dominating vertices. We obtain these results via a uniform proof of a common technical generalization of both, where we fix the number of $u$-cliques in the graph. This general result may be of independent interest. Then we localize these results, proving a tight inequality involving the sizes of the locally largest cliques and complete split graphs. |
| title | Maximizing subgraph density in graphs of bounded degree and clique number |
| topic | Combinatorics 05C35 |
| url | https://arxiv.org/abs/2504.10290 |