Decomposition of large uniform hypergraphs (Q762500)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposition of large uniform hypergraphs |
scientific article |
Statements
Decomposition of large uniform hypergraphs (English)
0 references
1985
0 references
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.
0 references
tournament poset
0 references
Erdős-Rado theorem
0 references
Ramsey type theorem
0 references
uniform hypergraph
0 references
decomposition
0 references