Sidorenko's conjecture, graph norms, and pseudorandomness
<p>This thesis is primarily concerned with correlation inequalities between the number of homomorphic copies of different graphs. In particular, many of the results relate to a beautiful conjecture of Sidorenko, which roughly states that the number of copies of a bipartite graph H in a gra...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
2017
|
| Subjects: |
| _version_ | 1797069479421673472 |
|---|---|
| author | Lee, J |
| author2 | Conlon, D |
| author_facet | Conlon, D Lee, J |
| author_sort | Lee, J |
| collection | OXFORD |
| description | <p>This thesis is primarily concerned with correlation inequalities between the number of homomorphic copies of different graphs. In particular, many of the results relate to a beautiful conjecture of Sidorenko, which roughly states that the number of copies of a bipartite graph H in a graph G is asymptotically minimised when G is the Erdos Reyni random graph.</p> <p>The first part of the thesis discusses recent approaches to attack Sidorenko's conjecture. We firstly prove that every graph that admits a special kind of tree decomposition satisfies the conjecture. The proof explicitly uses information theory, which also leads to a general tool for counting fixed graphs that are decomposable in analogous ways. A recursive approach to the conjecture, using Cartesian products of graphs, will also be discussed. We show that the class of graphs that satisfy the conjecture is closed under taking Cartesian products with either trees or even cycles.</p> <p>The second part studies a conjecture of Kohayakawa, Nagle, Rodl, and Schacht, which states that we have a random-like lower count for any graph H in G whenever G is locally dense, i.e., a fixed edge density is guaranteed for every large enough vertex subset. This conjecture is closely related to Sidorenko's conjecture in the sense that it is true for every bipartite graph H that satisfies Sidorenko's conjecture. We prove a partial converse, stating that if H satisfies the Kohayakawa-Nagle-Rodl-Schacht conjecture, then replacing edges of H by internally disjoint paths of length two gives an instance of Sidorenko's conjecture. We also prove some new instances of the Kohayakawa-Nagle-Rodl-Schacht conjecture by adding extra ideas to the information theoretic approach previously discussed.</p> |
| first_indexed | 2024-03-06T22:25:04Z |
| format | Thesis |
| id | oxford-uuid:5666a58e-77ae-4709-a41e-587cf176840a |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:25:04Z |
| publishDate | 2017 |
| record_format | dspace |
| spelling | oxford-uuid:5666a58e-77ae-4709-a41e-587cf176840a2022-03-26T16:49:59ZSidorenko's conjecture, graph norms, and pseudorandomnessThesishttp://purl.org/coar/resource_type/c_db06uuid:5666a58e-77ae-4709-a41e-587cf176840aMathematicsORA Deposit2017Lee, JConlon, D<p>This thesis is primarily concerned with correlation inequalities between the number of homomorphic copies of different graphs. In particular, many of the results relate to a beautiful conjecture of Sidorenko, which roughly states that the number of copies of a bipartite graph H in a graph G is asymptotically minimised when G is the Erdos Reyni random graph.</p> <p>The first part of the thesis discusses recent approaches to attack Sidorenko's conjecture. We firstly prove that every graph that admits a special kind of tree decomposition satisfies the conjecture. The proof explicitly uses information theory, which also leads to a general tool for counting fixed graphs that are decomposable in analogous ways. A recursive approach to the conjecture, using Cartesian products of graphs, will also be discussed. We show that the class of graphs that satisfy the conjecture is closed under taking Cartesian products with either trees or even cycles.</p> <p>The second part studies a conjecture of Kohayakawa, Nagle, Rodl, and Schacht, which states that we have a random-like lower count for any graph H in G whenever G is locally dense, i.e., a fixed edge density is guaranteed for every large enough vertex subset. This conjecture is closely related to Sidorenko's conjecture in the sense that it is true for every bipartite graph H that satisfies Sidorenko's conjecture. We prove a partial converse, stating that if H satisfies the Kohayakawa-Nagle-Rodl-Schacht conjecture, then replacing edges of H by internally disjoint paths of length two gives an instance of Sidorenko's conjecture. We also prove some new instances of the Kohayakawa-Nagle-Rodl-Schacht conjecture by adding extra ideas to the information theoretic approach previously discussed.</p> |
| spellingShingle | Mathematics Lee, J Sidorenko's conjecture, graph norms, and pseudorandomness |
| title | Sidorenko's conjecture, graph norms, and pseudorandomness |
| title_full | Sidorenko's conjecture, graph norms, and pseudorandomness |
| title_fullStr | Sidorenko's conjecture, graph norms, and pseudorandomness |
| title_full_unstemmed | Sidorenko's conjecture, graph norms, and pseudorandomness |
| title_short | Sidorenko's conjecture, graph norms, and pseudorandomness |
| title_sort | sidorenko s conjecture graph norms and pseudorandomness |
| topic | Mathematics |
| work_keys_str_mv | AT leej sidorenkosconjecturegraphnormsandpseudorandomness |