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.