Hypergraph decomposition

A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).

For \( r\)-graphs \( H_1,\dots,H_k\) with the same number of edges, a \( U\)-decomposition (first suggested by Stanislaw Ulam) is a family of partitions of each of the edge sets \( E(H_i)\) into \( t\) mutually isomorphic sets, i.e., \( E(H_i)=\cup_{j=1}^t E_{ij}\), where for each \( j\), all the \( E_{ij}\) are isomorphic. Let \( U_k(n,r)\) denote the least possible value \( m\) such that all families of \( k\) \( r\)-graphs must have a \( U\)-decompositions into \( t\) isomorphic sets.

A problem on decompositions of hypergraphs (proposed by Chung, Erdös and Graham [1])

Determine \(U_k(n,r)\).

For graphs, it was shown [2], [3], [1] that

\(\displaystyle \frac 2 3 n -\frac 1 3 < U_2(n,2) < \frac 2 3 n + c \)

and for \( k \geq 3\),

\(\displaystyle \frac 3 4 n -\sqrt{n-1} < U_k(n,2) < \frac 3 4 n + c_k.\)

There is still room for some improvement here.

For hypergraphs, it would be of interest to determine \( U_2(n,3)\), for example. It is known (see [1]) that

\(\displaystyle c_1 n^{4/3} \log \log n / \log n < U_2(n,3) < c_2 n^{4/3}. \)

Also, for \( \epsilon >0\),

\(\displaystyle c_3 n^{2-2/k-\epsilon} < U_k(n,3) < c_4 n^{2-1/k}. \)

Bibliography
1 F. R. K. Chung, P. Erdös and R. L. Graham, Minimal decompositions of hypergraphs into mutually isomorphic subhypergraphs, J. Comb. Theory Ser. A 32 (1982), 241-251.

2 F. R. K. Chung, P. Erdös, R. L. Graham, S. M. Ulam and F. F. Yao, Minimal decompositions of two graphs into pairwise isomorphic subgraphs, Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, FL, 1979), Congress. Numer. XXIII, 3-18, Utilitas Math., Winnipeg, Man., 1979.

3 F. R. K. Chung, P. Erdös and R. L. Graham, Minimal decompositions of graphs into mutually isomorphic subgraphs, Combinatorica 1 (1981), 13-24.