Minimalist designs

Ben Barber; Stefan Glock; Daniela Kühn; Allan Lo; Richard Montgomery; Deryk Osthus

doi:10.1002/rsa.20915

Minimalist designs

Ben Barber, Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery, Deryk Osthus^*

^*Corresponding author for this work

Mathematics

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

3 Citations (Scopus)

Abstract

The iterative absorption method has recently led to major progress in the area of (hyper-)graph decompositions. Among other results, a new proof of the existence conjecture for combinatorial designs, and some generalizations, was obtained. Here, we illustrate the method by investigating triangle decompositions: We give a simple proof that a triangle-divisible graph of large minimum degree has a triangle decomposition and prove a similar result for quasi-random host graphs.

Original language	English
Pages (from-to)	47-63
Number of pages	17
Journal	Random Structures and Algorithms
Volume	57
Issue number	1
DOIs	https://doi.org/10.1002/rsa.20915
Publication status	Published - 1 Aug 2020

Bibliographical note

Publisher Copyright:
© 2020 Wiley Periodicals, Inc.

Keywords

design theory
extremal graph theory
iterative absorption
triangle decomposition

ASJC Scopus subject areas

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Access to Document

10.1002/rsa.20915

Cite this

@article{e0efc8e857ba4903b1ec2155a0d19a1b,

title = "Minimalist designs",

abstract = "The iterative absorption method has recently led to major progress in the area of (hyper-)graph decompositions. Among other results, a new proof of the existence conjecture for combinatorial designs, and some generalizations, was obtained. Here, we illustrate the method by investigating triangle decompositions: We give a simple proof that a triangle-divisible graph of large minimum degree has a triangle decomposition and prove a similar result for quasi-random host graphs.",

keywords = "design theory, extremal graph theory, iterative absorption, triangle decomposition",

author = "Ben Barber and Stefan Glock and Daniela K{\"u}hn and Allan Lo and Richard Montgomery and Deryk Osthus",

note = "Publisher Copyright: {\textcopyright} 2020 Wiley Periodicals, Inc.",

year = "2020",

month = aug,

day = "1",

doi = "10.1002/rsa.20915",

language = "English",

volume = "57",

pages = "47--63",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "1",

}

TY - JOUR

T1 - Minimalist designs

AU - Barber, Ben

AU - Glock, Stefan

AU - Kühn, Daniela

AU - Lo, Allan

AU - Montgomery, Richard

AU - Osthus, Deryk

PY - 2020/8/1

Y1 - 2020/8/1

N2 - The iterative absorption method has recently led to major progress in the area of (hyper-)graph decompositions. Among other results, a new proof of the existence conjecture for combinatorial designs, and some generalizations, was obtained. Here, we illustrate the method by investigating triangle decompositions: We give a simple proof that a triangle-divisible graph of large minimum degree has a triangle decomposition and prove a similar result for quasi-random host graphs.

AB - The iterative absorption method has recently led to major progress in the area of (hyper-)graph decompositions. Among other results, a new proof of the existence conjecture for combinatorial designs, and some generalizations, was obtained. Here, we illustrate the method by investigating triangle decompositions: We give a simple proof that a triangle-divisible graph of large minimum degree has a triangle decomposition and prove a similar result for quasi-random host graphs.

KW - design theory

KW - extremal graph theory

KW - iterative absorption

KW - triangle decomposition

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

U2 - 10.1002/rsa.20915

DO - 10.1002/rsa.20915

M3 - Article

AN - SCOPUS:85081888344

SN - 1042-9832

VL - 57

SP - 47

EP - 63

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

ER -

Minimalist designs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this