dc.contributor.author Milicevic, Luka dc.date.accessioned 2018-02-22T09:41:08Z dc.date.available 2018-02-22T09:41:08Z dc.date.issued 2018-03-01 dc.date.submitted 2017-06-16 dc.identifier.uri https://www.repository.cam.ac.uk/handle/1810/273375 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.description.sponsorship 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.language.iso en dc.rights Attribution-NonCommercial-ShareAlike 4.0 International dc.rights.uri https://creativecommons.org/licenses/by-nc-sa/4.0/ dc.subject combinatorics dc.subject graph theory dc.subject extremal combinatorics dc.subject metric geometry dc.subject combinatorial geometry dc.subject 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) dc.publisher.institution University of Cambridge dc.publisher.department Department of Pure Mathematics and Mathematical Statistics dc.date.updated 2018-02-21T17:22:47Z dc.identifier.doi 10.17863/CAM.20403 dc.publisher.college Trinity College dc.type.qualificationtitle PhD in Pure Mathematics and Mathematical Statistics cam.supervisor Leader, Imre rioxxterms.freetoread.startdate 2018-02-21
﻿

### This item appears in the following Collection(s)

Except where otherwise noted, this item's licence is described as Attribution-NonCommercial-ShareAlike 4.0 International