Extremal problems for graphs and the integers

Lead Research Organisation: University of Birmingham
Department Name: School of Mathematics

Abstract

The project will investigate modern combinatorial methods and use these to tackle questions in graph theory as well as combinatorial number theory. For example, via the regularity method, the student will investigate conditions that force a graph G to contain an H-tiling of a given size. (Given graphs H and G, an H-tiling in a graph G is a collection of vertex-disjoint copies of H in G.) In particular, the student will work on generalising an important theorem of Komlos on almost perfect H-tilings in graphs. The other part of the project will concern extremal problems in the integers (such as the size and structure of sum-free sets).

Publications

10 25 50
publication icon
Hyde J (2019) A Degree Sequence Komlós Theorem in SIAM Journal on Discrete Mathematics

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509590/1 01/10/2016 30/09/2021
1935869 Studentship EP/N509590/1 25/09/2017 30/06/2021 Joseph Frederick Hyde
 
Description We have improved a key result in the area of graph tilings known as Komlós' Theorem. Komlós' Theorem concerns the minimum degree of a large graph G required so that one can place vertex disjoint copies of a certain smaller graph H onto G such that the copies of H almost cover all the vertices of G. We improve this theorem by replacing the minimum degree condition with a considerably stronger degree sequence condition.

We utilised our degree sequence Komlós' Theorem to prove a degree sequence version of another central result in the area of graph tilings: Kühn and Osthus' Theorem. In the process of proving our degree sequence version of Kühn and Osthus' Theorem we also proved a standalone elementary number theoretical result that only requires that the graph H we are tiling with have a certain property (denoted by hcf(H) = 1).
Exploitation Route Both our results have sufficient leeway to be improved upon and the methods we use can be further developed to prove degree sequence versions of many other theorems in graph and hypergraph theory. Indeed, currently a colleague and I are utilising similar methods to improve upon an existing result from the area of hypergraph matchings.
Sectors Digital/Communication/Information Technologies (including Software)