Show simple item record

dc.contributor.authorMilicevic, Luka
dc.date.accessioned2018-02-22T09:41:08Z
dc.date.available2018-02-22T09:41:08Z
dc.date.issued2018-03-01
dc.date.submitted2017-06-16
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/273375
dc.description.abstractIn 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.sponsorshipI 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.isoen
dc.rightsAttribution-NonCommercial-ShareAlike 4.0 International
dc.rights.urihttps://creativecommons.org/licenses/by-nc-sa/4.0/
dc.subjectcombinatorics
dc.subjectgraph theory
dc.subjectextremal combinatorics
dc.subjectmetric geometry
dc.subjectcombinatorial geometry
dc.subjectadditive combinatorics
dc.titleTopics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics
dc.typeThesis
dc.type.qualificationlevelDoctoral
dc.type.qualificationnameDoctor of Philosophy (PhD)
dc.publisher.institutionUniversity of Cambridge
dc.publisher.departmentDepartment of Pure Mathematics and Mathematical Statistics
dc.date.updated2018-02-21T17:22:47Z
dc.identifier.doi10.17863/CAM.20403
dc.publisher.collegeTrinity College
dc.type.qualificationtitlePhD in Pure Mathematics and Mathematical Statistics
cam.supervisorLeader, Imre
rioxxterms.freetoread.startdate2018-02-21


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

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