Detachments of hypergraphs I: The Berge-Johnson problem

DOI10.1017/S0963548312000041MaRDI QIDQ2908122zbMATH OpenOpenAlexFDO

Authors M. A. Bahmanian

Publication date 4 September 2012

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.05804

zbMATH Keywords

detachment of a hypergraphvertex splitting

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Combinatorial aspects of packing and covering (05B40) Coloring of graphs and hypergraphs (05C15) Graph designs and isomorphic decomposition (05C51) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A detachment of a hypergraph is formed by splitting each vertex into one or more subvertices, and sharing the incident edges arbitrarily among the subvertices. For a given edge-colored hypergraph $scrF$, we prove that there exists a detachment $scrG$ such that the degree of each vertex and the multiplicity of each edge in $scrF$ (and each color class of $scrF$) are shared fairly among the subvertices in $scrG$ (and each color class of $scrG$, respectively). Let $(lambd{a}_{1}dots,lambd{a}_m)K_{p_1,dots,p_n}^{h_1,dots,h_m}$ be a hypergraph with vertex partition $V_1,dots,V_n$, $|V_i|=p_i$ for $1leqileqn$ such that there are $lambd{a}_i$ edges of size $h_i$ incident with every $h_i$ vertices, at most one vertex from each part for $1leqileqm$ (so no edge is incident with more than one vertex of a part). We use our detachment theorem to show that the obvious necessary conditions for $(lambd{a}_{1}dots,lambd{a}_m)K_{p_1,dots,p_n}^{h_1,dots,h_m}$ to be expressed as the union $scr{G}_{1}cupldotscupscr{G}_k$ of $k$ edge-disjoint factors, where for $1leqileqk$, $scr{G}_i$ is $r_i$-regular, are also sufficient. Baranyai solved the case of $h_1=dots=h_m$, $lambd{a}_1=dots,lambd{a}_m=1$, $p_1=dots=p_m$, $r_1=dots=r_k$. Berge and Johnson, (and later Brouwer and Tijdeman, respectively) considered (and solved, respectively) the case of $h_i=i$, $1leqileqm$, $p_1=dots=p_m=lambd{a}_1=dots=lambd{a}_m=r_1=dots=r_k=1$. We also extend our result to the case where each $scr{G}_i$ is almost regular.

Recommendations

• Detachments of amalgamated 3-uniform hypergraphs: factorization consequences
• Amalgamations of almost regular edge-colourings of simple graphs
• Detachments of Complete Graphs
• Connected Baranyai's theorem
• Detachments Preserving Local Edge-Connectivity of Graphs

Cites work

• Amalgamations of almost regular edge-colourings of simple graphs
• Amalgamations of connected \(k\)-factorizations.
• Amalgamations of factorizations of complete graphs
• Embedding edge‐colorings into 2‐edge‐connected k‐factorizations of k_kn+1
• Hamilton decompositions of complete graphs with a 3-factor leave.
• Hamilton decompositions of complete multipartite graphs with any 2‐factor leave
• Hamiltonian decompositions of complete graphs
• Hamiltonian decompositions of complete regular s-partite graphs
• Nondisconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs
• On the edge-colouring problem for unions of complete uniform hypergraphs
• Outline and amalgamated triple systems of even index
• The edge-coloring of complete hypergraphs. I
• The reconstruction of latin squares with applications to school timetabling and to experimental design

Cited in

(15)

• On regular set systems containing regular subsystems
• Embedding connected factorizations
• Factorizations of complete multipartite hypergraphs
• Ryser's theorem for \(\rho\)-Latin rectangles
• Disjoint spread systems and fault location
• Embedding factorizations for 3-uniform hypergraphs II: r-factorizations into s-factorizations
• Connected Baranyai's theorem
• Detachments of Complete Graphs
• Detachments of amalgamated 3-uniform hypergraphs: factorization consequences
• Symmetric Layer-Rainbow Colorations of Cubes
• Explicit Baranyai partitions for quadruples, Part I: Quadrupling constructions
• Toward a three-dimensional counterpart of Cruse's theorem
• Ryser's theorem for symmetric -Latin squares
• Embedding connected factorizations. II
• On almost-regular edge colourings of hypergraphs

This page was built for publication: Detachments of hypergraphs I: The Berge-Johnson problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908122)