A survey of Heffter arrays. (English) Zbl 07921208
Colbourn, Charles J. (ed.) et al., New advances in designs, codes and cryptography, Stinson66, Toronto, Canada, June 13–17, 2022. Cham: Springer. Fields Inst. Commun. 86, 353-392 (2024).
Summary: Heffter arrays were introduced by D. S. Archdeacon et al. [Des. Codes Cryptography 77, No. 2–3, 409–426 (2015; Zbl 1323.05025)] as an interesting link between combinatorial designs and topological graph theory. Since the initial paper on this topic, there has been a good deal of interest in Heffter arrays. This survey presents an overview of the current state of the art of this topic. We begin with an introduction to Heffter arrays for the reader who is unfamiliar with the subject. Then we give a unified and comprehensive presentation of the major results, showing some proof methods. Connections of Heffter arrays to several other combinatorial objects are discussed, such as problems on partial sums and sequenceability, biembedding graphs on surfaces, difference families, and orthogonal graph decompositions. Then, proposed variants and generalizations of Heffter arrays are examined. A list of unsolved problems and an updated and complete bibliography are provided.
For the entire collection see [Zbl 1537.05001].
For the entire collection see [Zbl 1537.05001].
MSC:
| 05B30 | Other designs, configurations |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
Citations:
Zbl 1323.05025References:
| [1] | Abel, R.J.R., Buratti, M.: Difference families. In: Colbourn, C.J., Dinitz, J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn. Chapman & Hall/CRC, Boca Raton (2007) · Zbl 1101.05001 |
| [2] | Alon, N., Combinatorial Nullstellensatz. Comb. Probab. Comput., 8, 7-29, 1999 · Zbl 0920.05026 · doi:10.1017/S0963548398003411 |
| [3] | Alspach, B., Liversidge, G.: On strongly sequenceable abelian groups. Art Discret. Appl. Math. 3, #P1.02 (2020) · Zbl 1441.20015 |
| [4] | Alspach, B.; Kreher, DL; Pastine, A., The Friedlander-Gordon-Miller conjecture is true, Australas. J. Comb., 67, 11-24, 2017 · Zbl 1406.20049 |
| [5] | Alspach, B.; Heinrich, K.; Liu, G.; Dinitz, JH; Stinson, DR, Orthogonal factorizations of graphs, Contemporary Design Theory: A Collection of Surveys, 13-40, 1992, New York: Wiley, New York · Zbl 0779.05032 |
| [6] | Anderson, B., Sequencings of certain dihedral groups. In: Proceedings of Sixth S.E. Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 14, 65-76, 1975 · Zbl 0363.20046 |
| [7] | Archdeacon, D.S.: Heffter arrays and biembedding graphs on surfaces. Electron. J. Comb. 22, #P1.74 (2015) · Zbl 1310.05142 |
| [8] | Archdeacon, DS; Boothby, T.; Dinitz, JH, Tight Heffter arrays exist for all possible values, J. Comb. Des., 25, 5-35, 2017 · Zbl 1362.05029 · doi:10.1002/jcd.21520 |
| [9] | Archdeacon, DS; Dinitz, JH; Donovan, DM; Yazıcı, EŞ, Square integer Heffter arrays with empty cells, Des. Codes Cryptogr., 77, 409-426, 2015 · Zbl 1323.05025 · doi:10.1007/s10623-015-0076-4 |
| [10] | Archdeacon, DS; Dinitz, JH; Mattern, A.; Stinson, DR, On partial sums in cyclic groups, J. Comb. Math. Comb. Comput., 98, 327-342, 2016 · Zbl 1353.05067 |
| [11] | Bode, JP; Harborth, H., Directed paths of diagonals within polytopes, Discret. Math., 299, 3-10, 2005 · Zbl 1073.05038 · doi:10.1016/j.disc.2005.05.006 |
| [12] | Bryant, D., El-Zanati, S.: Graph decompositions. In: Colbourn, C.J., Dinitz, J.H. (eds.) Handbook of Combinatorial Designs, 2nd edn. Chapman & Hall/CRC, Boca Raton (2007) · Zbl 1101.05001 |
| [13] | Bryant, D., Gavlas, H., Ling, A.C.H.: Skolem-type difference sets for cycles. Electron. J. Comb. 10, #R38 (2003) · Zbl 1031.05102 |
| [14] | Buratti, M.; Colbourn, CJ; Dinitz, JH, Tight Heffter arrays from finite fields, New Advances in Designs, Codes and Cryptography, 25-36, 2024, Cham: Springer Nature, Cham · Zbl 07921191 |
| [15] | Buratti, M.: A description of any regular or 1-rotational design by difference methods, extended abstract in Combinatorics (2000) |
| [16] | Buratti, M.; Del Fra, A., Existence of cyclic k-cycle systems of the complete graph, Discret. Math., 261, 113-125, 2003 · Zbl 1013.05023 · doi:10.1016/S0012-365X(02)00463-6 |
| [17] | Buratti, M.; Rinaldi, G., A non-existence result on cyclic cycle-decompositions of the cocktail party graph, Discret. Math., 309, 4722-4726, 2009 · Zbl 1214.05114 · doi:10.1016/j.disc.2008.05.042 |
| [18] | Buratti, M.; Pasotti, A., Graph decompositions with the use of difference matrices, Bull. Inst. Comb. Appl., 47, 23-32, 2006 · Zbl 1107.05072 |
| [19] | Buratti, M., Pasotti A.: Heffter spaces, in preparation. https://arxiv.org/abs/2401.03940 |
| [20] | Buratti, M.; Stinson, DR, New results on modular Golomb rulers, optical orthogonal codes and related structures, Ars Math. Contemp., 20, 1-27, 2021 · Zbl 1469.05021 · doi:10.26493/1855-3974.2374.9ff |
| [21] | Burgess, AC; Cavenagh, NJ; Pike, DA, Mutually orthogonal cycle systems, Ars Math. Contemp., 23, P2.05, 2023 · Zbl 1506.05038 · doi:10.26493/1855-3974.2692.86d |
| [22] | Burrage, K., Cavenagh, N.J., Donovan, D., Yazıcı, E.Ş.: Globally simple Heffter arrays \(H(n;k)\) when \(k\equiv 0,3 \pmod{4} \). Discret. Math. 343, 111787 (2020) · Zbl 1435.05040 |
| [23] | Cavenagh, NJ; Dinitz, JH; Donovan, D.; Yazıcı, EŞ, The existence of square non-integer Heffter arrays, Ars Math. Contemp., 17, 369-395, 2019 · Zbl 1433.05064 · doi:10.26493/1855-3974.1817.b97 |
| [24] | Cavenagh, NJ; Donovan, D.; Yazıcı, EŞ, Biembeddings of cycle systems using integer Heffter arrays, J. Comb. Des., 28, 900-922, 2020 · Zbl 07840145 · doi:10.1002/jcd.21753 |
| [25] | Colbourn, CJ; Rosa, A., Triple Systems, 1999, Oxford: Clarendon Press, Oxford · Zbl 0938.05009 · doi:10.1093/oso/9780198535768.001.0001 |
| [26] | Costa, S.: Biembeddings of Archdeacon type: their full automorphism group and their number, https://arxiv.org/abs/2205.02066 |
| [27] | Costa, S.; Dalai, M.; Pasotti, A., A tour problem on a toroidal board, Australas. J. Comb., 76, 183-207, 2020 · Zbl 1439.05044 |
| [28] | Costa, S.; Della Fiore, S., Weak sequenceability in cyclic groups, J. Comb. Des., 30, 735-751, 2022 · Zbl 1529.05084 · doi:10.1002/jcd.21862 |
| [29] | Costa, S., Della Fiore, S.: Existence on \(\lambda \)-fold non-zero sum Heffter arrays through local considerations. Austral. J. Combin. 87, 301-339 (2023) · Zbl 1527.05030 |
| [30] | Costa, S., Della Fiore, S., Ollis, M.A.: Sequencing in semidirect products via the polynomial method, https://arxiv.org/abs/2301.09367 |
| [31] | Costa, S., Della Fiore, S., Ollis, M.A., Rovner-Frydman, S.Z.: On sequences in cyclic groups with distinct partial sums. Electron. J. Comb. 29, #P3.33 (2022) · Zbl 07582303 |
| [32] | Costa, S.; Della Fiore, S.; Pasotti, A., Non-zero sum Heffter arrays and their applications, Discret. Math., 345, 112925, 2022 · Zbl 1491.05041 · doi:10.1016/j.disc.2022.112952 |
| [33] | Costa, S., Mella, L.: A class of highly symmetric Archdeacon embeddings. Australas. J. Combin. https://arxiv.org/abs/2212.08491 |
| [34] | Costa, S.; Mella, L.; Pasotti, A., Weak Heffter arrays and biembedding graphs on non-orientable surfaces, Electron. J. Combin., 31, 1-8, 2024 · Zbl 1533.05042 · doi:10.37236/11891 |
| [35] | Costa, S.; Morini, F.; Pasotti, A.; Pellegrini, MA, A problem on partial sums in abelian groups, Discret. Math., 341, 705-712, 2018 · Zbl 1378.05214 · doi:10.1016/j.disc.2017.11.013 |
| [36] | Costa, S.; Morini, F.; Pasotti, A.; Pellegrini, MA, Globally simple Heffter arrays and orthogonal cyclic cycle decompositions, Australas. J. Comb., 72, 549-593, 2018 · Zbl 1405.05018 |
| [37] | Costa, S.; Morini, F.; Pasotti, A.; Pellegrini, MA, A generalization of Heffter arrays, J. Comb. Des., 28, 171-206, 2020 · Zbl 1536.05109 · doi:10.1002/jcd.21684 |
| [38] | Costa, S., Pasotti, A.: On \(\lambda \)-fold relative Heffter arrays and biembedding multigraphs on surfaces. Eur. J. Comb. 97, 103370 (2021) · Zbl 1469.05022 |
| [39] | Costa, S., Pasotti, A.: On the number of non-isomorphic (simple) k-gonal biembeddings of complete multipartite graphs. doi:10.26493/1855-3974.2910.5b3 |
| [40] | Costa, S.; Pasotti, A.; Pellegrini, MA, Relative Heffter arrays and biembeddings, Ars Math. Contemp., 18, 241-271, 2020 · Zbl 1464.05030 · doi:10.26493/1855-3974.2110.6f2 |
| [41] | Costa, S.; Pellegrini, MA, Some new results about a conjecture by Brian Alspach, Archiv der Mathematik, 115, 479-488, 2020 · Zbl 1530.20066 · doi:10.1007/s00013-020-01507-7 |
| [42] | Dinitz, JH; Mattern, ARW, Biembedding Steiner triple systems and n-cycle systems on orientable surfaces, Australas. J. Comb., 67, 327-344, 2017 · Zbl 1375.05035 |
| [43] | Dinitz, JH; Wanless, IM, The existence of square integer Heffter arrays, Ars Math. Contemp., 13, 81-93, 2017 · Zbl 1379.05021 · doi:10.26493/1855-3974.1121.fbf |
| [44] | Donovan, DM; Griggs, TS; Lefevre, GJ; McCourt, TA, Cyclic biembeddings of twofold triple systems, Ann. Comb., 16, 57-74, 2014 · Zbl 1295.05085 · doi:10.1007/s00026-013-0211-8 |
| [45] | Donovan, DM; Griggs, TS; Lefevre, GJ; McCourt, TA, Further biembeddings of twofold triple systems, Ars Math. Contemp., 8, 267-273, 2015 · Zbl 1325.05039 · doi:10.26493/1855-3974.415.ecd |
| [46] | Gévay, G., Resolvable configurations, Discret. Appl. Math., 266, 319-330, 2019 · Zbl 1464.51005 · doi:10.1016/j.dam.2019.02.019 |
| [47] | Graham, R.L.: On sums of integers taken from a fixed sequence. In: Proceedings, Washington State University Conference on Number Theory, pp. 22-40 (1971) · Zbl 0231.10034 |
| [48] | Grannell, MJ; Griggs, TS; Hilton, A.; Talbot, J., Designs and topology, Surveys in Combinatorics. London Mathematical Society Lecture Note Series, 121-174, 2007, Cambridge: Cambridge University Press, Cambridge · Zbl 1127.05013 |
| [49] | Grannell, MJ; Korzhik, VP, Orientable biembeddings of cyclic Steiner triple systems from current assignments on Möbius ladder graphs, Discret. Math., 309, 2847-2860, 2009 · Zbl 1190.05026 · doi:10.1016/j.disc.2008.07.016 |
| [50] | Gordon, B., Sequences in groups with distinct partial products, Pac. J. Math., 11, 1309-1313, 1961 · Zbl 0103.26202 · doi:10.2140/pjm.1961.11.1309 |
| [51] | Gross, JL; Tucker, TW, Topological Graph Theory, 1987, New York: Wiley, New York · Zbl 0621.05013 |
| [52] | Heffter, L., Über Nachbarconfigurationen, Triplesysteme und metacyklische Gruppen. Deutsche Mathem. Vereinig. Jahresber., 5, 67-69, 1896 |
| [53] | Hicks, J.; Ollis, MA; Schmitt, JR, Distinct partial sums in cyclic groups: polynomial method and constructive approaches, J. Comb. Des., 27, 369-385, 2019 · Zbl 1437.05238 · doi:10.1002/jcd.21652 |
| [54] | Jordon, H.; Morris, J., Cyclic Hamiltonian cycle systems of the complete graph minus a 1-factor, Discret. Math., 308, 2440-2449, 2008 · Zbl 1172.05332 · doi:10.1016/j.disc.2007.05.009 |
| [55] | Jordon, H.; Morris, J., Cyclic m-cycle systems of complete graphs minus a 1-factor, Australas. J. Comb., 67, 304-326, 2017 · Zbl 1375.05151 |
| [56] | Khodkar, A., Ellis, B.: Signed magic rectangles with two filled cells in each column, https://arxiv.org/abs/1901.05502 |
| [57] | Khodkar, A.; Leach, D., Magic rectangles with empty cells, Utilitas Math., 116, 45-56, 2020 · Zbl 1469.05025 |
| [58] | Khodkar, A.; Leach, D., Magic squares with empty cells, Ars Comb., 154, 45-52, 2021 · Zbl 1513.05051 |
| [59] | Khodkar, A.; Leach, D.; Ellis, B., Signed magic rectangles with three filled cells in each column, Bull. Inst. Comb. Appl., 90, 87-106, 2020 · Zbl 1461.05019 |
| [60] | Khodkar, A.; Schulz, C.; Wagner, H., Existence of some signed magic arrays, Discret. Math., 340, 906-926, 2017 · Zbl 1440.05050 · doi:10.1016/j.disc.2017.01.020 |
| [61] | Lucas, E.: Récréations Mathématiques, Tôme II. Albert Blanchard, Paris (1892) |
| [62] | Mella, L.; Pasotti, A., Tight globally simple non-zero sum Heffter arrays and biembeddings, J. Comb. Des., 31, 41-83, 2023 · Zbl 1529.05030 · doi:10.1002/jcd.21866 |
| [63] | Mella, L., Traetta, T.: Constructing generalized Heffter arrays via near alternating sign matrices, https://arxiv.org/abs/2306.09948 |
| [64] | Mendelsohn, E.; Rosa, A., Completing partial solutions to Heffter’s difference problem, Bull. Inst. Comb. Appl., 55, 73-79, 2009 · Zbl 1201.05013 |
| [65] | Mohar, B., Combinatorial local planarity and the width of graph embeddings, Can. J. Math., 44, 1272-1288, 1992 · Zbl 0777.05052 · doi:10.4153/CJM-1992-076-8 |
| [66] | Mohar, B.; Thomassen, C., Graphs on Surfaces, 2001, Baltimore: Johns Hopkins University Press, Baltimore · Zbl 0979.05002 · doi:10.56021/9780801866890 |
| [67] | Morini, F.; Pellegrini, MA, On the existence of integer relative Heffter arrays, Discret. Math., 343, 112088, 2020 · Zbl 1447.05045 · doi:10.1016/j.disc.2020.112088 |
| [68] | Morini, F., Pellegrini, M.A.: Magic rectangles, signed magic arrays and integer \(\lambda \)-fold relative Heffter arrays. Australas. J. Comb. 80, 249-280 (2021) · Zbl 1468.05021 |
| [69] | Morini, F.; Pellegrini, MA, Rectangular Heffter arrays: a reduction theorem, Discret. Math., 345, 113073, 2022 · Zbl 1497.05025 · doi:10.1016/j.disc.2022.113073 |
| [70] | Morini, F.; Pellegrini, MA, Magic partially filled arrays on abelian groups, J. Comb. Des., 31, 347-367, 2023 · Zbl 1526.05019 · doi:10.1002/jcd.21886 |
| [71] | Ollis, M.A.: Sequenceable groups and related topics. Electron. J. Comb. 20, #DS10v2 (2013) · Zbl 1081.20500 |
| [72] | Ollis, MA, Sequences in dihedral groups with distinct partial products, Australas. J. Comb., 78, 35-60, 2020 · Zbl 1530.20068 |
| [73] | Peltesohn, R., Eine Lösung der beiden Heffterschen Differenzenprobleme, Compositio Math., 6, 251-257, 1939 · Zbl 0020.04902 |
| [74] | Vietri, A.: Cyclic k-cycle systems of order \(2kn+k\): a solution of the last open cases. J. Comb. Des. 12, 299-301 (2004) · Zbl 1045.05025 |
| [75] | Wilson, RJ, Introduction to Graph Theory, 1979, Harlow, Essex: Longman, Harlow, Essex · Zbl 0458.05024 |
| [76] | Wu, S.L., Fu, H.L.: Cyclic m-cycle systems with \(m\leq 32\) or \(m=2q\) with q a prime power. J. Comb. Des. 14, 66-81 (2006) · Zbl 1085.05040 |
| [77] | Youngs, J.W.T.: The mystery of the Heawood conjecture. In: Graph Theory and Its Applications, pp. 17-50 Academic, New York (1970) · Zbl 0208.52303 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
