{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/334185"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/334185","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Combinatorics and Metric Geometry","abstract":"This thesis consists of an introduction and seven chapters, each devoted to a different combinatorial problem. In Chapters 1 and 2, we consider the main subject of this thesis; the sharp stability of the Brunn-Minkowski inequality (BM). This celebrated theorem from the 19th century asserts that for bodies A,B $\\subset$ $\\mathbb{R}$$^{k}$, we have |A + B|$^{1/k}$ $\\geq$ |A|$^{1/k}$ + |B|$^{1/k}$, where |$\\cdot$| is the Lebesgue measure and A + B := {a + b : a $\\in$ A, b $\\in$ B} is the Minkowski sum. Moreover, we have equality if and only if A,B are homothetic convex sets. The stability question, studied in many papers, asks how the distance to equality in BM relates to the distance from A,B to homothetic convex sets. In particular, given Brunn-Minkowsi deficit $\\delta$ := |A+B|$^{1/k}$ / |A|$^{1/k}$ + |B|$^{1/k}$ -1, and normalized volume ratio $\\textit{t}$ := |A|$^{1/k}$ / |A|$^{1/k}$ + |B|$^{1/k}$, what is the best bound one can find on $\\omega$ := |K$_{A}$ \\ A| / |A| + |K$_{B}$ \\ B| / |B|, where K$_{A}$ $\\supset$ A, and K$_{B}$ $\\supset$ B are homothetic convex sets of minimal size? In Chapter 2, we prove a conjecture by Figalli and Jerison establishing the sharp stability for homothetic sets. In particular, we show that for homothetic sets, we have $\\omega$ = O$_{k}$($\\delta$t$^{-1}$), for $\\delta$ sufficiently small. In Chapter 3, we establish the sharp stability for planar sets, i.e. we show that for planar sets and $\\delta$ sufficiently small, we have $\\omega$ = O($\\delta$$^{1/2}$t$^{-1/2}$). A crucial result in Chapter 3 shows that for any $\\epsilon$ > 0, if $\\delta$ is sufficiently small, then we have |co(A + B) \\ (A + B)| $\\leq$ (1 + $\\epsilon$)(|co(A) \\ A| + |co(B) \\ B|). In Chapter 4, we consider a reconstruction problem for functions on graphs. Given a function $\\textit{f}$:V(G) $\\rightarrow$ [k] on the vertices of a graph G and a random walk (U$_{i}$)$^{{\\infty}}_{i = 1}$ on that graph, can we reconstruct $\\textit{f}$ (up to automorphisms) based on just ($\\textit{f}$(U$_{i}$)$^{{\\infty}}_{i = 1}$? Gross and Grupel showed this was not generally possible on the hypercube, by constructing non-isomorphic $\\textit{locally p-biased}$ sets $\\textit{X}$, so that for each vertex $\\textit{v}$ the fraction of neighbours which is in $\\textit{X}$ is exactly $\\textit{p}$. Answering a question of Gross and Grupel, we construct uncountably many non-isomorphic partitions of $\\mathbb{Z}$$^{k}$ into 2k parts such that every element of $\\mathbb{Z}$$^{k}$ has exactly one neighbour in each part. As a result, we find $\\textit{locally p-biased}$ sets for all $\\textit{p = c/2n}$ with $\\textit{c}$ $\\in$ {0, ... , 2n}. In Chapter 5, we prove the complete graph case of the bunkbed conjecture. Given a graph G, let the bunkbed graph BB(G) be the graph G$\\Box$K$_{2}$, i.e. the graph obtained from considering two copies of G and connecting equivalent vertices with an edge. The bunkbed conjecture posed by Kasteleyn in 1985 asserts the very intuitive statement that when considering percolation with uniform parameter p, we have $\\mathbb{P}$(u$_{1}$ $\\leftrightarrow$ v$_{1}$) $\\geq$ $\\mathbb{P}$(u$_{1}$ $\\leftrightarrow$ v$_{2}$), i.e. a vertex has a higher probability of being connected to a vertex in the same copy of G than being connected to the equivalent vertex in the other copy of G. In Chapter 6, we consider the (t,r) broadcast domination number, a generalisation of the domination number in graphs. In this form of domination, we consider a set T $\\subset$ V(G) of towers which broadcast at strength t, where broadcast strength decays linearly with distance in the graph. A set of towers is (t,r) broadcast dominating if every vertex in the graph receives at least r signal from all towers combined. More formally, the (t,r) broadcast domination number of a graph G is the minimal cardinality of a set T $\\subset$ V(G) such that for every vertex v $\\in$ V(G), we have $^{{\\Sigma}}_{u {{\\in}} T}$ max{t - d(u,v),0} $\\geq$ r. Proving a conjecture by Drews, Harris, and Randolph, we establish that the minimal asymptotical density of (t,3) broadcasting subset of $\\mathbb{Z}$$^{2}$ is the same as the minimal asymptotical density of a (t-1,1) broadcasting subset of $\\mathbb{Z}$$^{2}$. In Chapter 7, we consider the eternal game chromatic number, a version of the game chromatic number in which the game continues after all vertices have been coloured. We show that with high probability $\\chi$$^\\infty_g$ (G$_{n,p}$) = (p/2 + o(1))n for odd n, and also for even n when p = 1/k for some k $\\in$ $\\mathbb{N}$. The upper bound applies for even n and any other value of p as well, but we conjecture in this case this upper bound is not sharp. Finally, we answer a question posed by Klostermeyer and Mendoza. In Chapter 8, we consider the bridge-burning cops and robbers game, a version of the game where after a robber moves over an edge, the edge is removed from the graph. Proving a generalization of a conjecture by Kinnersley and Peterson, we establish the asymptotically maximal capture time in this game for graphs with bridge-burning cops number at least three. In particular, we show that this maximal capture time grows as k$^{-O(k)}$n$^{k+2}$, where k $\\geq$ 3 is the bridge burning cop number and n is the number of vertices of the graph.","abstract_html":"This thesis consists of an introduction and seven chapters, each devoted to a different combinatorial problem. In Chapters 1 and 2, we consider the main subject of this thesis; the sharp stability of the Brunn-Minkowski inequality (BM). This celebrated theorem from the 19th century asserts that for bodies A,B $\\subset$ $\\mathbb{R}$<span class=\"etd-inline-math\"><sup>k</sup></span>, we have |A + B|<span class=\"etd-inline-math\"><sup>1/k</sup></span> $\\geq$ |A|<span class=\"etd-inline-math\"><sup>1/k</sup></span> + |B|<span class=\"etd-inline-math\"><sup>1/k</sup></span>, where |$\\cdot$| is the Lebesgue measure and A + B := {a + b : a $\\in$ A, b $\\in$ B} is the Minkowski sum. Moreover, we have equality if and only if A,B are homothetic convex sets. The stability question, studied in many papers, asks how the distance to equality in BM relates to the distance from A,B to homothetic convex sets. In particular, given Brunn-Minkowsi deficit <span class=\"etd-inline-math\">&delta;</span> := |A+B|<span class=\"etd-inline-math\"><sup>1/k</sup></span> / |A|<span class=\"etd-inline-math\"><sup>1/k</sup></span> + |B|<span class=\"etd-inline-math\"><sup>1/k</sup></span> -1, and normalized volume ratio <span class=\"etd-inline-math\"><em>t</em></span> := |A|<span class=\"etd-inline-math\"><sup>1/k</sup></span> / |A|<span class=\"etd-inline-math\"><sup>1/k</sup></span> + |B|<span class=\"etd-inline-math\"><sup>1/k</sup></span>, what is the best bound one can find on <span class=\"etd-inline-math\">&omega;</span> := |K<span class=\"etd-inline-math\"><sub>A</sub></span> \\ A| / |A| + |K<span class=\"etd-inline-math\"><sub>B</sub></span> \\ B| / |B|, where K<span class=\"etd-inline-math\"><sub>A</sub></span> $\\supset$ A, and K<span class=\"etd-inline-math\"><sub>B</sub></span> $\\supset$ B are homothetic convex sets of minimal size? In Chapter 2, we prove a conjecture by Figalli and Jerison establishing the sharp stability for homothetic sets. In particular, we show that for homothetic sets, we have <span class=\"etd-inline-math\">&omega;</span> = O<span class=\"etd-inline-math\"><sub>k</sub></span>(<span class=\"etd-inline-math\">&delta;</span>t<span class=\"etd-inline-math\"><sup>-1</sup></span>), for <span class=\"etd-inline-math\">&delta;</span> sufficiently small. In Chapter 3, we establish the sharp stability for planar sets, i.e. we show that for planar sets and <span class=\"etd-inline-math\">&delta;</span> sufficiently small, we have <span class=\"etd-inline-math\">&omega;</span> = O(<span class=\"etd-inline-math\">&delta;</span><span class=\"etd-inline-math\"><sup>1/2</sup></span>t<span class=\"etd-inline-math\"><sup>-1/2</sup></span>). A crucial result in Chapter 3 shows that for any <span class=\"etd-inline-math\">&epsilon;</span> &gt; 0, if <span class=\"etd-inline-math\">&delta;</span> is sufficiently small, then we have |co(A + B) \\ (A + B)| $\\leq$ (1 + <span class=\"etd-inline-math\">&epsilon;</span>)(|co(A) \\ A| + |co(B) \\ B|). In Chapter 4, we consider a reconstruction problem for functions on graphs. Given a function <span class=\"etd-inline-math\"><em>f</em></span>:V(G) $\\rightarrow$ [k] on the vertices of a graph G and a random walk (U<span class=\"etd-inline-math\"><sub>i</sub></span>)<span class=\"etd-inline-math\"><sup>{\\infty}</sup><sub>i = 1</sub></span> on that graph, can we reconstruct <span class=\"etd-inline-math\"><em>f</em></span> (up to automorphisms) based on just (<span class=\"etd-inline-math\"><em>f</em></span>(U<span class=\"etd-inline-math\"><sub>i</sub></span>)<span class=\"etd-inline-math\"><sup>{\\infty}</sup><sub>i = 1</sub></span>? Gross and Grupel showed this was not generally possible on the hypercube, by constructing non-isomorphic <span class=\"etd-inline-math\"><em>locally p-biased</em></span> sets <span class=\"etd-inline-math\"><em>X</em></span>, so that for each vertex <span class=\"etd-inline-math\"><em>v</em></span> the fraction of neighbours which is in <span class=\"etd-inline-math\"><em>X</em></span> is exactly <span class=\"etd-inline-math\"><em>p</em></span>. Answering a question of Gross and Grupel, we construct uncountably many non-isomorphic partitions of $\\mathbb{Z}$<span class=\"etd-inline-math\"><sup>k</sup></span> into 2k parts such that every element of $\\mathbb{Z}$<span class=\"etd-inline-math\"><sup>k</sup></span> has exactly one neighbour in each part. As a result, we find <span class=\"etd-inline-math\"><em>locally p-biased</em></span> sets for all <span class=\"etd-inline-math\"><em>p = c/2n</em></span> with <span class=\"etd-inline-math\"><em>c</em></span> $\\in$ {0, ... , 2n}. In Chapter 5, we prove the complete graph case of the bunkbed conjecture. Given a graph G, let the bunkbed graph BB(G) be the graph G$\\Box$K<span class=\"etd-inline-math\"><sub>2</sub></span>, i.e. the graph obtained from considering two copies of G and connecting equivalent vertices with an edge. The bunkbed conjecture posed by Kasteleyn in 1985 asserts the very intuitive statement that when considering percolation with uniform parameter p, we have $\\mathbb{P}$(u<span class=\"etd-inline-math\"><sub>1</sub></span> $\\leftrightarrow$ v<span class=\"etd-inline-math\"><sub>1</sub></span>) $\\geq$ $\\mathbb{P}$(u<span class=\"etd-inline-math\"><sub>1</sub></span> $\\leftrightarrow$ v<span class=\"etd-inline-math\"><sub>2</sub></span>), i.e. a vertex has a higher probability of being connected to a vertex in the same copy of G than being connected to the equivalent vertex in the other copy of G. In Chapter 6, we consider the (t,r) broadcast domination number, a generalisation of the domination number in graphs. In this form of domination, we consider a set T $\\subset$ V(G) of towers which broadcast at strength t, where broadcast strength decays linearly with distance in the graph. A set of towers is (t,r) broadcast dominating if every vertex in the graph receives at least r signal from all towers combined. More formally, the (t,r) broadcast domination number of a graph G is the minimal cardinality of a set T $\\subset$ V(G) such that for every vertex v $\\in$ V(G), we have <span class=\"etd-inline-math\"><sup>{\\Sigma}</sup><sub>u {{\\in}} T</sub></span> max{t - d(u,v),0} $\\geq$ r. Proving a conjecture by Drews, Harris, and Randolph, we establish that the minimal asymptotical density of (t,3) broadcasting subset of $\\mathbb{Z}$<span class=\"etd-inline-math\"><sup>2</sup></span> is the same as the minimal asymptotical density of a (t-1,1) broadcasting subset of $\\mathbb{Z}$<span class=\"etd-inline-math\"><sup>2</sup></span>. In Chapter 7, we consider the eternal game chromatic number, a version of the game chromatic number in which the game continues after all vertices have been coloured. We show that with high probability $\\chi$<span class=\"etd-inline-math\"><sup>\\</sup>infty<sub>g</sub></span> (G<span class=\"etd-inline-math\"><sub>n,p</sub></span>) = (p/2 + o(1))n for odd n, and also for even n when p = 1/k for some k $\\in$ $\\mathbb{N}$. The upper bound applies for even n and any other value of p as well, but we conjecture in this case this upper bound is not sharp. Finally, we answer a question posed by Klostermeyer and Mendoza. In Chapter 8, we consider the bridge-burning cops and robbers game, a version of the game where after a robber moves over an edge, the edge is removed from the graph. Proving a generalization of a conjecture by Kinnersley and Peterson, we establish the asymptotically maximal capture time in this game for graphs with bridge-burning cops number at least three. In particular, we show that this maximal capture time grows as k<span class=\"etd-inline-math\"><sup>-O(k)</sup></span>n<span class=\"etd-inline-math\"><sup>k+2</sup></span>, where k $\\geq$ 3 is the bridge burning cop number and n is the number of vertices of the graph.","abstract_has_math":true,"creators":["Van Hintum, Peter"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Bollobás, Béla"],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-11-27","date_published":"2021-11-27","updated_at":"2026-07-22T22:24:28Z","subjects":["Combinatorics","Metric Geometry","Graph Theory","Brunn-Minkowski theory"],"languages":["eng"],"rights":[],"rights_urls":["https://www.rioxx.net/licenses/all-rights-reserved/"],"identifier_entries":[{"key":"dc:creator.authoridentifier","label":"Author Identifier","values":["0000000223232897"],"render_values":[{"text":"0000-0002-2323-2897","href":"https://orcid.org/0000-0002-2323-2897","code":true}]}]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.81596","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Bollobás, Béla"]},{"key":"dc:creator","label":"Author","values":["Van Hintum, Peter"]},{"key":"dc:creator.authoridentifier","label":"Author Identifier","values":["0000000223232897"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2021-11-27"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/334185"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Combinatorics","Metric Geometry","Graph Theory","Brunn-Minkowski theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://www.rioxx.net/licenses/all-rights-reserved/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["10.17863/CAM.81596"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/6280c97e-1793-43c3-9c23-4be05140b576/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This thesis consists of an introduction and seven chapters, each devoted to a different combinatorial problem. In Chapters 1 and 2, we consider the main subject of this thesis; the sharp stability of the Brunn-Minkowski inequality (BM). This celebrated theorem from the 19th century asserts that for bodies A,B $\\subset$ $\\mathbb{R}$$^{k}$, we have |A + B|$^{1/k}$ $\\geq$ |A|$^{1/k}$ + |B|$^{1/k}$, where |$\\cdot$| is the Lebesgue measure and A + B := {a + b : a $\\in$ A, b $\\in$ B} is the Minkowski sum. Moreover, we have equality if and only if A,B are homothetic convex sets. The stability question, studied in many papers, asks how the distance to equality in BM relates to the distance from A,B to homothetic convex sets. In particular, given Brunn-Minkowsi deficit $\\delta$ := |A+B|$^{1/k}$ / |A|$^{1/k}$ + |B|$^{1/k}$ -1, and normalized volume ratio $\\textit{t}$ := |A|$^{1/k}$ / |A|$^{1/k}$ + |B|$^{1/k}$, what is the best bound one can find on $\\omega$ := |K$_{A}$ \\ A| / |A| + |K$_{B}$ \\ B| / |B|, where K$_{A}$ $\\supset$ A, and K$_{B}$ $\\supset$ B are homothetic convex sets of minimal size? In Chapter 2, we prove a conjecture by Figalli and Jerison establishing the sharp stability for homothetic sets. In particular, we show that for homothetic sets, we have $\\omega$ = O$_{k}$($\\delta$t$^{-1}$), for $\\delta$ sufficiently small. In Chapter 3, we establish the sharp stability for planar sets, i.e. we show that for planar sets and $\\delta$ sufficiently small, we have $\\omega$ = O($\\delta$$^{1/2}$t$^{-1/2}$). A crucial result in Chapter 3 shows that for any $\\epsilon$ > 0, if $\\delta$ is sufficiently small, then we have |co(A + B) \\ (A + B)| $\\leq$ (1 + $\\epsilon$)(|co(A) \\ A| + |co(B) \\ B|). In Chapter 4, we consider a reconstruction problem for functions on graphs. Given a function $\\textit{f}$:V(G) $\\rightarrow$ [k] on the vertices of a graph G and a random walk (U$_{i}$)$^{{\\infty}}_{i = 1}$ on that graph, can we reconstruct $\\textit{f}$ (up to automorphisms) based on just ($\\textit{f}$(U$_{i}$)$^{{\\infty}}_{i = 1}$? Gross and Grupel showed this was not generally possible on the hypercube, by constructing non-isomorphic $\\textit{locally p-biased}$ sets $\\textit{X}$, so that for each vertex $\\textit{v}$ the fraction of neighbours which is in $\\textit{X}$ is exactly $\\textit{p}$. Answering a question of Gross and Grupel, we construct uncountably many non-isomorphic partitions of $\\mathbb{Z}$$^{k}$ into 2k parts such that every element of $\\mathbb{Z}$$^{k}$ has exactly one neighbour in each part. As a result, we find $\\textit{locally p-biased}$ sets for all $\\textit{p = c/2n}$ with $\\textit{c}$ $\\in$ {0, ... , 2n}. In Chapter 5, we prove the complete graph case of the bunkbed conjecture. Given a graph G, let the bunkbed graph BB(G) be the graph G$\\Box$K$_{2}$, i.e. the graph obtained from considering two copies of G and connecting equivalent vertices with an edge. The bunkbed conjecture posed by Kasteleyn in 1985 asserts the very intuitive statement that when considering percolation with uniform parameter p, we have $\\mathbb{P}$(u$_{1}$ $\\leftrightarrow$ v$_{1}$) $\\geq$ $\\mathbb{P}$(u$_{1}$ $\\leftrightarrow$ v$_{2}$), i.e. a vertex has a higher probability of being connected to a vertex in the same copy of G than being connected to the equivalent vertex in the other copy of G. In Chapter 6, we consider the (t,r) broadcast domination number, a generalisation of the domination number in graphs. In this form of domination, we consider a set T $\\subset$ V(G) of towers which broadcast at strength t, where broadcast strength decays linearly with distance in the graph. A set of towers is (t,r) broadcast dominating if every vertex in the graph receives at least r signal from all towers combined. More formally, the (t,r) broadcast domination number of a graph G is the minimal cardinality of a set T $\\subset$ V(G) such that for every vertex v $\\in$ V(G), we have $^{{\\Sigma}}_{u {{\\in}} T}$ max{t - d(u,v),0} $\\geq$ r. Proving a conjecture by Drews, Harris, and Randolph, we establish that the minimal asymptotical density of (t,3) broadcasting subset of $\\mathbb{Z}$$^{2}$ is the same as the minimal asymptotical density of a (t-1,1) broadcasting subset of $\\mathbb{Z}$$^{2}$. In Chapter 7, we consider the eternal game chromatic number, a version of the game chromatic number in which the game continues after all vertices have been coloured. We show that with high probability $\\chi$$^\\infty_g$ (G$_{n,p}$) = (p/2 + o(1))n for odd n, and also for even n when p = 1/k for some k $\\in$ $\\mathbb{N}$. The upper bound applies for even n and any other value of p as well, but we conjecture in this case this upper bound is not sharp. Finally, we answer a question posed by Klostermeyer and Mendoza. In Chapter 8, we consider the bridge-burning cops and robbers game, a version of the game where after a robber moves over an edge, the edge is removed from the graph. Proving a generalization of a conjecture by Kinnersley and Peterson, we establish the asymptotically maximal capture time in this game for graphs with bridge-burning cops number at least three. In particular, we show that this maximal capture time grows as k$^{-O(k)}$n$^{k+2}$, where k $\\geq$ 3 is the bridge burning cop number and n is the number of vertices of the graph."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["95845dc374d75aba94520034aaa0e1b2"]},{"key":"dc:title","label":"Title","values":["Combinatorics and Metric Geometry"]}]}],"canonical_facts":{"dc:contributor.advisor":["Bollobás, Béla"],"dc:creator":["Van Hintum, Peter"],"dc:creator.authoridentifier":["0000000223232897"],"dc:date.issued":["2021-11-27"],"dc:description.abstract":["This thesis consists of an introduction and seven chapters, each devoted to a different combinatorial problem. In Chapters 1 and 2, we consider the main subject of this thesis; the sharp stability of the Brunn-Minkowski inequality (BM). This celebrated theorem from the 19th century asserts that for bodies A,B $\\subset$ $\\mathbb{R}$$^{k}$, we have |A + B|$^{1/k}$ $\\geq$ |A|$^{1/k}$ + |B|$^{1/k}$, where |$\\cdot$| is the Lebesgue measure and A + B := {a + b : a $\\in$ A, b $\\in$ B} is the Minkowski sum. Moreover, we have equality if and only if A,B are homothetic convex sets. The stability question, studied in many papers, asks how the distance to equality in BM relates to the distance from A,B to homothetic convex sets. In particular, given Brunn-Minkowsi deficit $\\delta$ := |A+B|$^{1/k}$ / |A|$^{1/k}$ + |B|$^{1/k}$ -1, and normalized volume ratio $\\textit{t}$ := |A|$^{1/k}$ / |A|$^{1/k}$ + |B|$^{1/k}$, what is the best bound one can find on $\\omega$ := |K$_{A}$ \\ A| / |A| + |K$_{B}$ \\ B| / |B|, where K$_{A}$ $\\supset$ A, and K$_{B}$ $\\supset$ B are homothetic convex sets of minimal size? In Chapter 2, we prove a conjecture by Figalli and Jerison establishing the sharp stability for homothetic sets. In particular, we show that for homothetic sets, we have $\\omega$ = O$_{k}$($\\delta$t$^{-1}$), for $\\delta$ sufficiently small. In Chapter 3, we establish the sharp stability for planar sets, i.e. we show that for planar sets and $\\delta$ sufficiently small, we have $\\omega$ = O($\\delta$$^{1/2}$t$^{-1/2}$). A crucial result in Chapter 3 shows that for any $\\epsilon$ > 0, if $\\delta$ is sufficiently small, then we have |co(A + B) \\ (A + B)| $\\leq$ (1 + $\\epsilon$)(|co(A) \\ A| + |co(B) \\ B|). In Chapter 4, we consider a reconstruction problem for functions on graphs. Given a function $\\textit{f}$:V(G) $\\rightarrow$ [k] on the vertices of a graph G and a random walk (U$_{i}$)$^{{\\infty}}_{i = 1}$ on that graph, can we reconstruct $\\textit{f}$ (up to automorphisms) based on just ($\\textit{f}$(U$_{i}$)$^{{\\infty}}_{i = 1}$? Gross and Grupel showed this was not generally possible on the hypercube, by constructing non-isomorphic $\\textit{locally p-biased}$ sets $\\textit{X}$, so that for each vertex $\\textit{v}$ the fraction of neighbours which is in $\\textit{X}$ is exactly $\\textit{p}$. Answering a question of Gross and Grupel, we construct uncountably many non-isomorphic partitions of $\\mathbb{Z}$$^{k}$ into 2k parts such that every element of $\\mathbb{Z}$$^{k}$ has exactly one neighbour in each part. As a result, we find $\\textit{locally p-biased}$ sets for all $\\textit{p = c/2n}$ with $\\textit{c}$ $\\in$ {0, ... , 2n}. In Chapter 5, we prove the complete graph case of the bunkbed conjecture. Given a graph G, let the bunkbed graph BB(G) be the graph G$\\Box$K$_{2}$, i.e. the graph obtained from considering two copies of G and connecting equivalent vertices with an edge. The bunkbed conjecture posed by Kasteleyn in 1985 asserts the very intuitive statement that when considering percolation with uniform parameter p, we have $\\mathbb{P}$(u$_{1}$ $\\leftrightarrow$ v$_{1}$) $\\geq$ $\\mathbb{P}$(u$_{1}$ $\\leftrightarrow$ v$_{2}$), i.e. a vertex has a higher probability of being connected to a vertex in the same copy of G than being connected to the equivalent vertex in the other copy of G. In Chapter 6, we consider the (t,r) broadcast domination number, a generalisation of the domination number in graphs. In this form of domination, we consider a set T $\\subset$ V(G) of towers which broadcast at strength t, where broadcast strength decays linearly with distance in the graph. A set of towers is (t,r) broadcast dominating if every vertex in the graph receives at least r signal from all towers combined. More formally, the (t,r) broadcast domination number of a graph G is the minimal cardinality of a set T $\\subset$ V(G) such that for every vertex v $\\in$ V(G), we have $^{{\\Sigma}}_{u {{\\in}} T}$ max{t - d(u,v),0} $\\geq$ r. Proving a conjecture by Drews, Harris, and Randolph, we establish that the minimal asymptotical density of (t,3) broadcasting subset of $\\mathbb{Z}$$^{2}$ is the same as the minimal asymptotical density of a (t-1,1) broadcasting subset of $\\mathbb{Z}$$^{2}$. In Chapter 7, we consider the eternal game chromatic number, a version of the game chromatic number in which the game continues after all vertices have been coloured. We show that with high probability $\\chi$$^\\infty_g$ (G$_{n,p}$) = (p/2 + o(1))n for odd n, and also for even n when p = 1/k for some k $\\in$ $\\mathbb{N}$. The upper bound applies for even n and any other value of p as well, but we conjecture in this case this upper bound is not sharp. Finally, we answer a question posed by Klostermeyer and Mendoza. In Chapter 8, we consider the bridge-burning cops and robbers game, a version of the game where after a robber moves over an edge, the edge is removed from the graph. Proving a generalization of a conjecture by Kinnersley and Peterson, we establish the asymptotically maximal capture time in this game for graphs with bridge-burning cops number at least three. In particular, we show that this maximal capture time grows as k$^{-O(k)}$n$^{k+2}$, where k $\\geq$ 3 is the bridge burning cop number and n is the number of vertices of the graph."],"dc:format.checksum.md5":["95845dc374d75aba94520034aaa0e1b2"],"dc:identifier.doi":["10.17863/CAM.81596"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/6280c97e-1793-43c3-9c23-4be05140b576/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/334185"],"dc:rights":["https://www.rioxx.net/licenses/all-rights-reserved/"],"dc:subject":["Combinatorics","Metric Geometry","Graph Theory","Brunn-Minkowski theory"],"dc:title":["Combinatorics and Metric Geometry"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:28Z"}