Minimalist designs

DOI10.1002/RSA.20915MaRDI QIDQ5120741zbMATH OpenOpenAlexFDO

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

Publication date 16 September 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.06956

zbMATH Keywords

design theoryextremal graph theoryiterative absorptiontriangle decomposition

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph designs and isomorphic decomposition (05C51) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The iterative absorption method has recently led to major progress in the area of (hyper-)graph decompositions. Amongst 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.

Recommendations

• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• Edge-decompositions of graphs with high minimum degree
• On the minimum degree required for a triangle decomposition
• Fractional triangle decompositions in graphs with large minimum degree
• Coloured and directed designs

Cites work

• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• Clique decompositions of multipartite graphs and completion of Latin squares
• Counting designs
• Edge-decompositions of graphs with high minimum degree
• Edge-disjoint Hamilton cycles in random graphs
• Fractional clique decompositions of dense graphs and hypergraphs
• Fractional clique decompositions of dense partite graphs
• Fractional triangle decompositions in graphs with large minimum degree
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• scientific article; zbMATH DE number 4215352 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Integer and fractional packings in dense graphs
• Nearly perfect matchings in regular simple hypergraphs
• On a hypergraph matching problem
• On a packing and covering problem
• On the decomposition threshold of a given graph
• On the exact decomposition threshold for even cycles
• Optimal packings of bounded degree trees
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• The minimum degree threshold for perfect graph packings
• Triangle Factors in Random Graphs
• Vertex coverings by monochromatic cycles and trees

Cited in

(14)

• Progress towards Nash-Williams' conjecture on triangle decompositions
• Minimal elements for product orders
• scientific article; zbMATH DE number 933212 (Why is no real title available?)
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• Substructures in Latin squares
• Large deviations in random latin squares
• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• Threshold for Steiner triple systems
• Graph and hypergraph packing
• Cycle decompositions in \(k\)-uniform hypergraphs
• k-independent Boolean networks
• Steiner triple systems with high discrepancy
• Toward a high-dimensional Dirac's theorem
• High-girth Steiner triple systems

This page was built for publication: Minimalist designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5120741)