Repository logo
 

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


Type

Thesis

Change log

Authors

Milicevic, Luka 

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 f1,f2,…,fn:XX is a \emph{contractive family} if there exists λ<1 such that for any x,yX we have d(fi(x),fi(y))≤λ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 λ<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 N3. These answer questions of Austin and Stein. In the second part, we prove that given any 4-colouring of the edges of Kn, we can find sets X,Y,Z and colours x,y,z (not necessarily distinct) such that XYZ=V(Kn), and each of Kn[X,x],Kn[Y,y] and Kn[Z,z] has diameter bounded by 160 (where KN[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 Rd is in \emph{general position} if no d+1 lie on a common hyperplane. Similarly, we say that a set of points in Rd 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 Rd, 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 ZN (the integers modulo N). For all ϵ>0 and kN, we construct a subset AZN for some N, such that |A2+kA|≤ϵN, while AA=ZN. (Here AA={a1−a2:a1,a2∈A} and A2+kA={a1a2+a1′+a2′+⋯+ak′:a1,a2,a1′,a2′,…,ak′∈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 fr(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 f4(n)≥(1+o(1))(n2), by showing that f4(n)≤1415(1+o(1))(n2). 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.

Description

Date

2017-06-16

Advisors

Leader, Imre

Keywords

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

Qualification

Doctor of Philosophy (PhD)

Awarding Institution

University of Cambridge
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.