Projects per year
Abstract
A recent paper of Balogh, Li and Treglown [3] initiated the study of Diractype problems for ordered graphs. In this paper, we prove a number of results in this area. In particular, we determine asymptotically the minimum degree threshold for forcing
(i) a perfect Htiling in an ordered graph, for any fixed ordered graph H of interval chromatic number at least 3;
(ii) an Htiling in an ordered graph G covering a fixed proportion of the vertices of G (for any fixed ordered
graph H);
(iii) an Hcover in an ordered graph (for any fixed ordered graph H).
The first two of these results resolve questions of Balogh, Li and Treglown, whilst (iii) resolves a question of FalgasRavry. Note that (i) combined with a result from [3] completely determines the asymptotic minimum degree threshold for forcing a perfect Htiling. Additionally, we prove a result that, combined with a theorem of Balogh, Li and Treglown, asymptotically determines the minimum degree threshold for forcing an almost perfect Htiling in an ordered graph (for any fixed ordered graph H). Our work therefore provides ordered graph analogues of the seminal tiling theorems of Kühn and Osthus [Combinatorica 2009] and of Komlós [Combinatorica 2000]. Each of our results exhibits some curious, and perhaps unexpected, behaviour. Our solution to (i) makes use of a novel absorbing argument.
(i) a perfect Htiling in an ordered graph, for any fixed ordered graph H of interval chromatic number at least 3;
(ii) an Htiling in an ordered graph G covering a fixed proportion of the vertices of G (for any fixed ordered
graph H);
(iii) an Hcover in an ordered graph (for any fixed ordered graph H).
The first two of these results resolve questions of Balogh, Li and Treglown, whilst (iii) resolves a question of FalgasRavry. Note that (i) combined with a result from [3] completely determines the asymptotic minimum degree threshold for forcing a perfect Htiling. Additionally, we prove a result that, combined with a theorem of Balogh, Li and Treglown, asymptotically determines the minimum degree threshold for forcing an almost perfect Htiling in an ordered graph (for any fixed ordered graph H). Our work therefore provides ordered graph analogues of the seminal tiling theorems of Kühn and Osthus [Combinatorica 2009] and of Komlós [Combinatorica 2000]. Each of our results exhibits some curious, and perhaps unexpected, behaviour. Our solution to (i) makes use of a novel absorbing argument.
Original language  English 

Pages (fromto)  e104 1–41 
Journal  Forum of Mathematics, Sigma 
Volume  10 
DOIs  
Publication status  Published  21 Nov 2022 
Fingerprint
Dive into the research topics of 'Diractype results for tilings and coverings in ordered graphs'. Together they form a unique fingerprint.Projects
 1 Finished

Matchings and tilings in graphs
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils