Forcing Graphs to be Forcing
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929635331145728 |
|---|---|
| author | Kiem, Aldo Parczyk, Olaf Spiegel, Christoph |
| author_facet | Kiem, Aldo Parczyk, Olaf Spiegel, Christoph |
| contents | Sidorenko's conjecture states that the number of copies of any given bipartite graph in another graph of given density is asymptotically minimized by a random graph. The forcing conjecture further strengthens this, claiming that any minimizer in fact needs to be quasi-random. Here we extend the family of bipartite graphs for which the forcing conjecture is known to hold to include balanced blow-ups of Sidorenko graphs and subdivisions of Sidorenko graphs by a forcing graph. This partially generalizes results by Conlon et al. (2018) and Conlon and Lee (2021). We also show that the box product of a Sidorenko graph with an edge is forcing, partially generalizing results of Kim, Lee, and Lee (2016) and, in particular, showing that cubes are forcing. We achieve these results through algebraic arguments building on Razborov's flag algebra framework (2007). This approach additionally allows us to construct Sidorenko hypergraphs from known 2-uniform Sidorenko graphs and to study forcing pairs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_12904 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Forcing Graphs to be Forcing Kiem, Aldo Parczyk, Olaf Spiegel, Christoph Combinatorics 05C35, 05C25, 05C76, 05C80 Sidorenko's conjecture states that the number of copies of any given bipartite graph in another graph of given density is asymptotically minimized by a random graph. The forcing conjecture further strengthens this, claiming that any minimizer in fact needs to be quasi-random. Here we extend the family of bipartite graphs for which the forcing conjecture is known to hold to include balanced blow-ups of Sidorenko graphs and subdivisions of Sidorenko graphs by a forcing graph. This partially generalizes results by Conlon et al. (2018) and Conlon and Lee (2021). We also show that the box product of a Sidorenko graph with an edge is forcing, partially generalizing results of Kim, Lee, and Lee (2016) and, in particular, showing that cubes are forcing. We achieve these results through algebraic arguments building on Razborov's flag algebra framework (2007). This approach additionally allows us to construct Sidorenko hypergraphs from known 2-uniform Sidorenko graphs and to study forcing pairs. |
| title | Forcing Graphs to be Forcing |
| topic | Combinatorics 05C35, 05C25, 05C76, 05C80 |
| url | https://arxiv.org/abs/2412.12904 |