×

zbMATH — the first resource for mathematics

Embedding factorizations for 3-uniform hypergraphs. (English) Zbl 1264.05088
Summary: In this article, two results are obtained on a hypergraph embedding problem. The proof technique is itself of interest, being the first time amalgamations have been used to address the embedding of hypergraphs. The first result finds necessary and sufficient conditions for the embedding a hyperedge-colored copy of the complete 3-uniform hypergraph of order \(m\), \(K^{3}_m\), into an \(r\)-factorization of \(K^{3}_n\), providing that \(n>2m+(-1+\sqrt{8m^{2}-16m-7}/2\). The second result finds necessary and sufficient conditions for an embedding when not only are the colors of the hyperedges of \(K^{3}_m\) given, but also the colors of all the “pieces” of hyperedges on these \(m\) vertices are prescribed (the “pieces” of hyperedges are eventually extended to hyperedges of size 3 in \(K^{3}_n\) by adding new vertices to the hyperedges of size 1 and 2 during the embedding process). Both these results make progress toward settling an old question of Cameron on completing partial 1-factorizations of hypergraphs.

MSC:
05C65 Hypergraphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] M. A. Bahmanian Detachments of amalgamated 3-uniform hypergrpahs: Factorization consequences J Comb Des
[2] M. A. Bahmanian Detachments of hypergraphs I: The Berge-Johnson problem Combinatorics, Probability and Computing 10.1017/S0963548312000041
[3] Baranyai, Colloquia Mathematica Societatis Janos Bolyai pp 91– (1975)
[4] Zs. Baranyai A. E. Brouwer Extension of colorings of the edges of a complete (uniform hyper)graph 1977 · Zbl 0362.05059
[5] Bryant, A proof of Lindner’s conjecture on embeddings of partial Steiner triple systems, J Combin Des 17 pp 63– (2009) · Zbl 1221.05029 · doi:10.1002/jcd.20189
[6] Cameron, London Math. Soc. Lecture Note Ser., vol. 23 (1976)
[7] Doyen, Embeddings of Steiner triple systems, Discrete Math 5 pp 229– (1973) · Zbl 0263.05017 · doi:10.1016/0012-365X(73)90139-8
[8] Häggkvist, Paul Erdos is eighty, 1 pp 215– (1993)
[9] Hall, An existence theorem for Latin squares, Bull Amer Math Soc 51 pp 387– (1945) · Zbl 0060.02801 · doi:10.1090/S0002-9904-1945-08361-X
[10] Hilton, Hamiltonian decompositions of complete graphs, J Combin Theory B 36 pp 125– (1984) · Zbl 0542.05044 · doi:10.1016/0095-8956(84)90020-0
[11] Hilton, Amalgamations of connected k-factorizations, J Combin Theory B 88 pp 267– (2003) · Zbl 1033.05084 · doi:10.1016/S0095-8956(03)00030-3
[12] Hilton, Hamiltonian decompositions of complete regular s-partite graphs, Discrete Math 58 pp 63– (1986) · Zbl 0593.05047 · doi:10.1016/0012-365X(86)90186-X
[13] Kirkman, On a problem in combinations, Camb Dublin Math J 2 pp 191– (1847)
[14] Johnson, Amalgamations of factorizations of complete graphs, J Combin Theory B 97 pp 597– (2007) · Zbl 1153.05055 · doi:10.1016/j.jctb.2006.09.004
[15] Lindner, A partial Steiner triple system of order n can be embedded in a Steiner triple system of order 6n+3, J Comb Theory Ser A 18 pp 349– (1975) · Zbl 0304.05005 · doi:10.1016/0097-3165(75)90046-1
[16] Nash-Williams, Amalgamations of almost regular edge-colourings of simple graphs, J Combin Theory B 43 pp 322– (1987) · Zbl 0654.05031 · doi:10.1016/0095-8956(87)90008-6
[17] Rodger, Embedding edge-colorings into 2-edge-connected k-factorizations of Kkn+1, J Graph Theory 10 pp 169– (1995) · Zbl 0815.05050 · doi:10.1002/jgt.3190190205
[18] Ryser, A combinatorial theorem with an application to Latin rectangles, Proc Amer Math Soc 2 pp 550– (1951) · Zbl 0043.01202 · doi:10.1090/S0002-9939-1951-0042361-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.