Survey on balanced graph and hypergraph designs (Q7033398)

Let \(V\) be a \(v\)-set, \(K_v\) be the complete graph on \(V\). Let \(G=(X,\mathcal{E})\) be a graph on \(n\) vertices. A \(G\)-design is a pair \(\Sigma=(V,\mathcal{B})\), where \(\mathcal{B}=\{G_1,\dots, G_b\}\), such that: \N\begin{itemize}\N\item[(1)] \(G_i\cong G\) for any \(i=1,\dots,b\); \N\item[(2)] for any \(x, y\in V\), \(x\neq y\), there exists a \(G_i\) such that \(\{x, y\}\in E(G_i)\) for \(i=1,\dots, b\).\N\end{itemize}\N\NThe elements of \(\mathcal{B}\) are called blocks. The degree of a vertex \(x\in V\) is the number of blocks of \(\mathcal{B}\) containing \(x\). \(\Sigma\) is called balanced if there exists \(d\in N\) such that \(d(x)= d\) for all \(x\in V\). \(\Sigma\) is usually called a \(G\)-decomposition of \(K_v\).\N\NLet \(K_v^{(3)}\) be the complete \(3\)-uniform hypergraph on \(V\) and let \( H=(X,\mathcal{E})\) be a 3-uniform hypergraph with \(n =|X|\) and \(m=|E|\). An \(H\)-design is a pair \(\Sigma=(V,\mathcal{B})\), where \(\mathcal{B}=\{H_1,\dots, H_b\}\) satisfies \N\begin{itemize}\N\item[(1)] \(H_i\cong H\) for any \(i=1,\dots,b\) and \N\item[(2)] for any \(x, y, z\in V,\) pairwise different, there exists an \(H_i\) such that such that \(\{x,y,z\} \in E(H_i)\) for \(i=1,\dots, b\).\N\end{itemize}\NThe elements of \(\mathcal{B}\) are called blocks and we say that \(\sum\) is an \(H\)-decomposition \(K_v^{(3)}\). The definition of balanced (strongly balanced) hypergraph design is analogous to the one given in the case of graph designs.\N\NIn this paper, the authors summarize some known results on balanced, strongly balanced, locally balanced, and strictly balanced \(G\)-designs. They consider some general cases such as those of cycles, paths, stars, and complete bipartite graphs, and examine the case of graphs with few vertices. For the hypergraph design case, they summarize some known results on balanced (strongly balanced) 3-hypergraphs.