{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/273375"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/273375","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics","abstract":"In this thesis, we consider several combinatorial topics, belonging to the areas appearing in the thesis title. Given a non-empty complete metric space $(X,d)$, a family of $n$ continuous maps $f_1,f_2,\\dots,f_n\\colon X\\to X$ is a \\emph{contractive family} if there exists $\\lambda<1$ such that for any $x,y\\in X$ we have $d(f_i(x),f_i(y))\\leq\\lambda d(x,y)$ for some $i$. In the first part of the thesis, we (i) construct a compact metric space $(X,d)$ with a contractive family $\\{f,g\\}$, such that no word in $f,g$ has a fixed point, and (ii) show that if $\\{f,g,h\\}$ is a contractive family such that $f,g,h$ commute and $\\lambda<10^{-23}$, then they have a common fixed point. The proofs of these two statements are combinatorial in nature. For \\textbf{(i)}, we introduce a new concept of a \\emph{diameter space}, leading us naturally to a combinatorial problem about constructing certain sets of words. The result \\textbf{(ii)} has a Ramsey-theoretic flavour, and is based on studying the local and global structure of a related metric space on $\\mathbb{N}^3$. These answer questions of Austin and Stein. In the second part, we prove that given any 4-colouring of the edges of $K_n$, we can find sets $X,Y,Z$ and colours $x,y,z$ (not necessarily distinct) such that $X\\cup Y\\cup Z=V(K_n)$, and each of $K_n[X, x],K_n[Y, y]$ and $K_n[Z, z]$ has diameter bounded by 160 (where $K_N[X,x]$ denotes the edges in $X$ that have colour $x$). This theorem is motivated by the work on commuting contractive families, where the analogous statement for 3 colours played a crucial role, and by the Lovász-Ryser conjecture. The proof is in the spirit of structural graph theory. The key point is the fact that the diameters are bounded. This strengthens a result of Gyárfás, who proved the same but with no diameter bounds (i.e. just with the sets being connected). Recall that a set of points in $\\mathbb{R}^d$ is in \\emph{general position} if no $d+1$ lie on a common hyperplane. Similarly, we say that a set of points in $\\mathbb{R}^d$ is in \\textit{almost general position} if no $d+2$ lie on a common hyperplane. In the third part, we answer a question of Füredi, by showing that, for each $d$, there are sets of $n$ points in almost general position in $\\mathbb{R}^d$, whose subsets in general position have size at most $o(n)$. The proof is based on algebraically studying to what extent polynomial maps preserve cohyperplanarity, and an application of the density version of the Hales--Jewett theorem. In the fourth part, we answer a question of Nathanson in additive combinatorics about sums, differences and products of sets in $\\mathbb{Z}_N$ (the integers modulo $N$). For all $\\epsilon>0$ and $k\\in\\mathbb{N}$, we construct a subset $A\\subset\\mathbb{Z}_N$ for some $N$, such that $|A^2+kA|\\leq\\epsilon N$, while $A-A=\\mathbb{Z}_N$. (Here $A-A=\\{a_1-a_2:a_1,a_2\\in A\\}$ and $A^2+kA=\\{a_1a_2+a'_1+a'_2+\\dots+a'_k:a_1,a_2,a'_1,a'_2,\\dots,a'_k\\in A\\}$.) We also prove some extensions of this result. Among other ingredients, the proof also includes an application of a quantitative equidistribution result for polynomials. In the final part, we consider the Graham-Pollak problem for hypergraphs. Let $f_r(n)$ be the minimum number of complete $r$-partite $r$-graphs needed to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. We disprove a conjecture that $f_4(n)\\geq (1+o(1))\\binom{n}{2}$, by showing that $f_4(n)\\leq\\frac{14}{15}(1+o(1))\\binom{n}{2}$. The proof is based on the relationship between this problem and a problem about decomposing products of complete graphs, and understanding how the Graham-Pollak theorem (for graphs) affects what can happen here.","abstract_html":"In this thesis, we consider several combinatorial topics, belonging to the areas appearing in the thesis title. Given a non-empty complete metric space $(X,d)$, a family of $n$ continuous maps f1,f2,\\dots,fn\\colon X\\to X is a \\emph{contractive family} if there exists $\\lambda<1$ such that for any $x,y\\in X$ we have d(fi(x),fi(y))\\leq\\lambda d(x,y) for some $i$. In the first part of the thesis, we (i) construct a compact metric space $(X,d)$ with a contractive family $\\{f,g\\}$, such that no word in $f,g$ has a fixed point, and (ii) show that if $\\{f,g,h\\}$ is a contractive family such that $f,g,h$ commute and \\lambda<10-23, then they have a common fixed point. The proofs of these two statements are combinatorial in nature. For \\textbf{(i)}, we introduce a new concept of a \\emph{diameter space}, leading us naturally to a combinatorial problem about constructing certain sets of words. The result \\textbf{(ii)} has a Ramsey-theoretic flavour, and is based on studying the local and global structure of a related metric space on \\mathbb{N}3. These answer questions of Austin and Stein. In the second part, we prove that given any 4-colouring of the edges of Kn, we can find sets $X,Y,Z$ and colours $x,y,z$ (not necessarily distinct) such that X\\cup Y\\cup Z=V(Kn), and each of Kn[X, x],Kn[Y, y] and Kn[Z, z] has diameter bounded by 160 (where KN[X,x] denotes the edges in $X$ that have colour $x$). This theorem is motivated by the work on commuting contractive families, where the analogous statement for 3 colours played a crucial role, and by the Lovász-Ryser conjecture. The proof is in the spirit of structural graph theory. The key point is the fact that the diameters are bounded. This strengthens a result of Gyárfás, who proved the same but with no diameter bounds (i.e. just with the sets being connected). Recall that a set of points in \\mathbb{R}d is in \\emph{general position} if no $d+1$ lie on a common hyperplane. Similarly, we say that a set of points in \\mathbb{R}d is in \\textit{almost general position} if no $d+2$ lie on a common hyperplane. In the third part, we answer a question of Füredi, by showing that, for each $d$, there are sets of $n$ points in almost general position in \\mathbb{R}d, whose subsets in general position have size at most $o(n)$. The proof is based on algebraically studying to what extent polynomial maps preserve cohyperplanarity, and an application of the density version of the Hales--Jewett theorem. In the fourth part, we answer a question of Nathanson in additive combinatorics about sums, differences and products of sets in \\mathbb{Z}N (the integers modulo $N$). For all ε>0 and $k\\in\\mathbb{N}$, we construct a subset A\\subset\\mathbb{Z}N for some $N$, such that |A2+kA|\\leqε N, while A-A=\\mathbb{Z}N. (Here A-A=\\{a1-a2:a1,a2\\in A\\} and A2+kA=\\{a1a2+a'1+a'2+\\dots+a'k:a1,a2,a'1,a'2,\\dots,a'k\\in A\\}.) We also prove some extensions of this result. Among other ingredients, the proof also includes an application of a quantitative equidistribution result for polynomials. In the final part, we consider the Graham-Pollak problem for hypergraphs. Let fr(n) be the minimum number of complete $r$-partite $r$-graphs needed to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. We disprove a conjecture that f4(n)\\geq (1+o(1))\\binom{n}{2}, by showing that f4(n)\\leq\\frac{14}{15}(1+o(1))\\binom{n}{2}. The proof is based on the relationship between this problem and a problem about decomposing products of complete graphs, and understanding how the Graham-Pollak theorem (for graphs) affects what can happen here.","abstract_has_math":true,"creators":["Milicevic, Luka"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Leader, Imre"],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-03-01","date_published":"2018-03-01","updated_at":"2026-07-22T22:24:13Z","subjects":["combinatorics","graph theory","extremal combinatorics","metric geometry","combinatorial geometry","additive combinatorics"],"languages":["en"],"rights":[],"rights_urls":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/e82c65b6-27bb-492c-9e8a-41d5a2f382d5/download","https://creativecommons.org/licenses/by-nc-sa/4.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.20403","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Leader, Imre"]},{"key":"dc:contributor.sponsor","label":"Sponsor","values":["I would like to thank Trinity College and Department of Pure Mathematics and Mathematical Statistics for their generous financial support and hospitality during PhD studies."]},{"key":"dc:creator","label":"Author","values":["Milicevic, Luka"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2018-03-01"]},{"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/273375"]},{"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","graph theory","extremal combinatorics","metric geometry","combinatorial geometry","additive combinatorics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/e82c65b6-27bb-492c-9e8a-41d5a2f382d5/download","https://creativecommons.org/licenses/by-nc-sa/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["10.17863/CAM.20403"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/b676f861-bf07-4018-a267-491b9abfbd23/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In this thesis, we consider several combinatorial topics, belonging to the areas appearing in the thesis title. Given a non-empty complete metric space $(X,d)$, a family of $n$ continuous maps $f_1,f_2,\\dots,f_n\\colon X\\to X$ is a \\emph{contractive family} if there exists $\\lambda<1$ such that for any $x,y\\in X$ we have $d(f_i(x),f_i(y))\\leq\\lambda d(x,y)$ for some $i$. In the first part of the thesis, we (i) construct a compact metric space $(X,d)$ with a contractive family $\\{f,g\\}$, such that no word in $f,g$ has a fixed point, and (ii) show that if $\\{f,g,h\\}$ is a contractive family such that $f,g,h$ commute and $\\lambda<10^{-23}$, then they have a common fixed point. The proofs of these two statements are combinatorial in nature. For \\textbf{(i)}, we introduce a new concept of a \\emph{diameter space}, leading us naturally to a combinatorial problem about constructing certain sets of words. The result \\textbf{(ii)} has a Ramsey-theoretic flavour, and is based on studying the local and global structure of a related metric space on $\\mathbb{N}^3$. These answer questions of Austin and Stein. In the second part, we prove that given any 4-colouring of the edges of $K_n$, we can find sets $X,Y,Z$ and colours $x,y,z$ (not necessarily distinct) such that $X\\cup Y\\cup Z=V(K_n)$, and each of $K_n[X, x],K_n[Y, y]$ and $K_n[Z, z]$ has diameter bounded by 160 (where $K_N[X,x]$ denotes the edges in $X$ that have colour $x$). This theorem is motivated by the work on commuting contractive families, where the analogous statement for 3 colours played a crucial role, and by the Lovász-Ryser conjecture. The proof is in the spirit of structural graph theory. The key point is the fact that the diameters are bounded. This strengthens a result of Gyárfás, who proved the same but with no diameter bounds (i.e. just with the sets being connected). Recall that a set of points in $\\mathbb{R}^d$ is in \\emph{general position} if no $d+1$ lie on a common hyperplane. Similarly, we say that a set of points in $\\mathbb{R}^d$ is in \\textit{almost general position} if no $d+2$ lie on a common hyperplane. In the third part, we answer a question of Füredi, by showing that, for each $d$, there are sets of $n$ points in almost general position in $\\mathbb{R}^d$, whose subsets in general position have size at most $o(n)$. The proof is based on algebraically studying to what extent polynomial maps preserve cohyperplanarity, and an application of the density version of the Hales--Jewett theorem. In the fourth part, we answer a question of Nathanson in additive combinatorics about sums, differences and products of sets in $\\mathbb{Z}_N$ (the integers modulo $N$). For all $\\epsilon>0$ and $k\\in\\mathbb{N}$, we construct a subset $A\\subset\\mathbb{Z}_N$ for some $N$, such that $|A^2+kA|\\leq\\epsilon N$, while $A-A=\\mathbb{Z}_N$. (Here $A-A=\\{a_1-a_2:a_1,a_2\\in A\\}$ and $A^2+kA=\\{a_1a_2+a'_1+a'_2+\\dots+a'_k:a_1,a_2,a'_1,a'_2,\\dots,a'_k\\in A\\}$.) We also prove some extensions of this result. Among other ingredients, the proof also includes an application of a quantitative equidistribution result for polynomials. In the final part, we consider the Graham-Pollak problem for hypergraphs. Let $f_r(n)$ be the minimum number of complete $r$-partite $r$-graphs needed to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. We disprove a conjecture that $f_4(n)\\geq (1+o(1))\\binom{n}{2}$, by showing that $f_4(n)\\leq\\frac{14}{15}(1+o(1))\\binom{n}{2}$. The proof is based on the relationship between this problem and a problem about decomposing products of complete graphs, and understanding how the Graham-Pollak theorem (for graphs) affects what can happen here."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["87eda9de84448d1f82354d60eee3eb5f","0e140959dc45dc182ee6de017aee7523"]},{"key":"dc:title","label":"Title","values":["Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics"]}]}],"canonical_facts":{"dc:contributor.advisor":["Leader, Imre"],"dc:contributor.sponsor":["I would like to thank Trinity College and Department of Pure Mathematics and Mathematical Statistics for their generous financial support and hospitality during PhD studies."],"dc:creator":["Milicevic, Luka"],"dc:date.issued":["2018-03-01"],"dc:description.abstract":["In this thesis, we consider several combinatorial topics, belonging to the areas appearing in the thesis title. Given a non-empty complete metric space $(X,d)$, a family of $n$ continuous maps $f_1,f_2,\\dots,f_n\\colon X\\to X$ is a \\emph{contractive family} if there exists $\\lambda<1$ such that for any $x,y\\in X$ we have $d(f_i(x),f_i(y))\\leq\\lambda d(x,y)$ for some $i$. In the first part of the thesis, we (i) construct a compact metric space $(X,d)$ with a contractive family $\\{f,g\\}$, such that no word in $f,g$ has a fixed point, and (ii) show that if $\\{f,g,h\\}$ is a contractive family such that $f,g,h$ commute and $\\lambda<10^{-23}$, then they have a common fixed point. The proofs of these two statements are combinatorial in nature. For \\textbf{(i)}, we introduce a new concept of a \\emph{diameter space}, leading us naturally to a combinatorial problem about constructing certain sets of words. The result \\textbf{(ii)} has a Ramsey-theoretic flavour, and is based on studying the local and global structure of a related metric space on $\\mathbb{N}^3$. These answer questions of Austin and Stein. In the second part, we prove that given any 4-colouring of the edges of $K_n$, we can find sets $X,Y,Z$ and colours $x,y,z$ (not necessarily distinct) such that $X\\cup Y\\cup Z=V(K_n)$, and each of $K_n[X, x],K_n[Y, y]$ and $K_n[Z, z]$ has diameter bounded by 160 (where $K_N[X,x]$ denotes the edges in $X$ that have colour $x$). This theorem is motivated by the work on commuting contractive families, where the analogous statement for 3 colours played a crucial role, and by the Lovász-Ryser conjecture. The proof is in the spirit of structural graph theory. The key point is the fact that the diameters are bounded. This strengthens a result of Gyárfás, who proved the same but with no diameter bounds (i.e. just with the sets being connected). Recall that a set of points in $\\mathbb{R}^d$ is in \\emph{general position} if no $d+1$ lie on a common hyperplane. Similarly, we say that a set of points in $\\mathbb{R}^d$ is in \\textit{almost general position} if no $d+2$ lie on a common hyperplane. In the third part, we answer a question of Füredi, by showing that, for each $d$, there are sets of $n$ points in almost general position in $\\mathbb{R}^d$, whose subsets in general position have size at most $o(n)$. The proof is based on algebraically studying to what extent polynomial maps preserve cohyperplanarity, and an application of the density version of the Hales--Jewett theorem. In the fourth part, we answer a question of Nathanson in additive combinatorics about sums, differences and products of sets in $\\mathbb{Z}_N$ (the integers modulo $N$). For all $\\epsilon>0$ and $k\\in\\mathbb{N}$, we construct a subset $A\\subset\\mathbb{Z}_N$ for some $N$, such that $|A^2+kA|\\leq\\epsilon N$, while $A-A=\\mathbb{Z}_N$. (Here $A-A=\\{a_1-a_2:a_1,a_2\\in A\\}$ and $A^2+kA=\\{a_1a_2+a'_1+a'_2+\\dots+a'_k:a_1,a_2,a'_1,a'_2,\\dots,a'_k\\in A\\}$.) We also prove some extensions of this result. Among other ingredients, the proof also includes an application of a quantitative equidistribution result for polynomials. In the final part, we consider the Graham-Pollak problem for hypergraphs. Let $f_r(n)$ be the minimum number of complete $r$-partite $r$-graphs needed to partition the edge set of the complete $r$-uniform hypergraph on $n$ vertices. We disprove a conjecture that $f_4(n)\\geq (1+o(1))\\binom{n}{2}$, by showing that $f_4(n)\\leq\\frac{14}{15}(1+o(1))\\binom{n}{2}$. The proof is based on the relationship between this problem and a problem about decomposing products of complete graphs, and understanding how the Graham-Pollak theorem (for graphs) affects what can happen here."],"dc:format.checksum.md5":["87eda9de84448d1f82354d60eee3eb5f","0e140959dc45dc182ee6de017aee7523"],"dc:identifier.doi":["10.17863/CAM.20403"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/b676f861-bf07-4018-a267-491b9abfbd23/download"],"dc:language":["en"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/273375"],"dc:rights":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/e82c65b6-27bb-492c-9e8a-41d5a2f382d5/download","https://creativecommons.org/licenses/by-nc-sa/4.0/"],"dc:subject":["combinatorics","graph theory","extremal combinatorics","metric geometry","combinatorial geometry","additive combinatorics"],"dc:title":["Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:13Z"}