The paper [Costa et al., Discrete Math. 345 (2022), 112952] introduced, for cyclic groups, the class of partially filled arrays of the non-zero sum Heffter array that are, as the Heffter arrays, related to difference families, graph decompositions, and biembeddings. Here we generalize this definition to any finite group. Given a subgroup J of order t of a finite group (G, +), a λ-fold non-zero sum Heffter array over G relative to J,λNHG,J (m, n; h, k), is an m×n partially filled array with entries in G such that: each row contains h filled cells and each column contains k filled cells; for every x ∈ G \ J, the sum of the occurrences of x and −x is λ; the sum of the elements in every row and column is, following the natural orderings from left to right for the rows and from top to bottom for the columns, different from 0. The 2022 paper by Costa et al. also presented a complete, probabilistic solution for the existence problem in case λ = 1 and G = Zv which is the starting point of this investigation. In this paper we will consider the existence problem for a generic value of λ and a generic finite group G, and we present an almost complete solution to this problem. In particular, we will prove, through local considerations (inspired by the Lovász Local Lemma), that there exists a λ-fold non-zero sum Heffter array over G relative to J whenever the trivial necessary conditions are satisfied and |G| ≥ 41. This value can be reduced to 29 in case the array does not contain empty cells. Finally, we will show that these arrays give rise to biembeddings of multigraphs into orientable surfaces and we provide new infinite families of such embeddings.

Existence of λ-fold non-zero sum Heffter arrays through local considerations

Della Fiore Stefano
2023-01-01

Abstract

The paper [Costa et al., Discrete Math. 345 (2022), 112952] introduced, for cyclic groups, the class of partially filled arrays of the non-zero sum Heffter array that are, as the Heffter arrays, related to difference families, graph decompositions, and biembeddings. Here we generalize this definition to any finite group. Given a subgroup J of order t of a finite group (G, +), a λ-fold non-zero sum Heffter array over G relative to J,λNHG,J (m, n; h, k), is an m×n partially filled array with entries in G such that: each row contains h filled cells and each column contains k filled cells; for every x ∈ G \ J, the sum of the occurrences of x and −x is λ; the sum of the elements in every row and column is, following the natural orderings from left to right for the rows and from top to bottom for the columns, different from 0. The 2022 paper by Costa et al. also presented a complete, probabilistic solution for the existence problem in case λ = 1 and G = Zv which is the starting point of this investigation. In this paper we will consider the existence problem for a generic value of λ and a generic finite group G, and we present an almost complete solution to this problem. In particular, we will prove, through local considerations (inspired by the Lovász Local Lemma), that there exists a λ-fold non-zero sum Heffter array over G relative to J whenever the trivial necessary conditions are satisfied and |G| ≥ 41. This value can be reduced to 29 in case the array does not contain empty cells. Finally, we will show that these arrays give rise to biembeddings of multigraphs into orientable surfaces and we provide new infinite families of such embeddings.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4853675
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact