Hypergraph decomposition
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
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
For hypergraphs, it would be of interest to determine \( U_2(n,3)\), for example. It is known (see [1]) that
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.
|