Topics in metric geometry, combinatorial geometry, extremal combinatorics and additive combinatorics

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₁,f₂,\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}³. 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 ε>0 and $k\in\mathbb{N}$, we construct a subset A\subset\mathbb{Z}_N for some $N$, such that |A²+kA|\leqε N, while A-A=\mathbb{Z}_N. (Here A-A=\{a₁-a₂:a₁,a₂\in A\} and A²+kA=\{a₁a₂+a'₁+a'₂+\dots+a'_k:a₁,a₂,a'₁,a'₂,\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₄(n)\geq (1+o(1))\binom{n}{2}, by showing that f₄(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.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2018

Author dc:creator

• Milicevic, Luka

Advisor dc:contributor.advisor

• Leader, Imre

• combinatorics
• graph theory
• extremal combinatorics
• metric geometry
• combinatorial geometry
• additive combinatorics

Licence

• https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/e82c65b6-27bb-492c-9e8a-41d5a2f382d5/download
• https://creativecommons.org/licenses/by-nc-sa/4.0/

Language dc:language

en

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.20403

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/273375