Tilings in vertex ordered graphs

Jozsef Balogh; Lina Li; Andrew Treglown

doi:10.1016/j.jctb.2022.02.006

Tilings in vertex ordered graphs

Jozsef Balogh, Lina Li, Andrew Treglown

Mathematics

Research output: Contribution to journal › Article › peer-review

52 Downloads (Pure)

Abstract

Over recent years there has been much interest in both Turán and Ramsey properties of vertex ordered graphs. In this paper we initiate the study of embedding spanning structures into vertex ordered graphs. In particular, we introduce a general framework for approaching the problem of determining the minimum degree threshold for forcing a perfect H-tiling in an ordered graph. In the (unordered) graph setting, this problem was resolved by Kühn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009]. We use our general framework to resolve the perfect H-tiling problem for all ordered graphs H of interval chromatic number 2. Already in this restricted setting the class of extremal examples is richer than in the unordered graph problem. In the process of proving our results, novel approaches to both the regularity and absorbing methods are developed.

Original language	English
Pages (from-to)	171-201
Number of pages	31
Journal	Journal of Combinatorial Theory. Series B
Volume	155
Early online date	3 Mar 2022
DOIs	https://doi.org/10.1016/j.jctb.2022.02.006
Publication status	Published - Jul 2022

Bibliographical note

Funding Information:
Partially supported by NSF Grant DMS-1764123 and Arnold O. Beckman Research Award (UIUC) Campus Research Board 18132 and the Langan Scholar Fund (UIUC).Research supported by EPSRC grant EP/V002279/1.

Keywords

Absorbing method
Dirac-type problems
Factors
Ordered graphs
Regularity method

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2022.02.006Licence: Creative Commons: Attribution (CC BY)

1-s2.0-S0095895622000156-mainFinal published version, 591 KBLicence: Creative Commons: Attribution (CC BY)

Matchings and tilings in graphs
Lo, A. (Co-Investigator) & Treglown, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils

Cite this

@article{5633a52c411043cfb9737a313d647ef8,

title = "Tilings in vertex ordered graphs",

abstract = "Over recent years there has been much interest in both Tur{\'a}n and Ramsey properties of vertex ordered graphs. In this paper we initiate the study of embedding spanning structures into vertex ordered graphs. In particular, we introduce a general framework for approaching the problem of determining the minimum degree threshold for forcing a perfect H-tiling in an ordered graph. In the (unordered) graph setting, this problem was resolved by K{\"u}hn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009]. We use our general framework to resolve the perfect H-tiling problem for all ordered graphs H of interval chromatic number 2. Already in this restricted setting the class of extremal examples is richer than in the unordered graph problem. In the process of proving our results, novel approaches to both the regularity and absorbing methods are developed.",

keywords = "Absorbing method, Dirac-type problems, Factors, Ordered graphs, Regularity method",

author = "Jozsef Balogh and Lina Li and Andrew Treglown",

note = "Funding Information: Partially supported by NSF Grant DMS-1764123 and Arnold O. Beckman Research Award (UIUC) Campus Research Board 18132 and the Langan Scholar Fund (UIUC).Research supported by EPSRC grant EP/V002279/1.",

year = "2022",

month = jul,

doi = "10.1016/j.jctb.2022.02.006",

language = "English",

volume = "155",

pages = "171--201",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Tilings in vertex ordered graphs

AU - Balogh, Jozsef

AU - Li, Lina

AU - Treglown, Andrew

N1 - Funding Information: Partially supported by NSF Grant DMS-1764123 and Arnold O. Beckman Research Award (UIUC) Campus Research Board 18132 and the Langan Scholar Fund (UIUC).Research supported by EPSRC grant EP/V002279/1.

PY - 2022/7

Y1 - 2022/7

N2 - Over recent years there has been much interest in both Turán and Ramsey properties of vertex ordered graphs. In this paper we initiate the study of embedding spanning structures into vertex ordered graphs. In particular, we introduce a general framework for approaching the problem of determining the minimum degree threshold for forcing a perfect H-tiling in an ordered graph. In the (unordered) graph setting, this problem was resolved by Kühn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009]. We use our general framework to resolve the perfect H-tiling problem for all ordered graphs H of interval chromatic number 2. Already in this restricted setting the class of extremal examples is richer than in the unordered graph problem. In the process of proving our results, novel approaches to both the regularity and absorbing methods are developed.

AB - Over recent years there has been much interest in both Turán and Ramsey properties of vertex ordered graphs. In this paper we initiate the study of embedding spanning structures into vertex ordered graphs. In particular, we introduce a general framework for approaching the problem of determining the minimum degree threshold for forcing a perfect H-tiling in an ordered graph. In the (unordered) graph setting, this problem was resolved by Kühn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009]. We use our general framework to resolve the perfect H-tiling problem for all ordered graphs H of interval chromatic number 2. Already in this restricted setting the class of extremal examples is richer than in the unordered graph problem. In the process of proving our results, novel approaches to both the regularity and absorbing methods are developed.

KW - Absorbing method

KW - Dirac-type problems

KW - Factors

KW - Ordered graphs

KW - Regularity method

UR - http://www.scopus.com/inward/record.url?scp=85125547585&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2022.02.006

DO - 10.1016/j.jctb.2022.02.006

M3 - Article

SN - 0095-8956

VL - 155

SP - 171

EP - 201

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Tilings in vertex ordered graphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Projects

Matchings and tilings in graphs

Cite this