Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.12418 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910493003743232 |
|---|---|
| author | Bradač, Domagoj Sudakov, Benny Wigderson, Yuval |
| author_facet | Bradač, Domagoj Sudakov, Benny Wigderson, Yuval |
| contents | A graph $G$ is said to be $p$-locally dense if every induced subgraph of $G$ with linearly many vertices has edge density at least $p$. A famous conjecture of Kohayakawa, Nagle, Rödl, and Schacht predicts that locally dense graphs have, asymptotically, at least as many copies of any fixed graph $H$ as are found in a random graph of edge density $p$.
In this paper, we prove several results around the KNRS conjecture. First, we prove that certain natural gluing operations on $H$ preserve this property, thus proving the conjecture for many graphs $H$ for which it was previously unknown. Secondly, we study a stability version of this conjecture, and prove that for many graphs $H$, approximate equality is attained in the KNRS conjecture if and only if the host graph $G$ is quasirandom. Finally, we introduce a weakening of the KNRS conjecture, which requires the host graph to be nearly degree-regular, and prove this conjecture for a larger family of graphs. Our techniques reveal a surprising connection between these questions, semidefinite optimization, and the study of copositive matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_12418 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Counting subgraphs in locally dense graphs Bradač, Domagoj Sudakov, Benny Wigderson, Yuval Combinatorics A graph $G$ is said to be $p$-locally dense if every induced subgraph of $G$ with linearly many vertices has edge density at least $p$. A famous conjecture of Kohayakawa, Nagle, Rödl, and Schacht predicts that locally dense graphs have, asymptotically, at least as many copies of any fixed graph $H$ as are found in a random graph of edge density $p$. In this paper, we prove several results around the KNRS conjecture. First, we prove that certain natural gluing operations on $H$ preserve this property, thus proving the conjecture for many graphs $H$ for which it was previously unknown. Secondly, we study a stability version of this conjecture, and prove that for many graphs $H$, approximate equality is attained in the KNRS conjecture if and only if the host graph $G$ is quasirandom. Finally, we introduce a weakening of the KNRS conjecture, which requires the host graph to be nearly degree-regular, and prove this conjecture for a larger family of graphs. Our techniques reveal a surprising connection between these questions, semidefinite optimization, and the study of copositive matrices. |
| title | Counting subgraphs in locally dense graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.12418 |