Decomposition of large combinatorial structures
type: Item
instance of: scholarly article
title: Decomposition of large combinatorial structures
zbMATH Open document ID: 0653.05053
DOI: 10.1007/BF01194393
author: Yair Caro
published in: Archiv der Mathematik
publication date: 1989-01-01T00:00:00Z
review text: Let H be a hypergraph and let F be a family of hypergraphs. A partition of the edge set of H is called an F-decomposition if each set from the partition induces in H a hypergraph isomorphic to a member of F. Let \(F_{n,k}(p,q)\) be an n-uniform hypergraph with vertex set X and edge set \(E=\{e_ 1,...,e_ k\}\) satisfying the conditions: (1) there is \(P\subseteq X,| P| =p\), such that for every \(2\leq i<j\leq k\) \(e_ i\cap e_ j=P\), (2) there is \(Q\subseteq P,| Q| =q\), such that for every \(2\leq i\leq k\) \(e_ i\cap e_ 1=Q\). Let \(\Pi_{n,k,r}=\{F_{n,k}(p,q):\) \(0\leq q\leq p\leq r\leq n-1\}.\) We prove the following theorem: Let n,k,r be given integers, \(0\leq r\leq n-1\). There exist a positive constant \(c=c(n,k,r)\) and a minimal integer C(n,k,r) such that every n- uniform hypergraph H with e(H)\(\geq C(n,k,r)\) and \(\Delta\) (H)\(\leq ce(H)\) has a \(\Pi_{n,k,r}\)-decomposition. \((e(H)=| E(H)|\) and \(\Delta\) (H) is the maximal degree of a vertex in H.) This result improves and generalizes earlier results of Alon, Caro, and Lonc and Truszczynski. Generalizations to other combinatorial structures are given.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4065038
zbMATH Keywords: family of hypergraphs
zbMATH Keywords: decomposition
zbMATH Keywords: uniform hypergraph
zbMATH Keywords: generalizations to other combinatorial structures
zbMATH Keywords: edge partition
MaRDI profile type: Publication
cites work: A note on the decomposition of graphs into isomorphic matchings
cites work: The decomposition of trees into subtrees
cites work: Q3752404
cites work: Q4120601
cites work: NP-completeness of graph decomposition problems
cites work: Intersection Theorems for Systems of Sets
cites work: Decomposition of large uniform hypergraphs
cites work: Q3741644
cites work: Q3758841
description: scientific article; zbMATH DE number 4065038