Decomposition of large uniform hypergraphs

Generalized Ramsey theory (05C55) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

For any nonnegative integer k,n,p,q,q\(\leq p\) let \(F_{n,k}(p,q)\) be an n-uniform hypergraph with the vertex set X and the edge set \({\mathcal 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 X\), \(| Q| =q\), such that for every \(2\leq i\leq k\), \(E_ 1\cap E_ i=Q\). \((F_{n,k}(p,p)\) is the well-known \(\Delta\)-system.) Let \({\mathcal F}_{n,k}=\{F_{n,k}(p,q):\quad 0\leq q\leq p\leq n-1\}.\) The main result of the paper is Theorem: There is an integer \(\psi\) (n,k) such that every n-uniform hypergraph H with edge number e(H) satisfying conditions e(H)\(\equiv 0\) (mod k) (this is a trivial necessity) and e(H)\(\geq \psi (n,k)\) has an \({\mathcal F}_{n,k}\)-decomposition such that there is a partition of \({\mathcal E}(H)\) each set which is isomorphic to a hypergraph from \({\mathcal F}_{n,k}\). The authors prove, that \(\psi (n,k)\leq \phi (n,(k-1)(\phi (n,k-1))+n),\) where \(\phi\) (n,k) is the well-known Erdős- Rado function for the existence of \(\Delta\)-systems.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Decomposition of large uniform hypergraphs

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