Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics
View / Open Files
Authors
Milicevic, Luka
Advisors
Leader, Imre
Date
2018-03-01Awarding Institution
University of Cambridge
Author Affiliation
Department of Pure Mathematics and Mathematical Statistics
Qualification
Doctor of Philosophy (PhD)
Language
English
Type
Thesis
Metadata
Show full item recordCitation
Milicevic, L. (2018). Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics (Doctoral thesis). https://doi.org/10.17863/CAM.20403
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.
Keywords
combinatorics, graph theory, extremal combinatorics, metric geometry, combinatorial geometry, additive combinatorics
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.
Identifiers
This record's DOI: https://doi.org/10.17863/CAM.20403
Rights
Attribution-NonCommercial-ShareAlike 4.0 International
Licence URL: https://creativecommons.org/licenses/by-nc-sa/4.0/