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).
Organisations
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 | 01/10/2017 | 30/06/2021 | Joseph 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). Candida Bowtell and I used the methodology developed in my paper A Degree Sequence Komlós Theorem to prove a degree sequence condition forcing a perfect matching in 3 uniform hypergraphs. This result improves implies and strengthens a result of Han, Person and Schacht. Balogh, Csaba, Jing and Pluhár recently determined the minimum degree threshold that ensures a 2-coloured graph G contains a Hamilton cycle of significant colour bias (i.e., a Hamilton cycle that contains significantly more than half of its edges in one colour). With Andrea Freschi, Joanna Lada and Andrew Treglown, I proved an extension of this result, determining the corresponding threshold for r-colourings. Motivated by analogous questions in the setting of Steiner triple systems and Latin squares, Nenadov, Sudakov and Wagner [Completion and deficiency problems, Journal of Combinatorial Theory Series B, 2020] recently introduced the notion of graph deficiency. Given a global spanning property P and a graph G, the deficiency def(G) of the graph G with respect to the property P is the smallest non-negative integer t such that the join G*K_t has property P. In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an n-vertex graph G needs to ensure G*K_t contains a K_r-factor (for any fixed r=3). With Andrea Freschi and Andrew Treglown, I resolved their problem fully. We also gave an analogous result which forces G*K_t to contain any fixed bipartite (n+t)-vertex graph of bounded degree and small bandwidth. |
| Exploitation Route | Our first two 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. Candida and I's result is the first vertex degree sequence result in hypergraphs. As such, we have pioneered the way for others to use our methods (and similar approaches) to prove other vertex degree sequence results in hypergraphs. One natural way of extending my result with Andrea Freschi, Joanna Lada and Andrew Treglown is to prove a similar result for digraphs. My result with Andrea Freschi and Andrew Treglown opens the way for others to consider the deficiency problem for other global spanning properties P, such as perfect H-tilings for a fixed graph H that isn't a clique (we ask a question regarding the deficiency problem for perfect H-tilings in our paper). |
| Sectors | Digital/Communication/Information Technologies (including Software) |