Repository logo
 

Results in Extremal Graph Theory, Ramsey Theory and Additive Combinatorics


Loading...
Thumbnail Image

Type

Thesis

Change log

Authors

Janzer, Oliver 

Abstract

This dissertation contains results from various areas of Combinatorics.

In Chapter 2, we consider a central problem in Extremal Graph Theory. The extremal number (or Turán number) ex(n,H) of a graph H is the maximum number of edges in an H-free graph on n vertices. It is a major area of research to better understand the extremal number of bipartite graphs. In this chapter we develop a new method which allows us to obtain strong (and often best possible) upper bounds in a wide range of cases. Our results answer several conjectures of Conlon and Lee, and Kang, Kim and Liu. Furthermore, they relate to and improve work of (among others) Füredi, Alon, Krivelevich and Sudakov, Kostochka and Pyber, and Jiang and Seiver.

While in Chapter 2 the focus is on subdivided graphs, in Chapter 3 we study the extremal number of blow-ups. In particular, we obtain tight upper bounds for the extremal number of blow-ups of trees. As an extension of this, we pose a general conjecture relating the extremal number of F and that of its blow-up. We prove the conjecture for the 2-blowup of C_6.

In Chapter 4 we study a coloured variant of the Turán problem. The rainbow Turán number of H, denoted by ex*(n,H), is the maximum possible number of edges in an n-vertex properly edge-coloured graph without a rainbow subgraph isomorphic to H. We prove that ex*(n,C_{2k})=O(n^{1+1/k}), which is tight and establishes a conjecture of Keevash, Mubayi, Sudakov and Verstraete. We use the same method to answer several further questions in various topics: among others, a question of Conlon and Tyomkyn on colour-isomorphic cycles and a conjecture of Jiang and Newman of blow-ups of cycles. We also disprove an old conjecture of Erdős and Simonovits on (ordinary) extremal numbers.

In Chapter 5, we consider the following problem. Let 2 ≤ s < t be fixed integers. If G is an arbitrary K_t-free graph on n vertices, how large a K_s-free induced subgraph must there exist in G? This number, which is a generalisation of the usual off-diagonal Ramsey numbers, is viewed as a function in n, and is called the Erdős-Rogers function. We obtain new upper bounds in the case s+2 ≤ t ≤ 2s-1, improving results of (among others) Bollobás, Erdős and Krivelevich, and answering a question of Dudek, Retter and Rödl.

In Chapter 6, we investigate the relationship between two well-studied notions of tensor rank. We show that the partition rank of a tensor is bounded above by a polynomial in the analytic rank of the same tensor. This improves Ackermann-type bounds obtained by various authors including Green and Tao, and Bhowmick and Lovett.

In Chapter 7, we use the main technical lemma of Chapter 6 to prove a result about the expansion of subsets of the Cayley graph on the tensor product F_2^{n_1} ⊗ … ⊗ F_2^{n_d} where the generators are the rank 1 tensors. This is motivated by the famous Unique Games Conjecture from Theoretical Computer Science, and is a partial generalisation of a recent breakthrough result of Khot, Minzer and Safra.

In Chapter 8, we ask the following question. Given constants α,β,γ, what is the minimal possible edge density of a graph G on n vertices with the property that every subset A⊆V(G) with |A| ≥ αn contains a subset B⊆A with |B| ≥ βn such that G[B] has edge density at least γ? We also study a bipartite version of this question, obtaining sharp results in both cases.

In Chapter 9, we determine asymptotically the maximum possible number of induced C_5's in a planar graph on n vertices.

Description

Date

2020-06-11

Advisors

Gowers, William Timothy

Keywords

Combinatorics, Graph Theory, Ramsey Theory, Additive Combinatorics

Qualification

Doctor of Philosophy (PhD)

Awarding Institution

University of Cambridge