Transitive tournament tilings in oriented graphs with large minimum total degree

Louis DeBiasio; Allan Lo; Theodore Molla; Andrew Treglown

doi:10.1137/19M1269257

Transitive tournament tilings in oriented graphs with large minimum total degree

Louis DeBiasio
, Allan Lo
, Theodore Molla
, Andrew Treglown

Mathematics

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

410 Downloads (Pure)

Abstract

Let T^→k be the transitive tournament on k vertices. We show that every oriented graph on n = 4m vertices with minimum total degree (11/12 + o(1))n can be partitioned into vertex disjoint T^→₄'s, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint T→_k's.

Original language	English
Pages (from-to)	250–266
Number of pages	17
Journal	SIAM Journal on Discrete Mathematics
Volume	35
Issue number	1
DOIs	https://doi.org/10.1137/19M1269257
Publication status	Published - 22 Feb 2021

Keywords

absorbing
fractional matching
linear programming
oriented ramsey
tiling ramsey
tournaments

Access to Document

10.1137/19M1269257Licence: None: All rights reserved

DeBiasioL2021TransitiveFinal published version, 545 KBLicence: None: All rights reserved

A graph theoretical approach for combinatorial designs
Lo, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/11/16 → 31/10/18
Project: Research Councils
EPSRC Fellowship: Dr Andrew Treglown - Independence in groups, graphs and the integers
Treglown, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/06/15 → 31/05/18
Project: Research Councils

Cite this

@article{f83a1576df664ee6b2d327d0eaec5a1f,

title = "Transitive tournament tilings in oriented graphs with large minimum total degree",

abstract = "Let T→k be the transitive tournament on k vertices. We show that every oriented graph on n = 4m vertices with minimum total degree (11/12 + o(1))n can be partitioned into vertex disjoint T→4's, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint T→k's. ",

keywords = "absorbing, fractional matching, linear programming, oriented ramsey, tiling ramsey, tournaments",

author = "Louis DeBiasio and Allan Lo and Theodore Molla and Andrew Treglown",

year = "2021",

month = feb,

day = "22",

doi = "10.1137/19M1269257",

language = "English",

volume = "35",

pages = "250–266",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Transitive tournament tilings in oriented graphs with large minimum total degree

AU - DeBiasio, Louis

AU - Lo, Allan

AU - Molla, Theodore

AU - Treglown, Andrew

PY - 2021/2/22

Y1 - 2021/2/22

N2 - Let T→k be the transitive tournament on k vertices. We show that every oriented graph on n = 4m vertices with minimum total degree (11/12 + o(1))n can be partitioned into vertex disjoint T→4's, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint T→k's.

AB - Let T→k be the transitive tournament on k vertices. We show that every oriented graph on n = 4m vertices with minimum total degree (11/12 + o(1))n can be partitioned into vertex disjoint T→4's, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint T→k's.

KW - absorbing

KW - fractional matching

KW - linear programming

KW - oriented ramsey

KW - tiling ramsey

KW - tournaments

UR - https://www.scopus.com/pages/publications/85103174427

U2 - 10.1137/19M1269257

DO - 10.1137/19M1269257

M3 - Article

SN - 0895-4801

VL - 35

SP - 250

EP - 266

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

Transitive tournament tilings in oriented graphs with large minimum total degree

Abstract

Keywords

Access to Document

Fingerprint

Projects

A graph theoretical approach for combinatorial designs

EPSRC Fellowship: Dr Andrew Treglown - Independence in groups, graphs and the integers

Cite this