Decomposition of large combinatorial structures
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.
generalizations to other combinatorial structures
scientific article; zbMATH DE number 4065038
scientific article