Indecomposable regular graphs and hypergraphs (Q1197014)

A hypergraph \(H\) consists of a finite nonempty set \(V(H)\) called the vertex set and a collection \(E(H)\) (called the edge set of \(H)\) of subsets of the power set of \(V(H)\). Note \(E(H)\) may contain the same set more then once. The number of times an element \(e\) in \(E(H)\) appears in \(E(H)\) is called its multiplicity denoted by \(m_ H(e)\). If each edge of \(H\) appears exactly once in \(E(H)\), \(H\) is said to be a simple hypergraph. A hypergraph is a \(k\)-uniform hypergraph if each edge contains \(k\) elements. The 2-uniform hypergraphs are graphs. The degree of a vertex \(v\) in \(H\) is defined by \(\deg_ H(v)=\Sigma(m_ H(e)\mid v\in e\in E(H))\). The hypergraph \(H\) is \(d\)-regular if \(\deg_ H(v)=d\) for all \(v\in V(H)\). A subhypergraph is a spanning subhypergraph if \(\cup E(F)=\cup E(H)\). The hypergraph \(H\) is indecomposable if it contains no proper non-empty regular spanning subhypergraph. It is shown that if \(d>\sqrt n-1\) and if \(G\) is a simple \(d\)-regular graph on \(n\) vertices, then \(G\) contains a proper regular spanning subhypergraph; and if \(G\) is a \(d\)-regular multigraph with \(n\) vertices such that \(d>(n-1)/3\), then \(G\) contains a proper regular spanning subgraph. It is shown that these bounds are sharp for odd \(d\). For \(n\geq k\geq 1\), \(D(n,k)\) is the maximum possible \(d\) such that there exists a \(d\)-regular indecomposable \(k\)- uniform hypergrah on \(n\) vertices. Alon and Berman conjectured that \(D(n,k)\leq n^{c(k)}\) where \(c(k)\) depends on \(k\) only. This conjecture is disproved in this paper by constructing examples that show that \(D(n,3)\geq 2^{(n-6)/2}\).