# 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

Hyde J
(2020)

*A Degree Sequence Version of the Kühn-Osthus Tiling Theorem*in The Electronic Journal of Combinatorics
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) |