Toward a three-dimensional counterpart of Cruse’s theorem
HTML articles powered by AMS MathViewer
- by Amin Bahmanian;
- Proc. Amer. Math. Soc. 152 (2024), 1947-1959
- DOI: https://doi.org/10.1090/proc/16714
- Published electronically: March 27, 2024
- HTML | PDF | Request permission
Abstract:
Completing partial latin squares is NP-complete. Motivated by Ryser’s theorem for latin rectangles, in 1974, Cruse found conditions that ensure a partial symmetric latin square of order $m$ can be embedded in a symmetric latin square of order $n$. Loosely speaking, this results asserts that an $n$-coloring of the edges of the complete $m$-vertex graph $K_m$ can be embedded in a one-factorization of $K_n$ if and only if $n$ is even and the number of edges of each color is at least $m-n/2$. We establish necessary and sufficient conditions under which an edge-coloring of the complete $\lambda$-fold $m$-vertex 3-graph $\lambda K_m^3$ can be embedded in a one-factorization of $\lambda K_n^3$. In particular, we prove the first known Ryser type theorem for hypergraphs by showing that if $n\equiv 0\ (\mathrm {mod}\ 3)$, any edge-coloring of $\lambda K_m^3$ where the number of triples of each color is at least $m/2-n/6$, can be embedded in a one-factorization of $\lambda K_n^3$. Finally we prove an Evans type result by showing that if $n\equiv 0\ (\mathrm {mod}\ 3)$ and $n\geq 3m$, then any $q$-coloring of the edges of any $F\subseteq \lambda K_m^3$ can be embedded in a one-factorization of $\lambda K_n^3$ as long as $q\leq \lambda \binom {n-1}{2}-\lambda \binom {m}{3}/\left \lfloor m/3\right \rfloor$.References
- M. A. Bahmanian, Detachments of hypergraphs I: The Berge-Johnson problem, Combin. Probab. Comput. 21 (2012), no. 4, 483–495. MR 2942724, DOI 10.1017/S0963548312000041
- Amin Bahmanian and Chris Rodger, Embedding factorizations for 3-uniform hypergraphs, J. Graph Theory 73 (2013), no. 2, 216–224. MR 3056885, DOI 10.1002/jgt.21669
- Amin Bahmanian, Symmetric layer-rainbow colorations of cubes, SIAM J. Discrete Math. 37 (2023), no. 4, 2617–2625. MR 4665304, DOI 10.1137/22M1494488
- R. A. Bailey, Peter J. Cameron, Cheryl E. Praeger, and Csaba Schneider, The geometry of diagonal groups, Trans. Amer. Math. Soc. 375 (2022), no. 8, 5259–5311. MR 4469221, DOI 10.1090/tran/8507
- Zs. Baranyai, On the factorization of the complete uniform hypergraph, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam-London, 1975, pp. 91–108. MR 416986
- Thomas Britz, Nicholas J. Cavenagh, and Henrik Kragh Sørensen, Maximal partial Latin cubes, Electron. J. Combin. 22 (2015), no. 1, Paper 1.81, 17. MR 3336595, DOI 10.37236/4726
- Darryn Bryant, Nicholas J. Cavenagh, Barbara Maenhaut, Kyle Pula, and Ian M. Wanless, Nonextendible Latin cuboids, SIAM J. Discrete Math. 26 (2012), no. 1, 239–249. MR 2902643, DOI 10.1137/110825534
- Nam-Po Chiang and Hung-Lin Fu, A note on embedding of a latin parallelepiped into a latin cube, Tatung J. XXII (1992), 311–313.
- Charles J. Colbourn and Jeffrey H. Dinitz (eds.), Handbook of combinatorial designs, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007. MR 2246267
- Allan B. Cruse, On embedding incomplete symmetric Latin squares, J. Combinatorial Theory Ser. A 16 (1974), 18–22. MR 329925, DOI 10.1016/0097-3165(74)90068-5
- Allan B. Cruse, On the finite completion of partial Latin cubes, J. Combinatorial Theory Ser. A 17 (1974), 112–119. MR 345854, DOI 10.1016/0097-3165(74)90032-6
- J. Csima, Embedding partial idempotent $d$-ary quasigroups, Pacific J. Math. 80 (1979), no. 2, 351–357. MR 539421, DOI 10.2140/pjm.1979.80.351
- Tristan Denley and Lars-Daniel Öhman, Extending partial Latin cubes, Ars Combin. 113 (2014), 405–414. MR 3186483
- John T. Ethier and Gary L. Mullen, Sets of mutually orthogonal Sudoku frequency squares, Des. Codes Cryptogr. 87 (2019), no. 1, 57–65. MR 3897549, DOI 10.1007/s10623-018-0487-0
- Trevor Evans, Embedding incomplete latin squares, Amer. Math. Monthly 67 (1960), 958–961. MR 122728, DOI 10.2307/2309221
- R. A. Fisher, A system of confounding for factors with more than two alternatives, giving completely orthogonal cubes and higher powers, Ann. Eugenics 12 (1945), 283–290. MR 13113, DOI 10.1111/j.1469-1809.1943.tb02332.x
- Hung-Lin Fu, On Latin $(n\times n\times (n-2))$-parallelepipeds, Tamkang J. Math. 17 (1986), no. 1, 107–111. MR 872667
- J. L. Goldwasser, A. J. W. Hilton, D. G. Hoffman, and Sibel Özkan, Hall’s theorem and extending partial Latinized rectangles, J. Combin. Theory Ser. A 130 (2015), 26–41. MR 3280683, DOI 10.1016/j.jcta.2014.10.007
- R. Häggkvist and T. Hellgren, Extensions of edge-colourings in hypergraphs. I, Combinatorics, Paul Erdős is eighty, Vol. 1, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993, pp. 215–238. MR 1249714
- Roland Häggkvist and Jeannette Janssen, New bounds on the list-chromatic index of the complete graph and other simple graphs, Combin. Probab. Comput. 6 (1997), no. 3, 295–313. MR 1464567, DOI 10.1017/S0963548397002927
- Marshall Hall, An existence theorem for Latin squares, Bull. Amer. Math. Soc. 51 (1945), 387–388. MR 13111, DOI 10.1090/S0002-9904-1945-08361-X
- A. S. Hedayat, N. J. A. Sloane, and John Stufken, Orthogonal arrays, Springer Series in Statistics, Springer-Verlag, New York, 1999. Theory and applications; With a foreword by C. R. Rao. MR 1693498, DOI 10.1007/978-1-4612-1478-6
- Peter Horák, Latin parallelepipeds and cubes, J. Combin. Theory Ser. A 33 (1982), no. 2, 213–214. MR 677575, DOI 10.1016/0097-3165(82)90010-3
- M. Huggan, G. L. Mullen, B. Stevens, and D. Thomson, Sudoku-like arrays, codes and orthogonality, Des. Codes Cryptogr. 82 (2017), no. 3, 675–693. MR 3600882, DOI 10.1007/s10623-016-0190-y
- A. Donald Keedwell and József Dénes, Latin squares and their applications, 2nd ed., Elsevier/North-Holland, Amsterdam, 2015. With a foreword to the previous edition by Paul Erdös. MR 3495977
- K. Kishen, On latin and hyper-graeco-latin cubes and hyper-cubes, Curr. Sci. 11 (1942), 98–99.
- K. Kishen, On the construction of latin and hyper-graeco-latin cubes and hypercubes, J. Indian Soc. Agric. Statist. 2 (1949), 20–48. MR 34743
- Martin Kochol, Latin $(n\times n\times (n-2))$-parallelepipeds not completing to a Latin cube, Math. Slovaca 39 (1989), no. 2, 121–125 (English, with Russian summary). MR 1018253
- Martin Kochol, Latin parallelepipeds not completing to a cube, Math. Slovaca 41 (1991), no. 1, 3–9. MR 1094977
- Martin Kochol, Relatively narrow Latin parallelepipeds that cannot be extended to a Latin cube, Ars Combin. 40 (1995), 247–260. MR 1352785
- Martin Kochol, Non-extendible Latin parallelepipeds, Inform. Process. Lett. 112 (2012), no. 24, 942–943. MR 2979500, DOI 10.1016/j.ipl.2012.08.014
- Denis S. Krotov and Ev V. Sotnikova, Embedding in $q$-ary 1-perfect codes and partitions, Discrete Math. 338 (2015), no. 11, 1856–1859. MR 3357771, DOI 10.1016/j.disc.2015.04.014
- Jaromy Kuhl and Tristan Denley, Some partial Latin cubes and their completions, European J. Combin. 32 (2011), no. 8, 1345–1352. MR 2838020, DOI 10.1016/j.ejc.2011.05.003
- Charles J. Colbourn and Jeffrey H. Dinitz (eds.), Handbook of combinatorial designs, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007. MR 2246267
- Charles C. Lindner, A finite partial idempotent Latin cube can be embedded in a finite idempotent latin cube, J. Combinatorial Theory Ser. A 21 (1976), no. 1, 104–109. MR 441759, DOI 10.1016/0097-3165(76)90052-2
- Zur Luria. New bounds on the number of n-queens configurations. arXiv e-prints, page arXiv:1705.05225, May 2017.
- O. Marcotte and P. D. Seymour, Extending an edge-coloring, J. Graph Theory 14 (1990), no. 5, 565–573. MR 1073098, DOI 10.1002/jgt.3190140508
- Brendan D. McKay and Ian M. Wanless, A census of small Latin hypercubes, SIAM J. Discrete Math. 22 (2008), no. 2, 719–736. MR 2399374, DOI 10.1137/070693874
- V. N. Potapov, On the complementability of partial $n$-quasigroups of order 4, Mat. Tr. 14 (2011), no. 2, 147–172 (Russian, with Russian summary); English transl., Siberian Adv. Math. 22 (2012), no. 2, 135–151. MR 2961772, DOI 10.3103/s1055134412020058
- Vladimir N. Potapov, Constructions of pairs of orthogonal Latin cubes, J. Combin. Des. 28 (2020), no. 8, 604–613. MR 4113541, DOI 10.1002/jcd.21718
- Vladimir N. Potapov, Embedding in MDS codes and Latin cubes, J. Combin. Des. 30 (2022), no. 9, 626–633. MR 4453977, DOI 10.1002/jcd.21849
- H. J. Ryser, A combinatorial theorem with an application to latin rectangles, Proc. Amer. Math. Soc. 2 (1951), 550–552. MR 42361, DOI 10.1090/S0002-9939-1951-0042361-0
- A. A. Taranenko, On the numbers of 1-factors and 1-factorizations of hypergraphs, Discrete Math. 340 (2017), no. 4, 753–762. MR 3603556, DOI 10.1016/j.disc.2016.11.024
Bibliographic Information
- Amin Bahmanian
- Affiliation: Department of Mathematics, Illinois State University, Normal, Illinois 61790-4520
- MR Author ID: 984318
- ORCID: 0000-0002-7324-4028
- Received by editor(s): November 18, 2022
- Received by editor(s) in revised form: June 16, 2023, September 14, 2023, and November 2, 2023
- Published electronically: March 27, 2024
- Communicated by: Isabella Novik
- © Copyright 2024 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 152 (2024), 1947-1959
- MSC (2020): Primary 05B15, 05C70, 05C65, 05C15
- DOI: https://doi.org/10.1090/proc/16714
- MathSciNet review: 4728465