Structure for algorithms, graph reconstruction and hypercube intersections
<p>We begin by studying several structural properties of graphs that lead to 'efficient' colouring algorithms. We first show that the treedepth of a <em>P<sub>t</sub></em>-free graph is bounded by <em>t</em> times its maximum degree, and use this t...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2020
|
| Subjects: |
| _version_ | 1817932726212231168 |
|---|---|
| author | Groenland, C |
| author2 | Scott, A |
| author_facet | Scott, A Groenland, C |
| author_sort | Groenland, C |
| collection | OXFORD |
| description | <p>We begin by studying several structural properties of graphs that lead to 'efficient' colouring algorithms. We first show that the treedepth of a <em>P<sub>t</sub></em>-free graph is bounded by <em>t</em> times its maximum degree, and use this to show that the number of 3-colourings can be computed in time O(2√<sup>tn log(n)</sup>) for any <em>P<sub>t</sub></em>-free graph on n vertices. We then prove that several graph classes, including the class of planar graphs, have asymptotic dimension 2. This has applications to graph colouring and partitioning schemes. We end this part by studying when a 'connected' greedy procedure for colouring the edges of a graph can find an optimal colouring.</p>
<p>In the second part, we consider extremal questions on the reconstruction of graph parameters. The deck of cards of a graph G is given by the multiset {G-v:v ∈ V(G)} of induced subgraphs of order n-1. A graph parameter f can be reconstructed if any two graphs G and H with the same deck of cards satisfy f(G)=f(H). For n sufficiently large, we show that the number of edges of a graph on n vertices is determined by any subdeck containing at least n- 1/12 √n cards. For planar graphs, we can reconstruct not only the number of edges, but also the degree sequence, even if a linear number of cards is missing. We then turn our attention to a set-up where rather than missing cards from the deck, the cards are 'smaller', and we consider the problem of reconstructing the degree sequence and recognising connectivity. In all cases, we significantly improve the best-known bounds. </p>
<p>Finally, we turn to the study of intersection patterns in the hypercube. We investigate the possible intersection sizes a k-dimensional linear subspace can have with the hypercube {0,1}<sup>n</sup>. For fixed k and arbitrary n, the intersection size must be between 1 and 2<sup>k</sup>. We exactly determine the possible intersection sizes larger than 2<sup>k-1</sup> for every n, settling a conjecture of Melo and Winter, and then disprove a second conjecture of Melo and Winter by showing that a positive proportion of the intersection sizes smaller than 2<sup>k-1</sup> are impossible to obtain.
After that, we give some partial progress towards the problem of determining the minimum number of hyperplanes required to cover a subset B⊆{0,1}<sup>n</sup> without covering any point from {0,1}<sup>n</sup> \ <em>B</em>.</p> |
| first_indexed | 2024-03-06T20:49:02Z |
| format | Thesis |
| id | oxford-uuid:36f1bce5-4506-4ed7-a953-d3291c90c721 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:42:29Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | oxford-uuid:36f1bce5-4506-4ed7-a953-d3291c90c7212024-12-07T13:36:33ZStructure for algorithms, graph reconstruction and hypercube intersectionsThesishttp://purl.org/coar/resource_type/c_db06uuid:36f1bce5-4506-4ed7-a953-d3291c90c721MathematicsGraph theoryAlgorithmsEnglishHyrax Deposit2020Groenland, CScott, AScott, AMcDiarmid, CLeader, I<p>We begin by studying several structural properties of graphs that lead to 'efficient' colouring algorithms. We first show that the treedepth of a <em>P<sub>t</sub></em>-free graph is bounded by <em>t</em> times its maximum degree, and use this to show that the number of 3-colourings can be computed in time O(2√<sup>tn log(n)</sup>) for any <em>P<sub>t</sub></em>-free graph on n vertices. We then prove that several graph classes, including the class of planar graphs, have asymptotic dimension 2. This has applications to graph colouring and partitioning schemes. We end this part by studying when a 'connected' greedy procedure for colouring the edges of a graph can find an optimal colouring.</p> <p>In the second part, we consider extremal questions on the reconstruction of graph parameters. The deck of cards of a graph G is given by the multiset {G-v:v ∈ V(G)} of induced subgraphs of order n-1. A graph parameter f can be reconstructed if any two graphs G and H with the same deck of cards satisfy f(G)=f(H). For n sufficiently large, we show that the number of edges of a graph on n vertices is determined by any subdeck containing at least n- 1/12 √n cards. For planar graphs, we can reconstruct not only the number of edges, but also the degree sequence, even if a linear number of cards is missing. We then turn our attention to a set-up where rather than missing cards from the deck, the cards are 'smaller', and we consider the problem of reconstructing the degree sequence and recognising connectivity. In all cases, we significantly improve the best-known bounds. </p> <p>Finally, we turn to the study of intersection patterns in the hypercube. We investigate the possible intersection sizes a k-dimensional linear subspace can have with the hypercube {0,1}<sup>n</sup>. For fixed k and arbitrary n, the intersection size must be between 1 and 2<sup>k</sup>. We exactly determine the possible intersection sizes larger than 2<sup>k-1</sup> for every n, settling a conjecture of Melo and Winter, and then disprove a second conjecture of Melo and Winter by showing that a positive proportion of the intersection sizes smaller than 2<sup>k-1</sup> are impossible to obtain. After that, we give some partial progress towards the problem of determining the minimum number of hyperplanes required to cover a subset B⊆{0,1}<sup>n</sup> without covering any point from {0,1}<sup>n</sup> \ <em>B</em>.</p> |
| spellingShingle | Mathematics Graph theory Algorithms Groenland, C Structure for algorithms, graph reconstruction and hypercube intersections |
| title | Structure for algorithms, graph reconstruction and hypercube intersections |
| title_full | Structure for algorithms, graph reconstruction and hypercube intersections |
| title_fullStr | Structure for algorithms, graph reconstruction and hypercube intersections |
| title_full_unstemmed | Structure for algorithms, graph reconstruction and hypercube intersections |
| title_short | Structure for algorithms, graph reconstruction and hypercube intersections |
| title_sort | structure for algorithms graph reconstruction and hypercube intersections |
| topic | Mathematics Graph theory Algorithms |
| work_keys_str_mv | AT groenlandc structureforalgorithmsgraphreconstructionandhypercubeintersections |