Graph reconstruction and structure
<p>This thesis explores the difficulties of capturing graph structure, and the recent approaches that have been able to do so effectively in some settings.</p> <p>The famous Graph Reconstruction Conjecture (Kelly-Ulam, 1941) states that every graph on at least 3 vertices is unique...
| Huvudupphovsman: | |
|---|---|
| Övriga upphovsmän: | |
| Materialtyp: | Lärdomsprov |
| Språk: | English |
| Publicerad: |
2023
|
| Ämnen: |
| _version_ | 1826314598308904960 |
|---|---|
| author | Tan, J |
| author2 | Scott, A |
| author_facet | Scott, A Tan, J |
| author_sort | Tan, J |
| collection | OXFORD |
| description | <p>This thesis explores the difficulties of capturing graph structure, and the recent approaches that have been able to do so effectively in some settings.</p>
<p>The famous Graph Reconstruction Conjecture (Kelly-Ulam, 1941) states that every graph on at least 3 vertices is uniquely determined by its deck of vertex-deleted subgraphs. Despite sustained efforts, it remains wide open. In Part I, we break new ground on several variants of this reconstruction problem. Two such settings are even harder than the classical case; we reconstruct graphs or their properties from decks of k-vertex-deleted subgraphs as well as from incomplete decks where l subgraphs are missing. While most general results in literature only apply when k and l are small constants, in both cases we develop techniques that facilitate significant leaps to even handle deficits that are linear in the number of vertices. For the third variant, we introduce axioms to define a family of reconstruction problems in which decks are defined by ‘switching’ at a vertex instead of deletions. This encompasses a well-known problem of Stanley from 1985. Our key result is a new sufficient condition for switching-reconstructibility that applies under this generic framework.</p>
<p>Part II examines the problem of formulating approximate characterisations of graphs in terms of simpler building blocks. A recent focal point has been on graph product structure theory, which allows many graph classes to be described using graphs of bounded treewidth. Having first appeared in 2019, this theory is still actively under development, but has already facilitated progress on longstanding problems. As a new application in the intersection of structural and geometric graph theory, we use it to prove that all proper minor-closed classes of graphs have touching representations by comparable boxes in bounded dimensions. We also show that product structure can, in turn, describe the bounded treewidth building blocks from the original theorems using even simpler parts.</p> |
| first_indexed | 2024-03-07T08:02:00Z |
| format | Thesis |
| id | oxford-uuid:5b6d514c-241f-4a77-8fa2-55fd069df278 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:09:32Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | oxford-uuid:5b6d514c-241f-4a77-8fa2-55fd069df2782024-09-30T07:55:18ZGraph reconstruction and structureThesishttp://purl.org/coar/resource_type/c_db06uuid:5b6d514c-241f-4a77-8fa2-55fd069df278CombinatoricsGraph theoryEnglishHyrax Deposit2023Tan, JScott, A<p>This thesis explores the difficulties of capturing graph structure, and the recent approaches that have been able to do so effectively in some settings.</p> <p>The famous Graph Reconstruction Conjecture (Kelly-Ulam, 1941) states that every graph on at least 3 vertices is uniquely determined by its deck of vertex-deleted subgraphs. Despite sustained efforts, it remains wide open. In Part I, we break new ground on several variants of this reconstruction problem. Two such settings are even harder than the classical case; we reconstruct graphs or their properties from decks of k-vertex-deleted subgraphs as well as from incomplete decks where l subgraphs are missing. While most general results in literature only apply when k and l are small constants, in both cases we develop techniques that facilitate significant leaps to even handle deficits that are linear in the number of vertices. For the third variant, we introduce axioms to define a family of reconstruction problems in which decks are defined by ‘switching’ at a vertex instead of deletions. This encompasses a well-known problem of Stanley from 1985. Our key result is a new sufficient condition for switching-reconstructibility that applies under this generic framework.</p> <p>Part II examines the problem of formulating approximate characterisations of graphs in terms of simpler building blocks. A recent focal point has been on graph product structure theory, which allows many graph classes to be described using graphs of bounded treewidth. Having first appeared in 2019, this theory is still actively under development, but has already facilitated progress on longstanding problems. As a new application in the intersection of structural and geometric graph theory, we use it to prove that all proper minor-closed classes of graphs have touching representations by comparable boxes in bounded dimensions. We also show that product structure can, in turn, describe the bounded treewidth building blocks from the original theorems using even simpler parts.</p> |
| spellingShingle | Combinatorics Graph theory Tan, J Graph reconstruction and structure |
| title | Graph reconstruction and structure |
| title_full | Graph reconstruction and structure |
| title_fullStr | Graph reconstruction and structure |
| title_full_unstemmed | Graph reconstruction and structure |
| title_short | Graph reconstruction and structure |
| title_sort | graph reconstruction and structure |
| topic | Combinatorics Graph theory |
| work_keys_str_mv | AT tanj graphreconstructionandstructure |