Partitioning the edge set of a hypergraph into almost regular cycles. (English) Zbl 1402.05173

Bahmanian, Amin; Haghshenas, Sadegheh

J. Comb. Des. 26, No. 10, 465-479 (2018).

Summary: A cycle of length \(t\) in a hypergraph is an alternating sequence \(v_1,e_1,v_2,\ldots,v_t,e_t\) of distinct vertices \(v_i\) and distinct edges \(e_i\) so that \(\{v_i,v_{i+1}\}\subseteq e_i\)(with \(v_{t+1}:=v_1\)). Let \(\lambda K_n^h\) be the \(\lambda\)-fold \(n\)-vertex complete \(h\)-graph. Let \(\mathcal{G}=(V,E)\) be a hypergraph all of whose edges are of size at least \(h\), and \(2\leq c_1\leq\cdots\leq c_k\leq|V|\). In order to partition the edge set of \(\mathcal{G}\) into cycles of specified lengths \(c_1,\ldots,c_k\), an obvious necessary condition is that \(\sum_{i=1}^kc_i=|E|\). We show that this condition is sufficient in the following cases.
(R1) \(h\geq\max\{c_k,\lceil n/2\rceil+1\}\).
(R2) \(\mathcal{G}=\lambda K_n^h,\;h\geq\lceil n/2\rceil+2\).
(R3) \(\mathcal{G}=K_n^h,\;c_1=\cdots=c_k:=c,c|n(n-1),\;n\geq85\).
In (R2), we guarantee that each cycle is almost regular. In (R3), we also solve the case where a “small” subset \(L\) of edges of \(K^h_n\) is removed.

MSC:

05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C65	Hypergraphs
05C38	Paths and cycles
05C45	Eulerian and Hamiltonian graphs

Keywords:

almost regular; Baranyai’s theorem; complete uniform hypergraph; cycle; circle; partition; Hamiltonicity; Kruskal-Katona theorem