Topics in additive combinatorics

Thesis

This thesis deals with four problems in additive combinatorics. After giving a brief introduction to the field and overview of the results in Chapter 1, in Chapter 2 we consider the problem of finding the clique number of the Cayley graph on 𝔽₂ⁿ generated by a random subset. We prove a number of results, most notably that for n in a set of density 1, the clique number is concentrated on a single value.

In Chapter 3 we prove that a randomly chosen subset of a finite group is a randomness extractor with high probability. More precisely, we prove that for every fixed δ > 0, given a finite group G and A ⊂ G a random subset of density 1/2, we prove that with high probability for all subsets |X| |Y| ≥ log^2+δ |G| for ( 1/2 + o(1))|X| |Y| of the pairs (x; y) ∈ X × Y we have xy ∈ A.

In Chapter 4 we give a new probabilistic model for the Paley graph which incorporates some multiplicative structure and as a result captures the Graham-Ringrose phenomenon, namely that the its clique number is sometimes a bit larger than what one might expect when considering the usual random model (random Cayley graph). We prove that if we sample such a random graph independently for every prime, then almost surely (i) for infinitely many primes p the clique number is Ω(log p log log p), whilst (ii) for almost all primes the clique number is (2 + o(1)) log p.

Whereas in the previous chapters we were mostly concerned with generic sets, in Chapter 5 we consider a rather different problem concerning additive properties of a specific set. We prove an asymptotic for the number of additive triples of bijections {1,...,n} → ℤ=nℤ, that is, the number of pairs of bijections π₁; π₂: {1,...,n} → ℤ=nℤ such that the pointwise sum π₁ + π₂ is also a bijection.

Authors: Mrazovic, R

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford