Séminaire Lotharingien de Combinatoire 91 (2025), Article B91b

THE WEAK ACYCLIC MATCHING PROPERTY IN ABELIAN GROUPS

MOHSEN ALIABADI^{1} AND PETER TAYLOR^{2}

Abstract. A matching from a finite subset A ⊂ ℤ^{n} to another subset B ⊂ ℤ^{n} is a bijection f : A → B with the property that a + f(a) never lies in A. A matching is called acyclic if it is uniquely determined by its multiplicity function. Alon et al. established the acyclic matching property for ℤ^{n}, which was later extended to all abelian torsion-free groups. In a prior work, the authors of this paper settled the acyclic matching property for all abelian groups. The objective of this note is to explore a related concept, known as the weak acyclic matching property, within the context of abelian groups.

1. Introduction

Let (G, +) denote an abelian group. Consider nonempty finite subsets A, B ⊆ G. A matching from A to B is defined as a bijection f : A → B satisfying the condition a + f(a) ∉ A for every a ∈ A. When such a matching exists from A to B, we say that A is matched to B. This concept, introduced by Fan and Losonczy in [8], serves as a tool in exploring Wakeford’s classical problem concerning canonical forms for symmetric tensors [14]. It is evident that the existence of a matching from A to B requires |A| = |B| and 0 ∉ B.

An abelian group G possesses the matching property if the aforementioned conditions on A and B suffice to ensure the existence of a matching from A to B. Losonczy addressed the question of which groups possess this property in [13], giving the following criterion.

Theorem 1.1. An abelian group G possesses the matching property if and only if G is torsion-free or cyclic of prime order.

For a matching f : A → B, the associated multiplicity function m_{f} : G → ℤ_{≥0} is defined as follows:

for all x ∈ G, m_{f}(x) = |{a ∈ A : a + f(a) = x}|.

A matching f : A → B is called acyclic if for any matching g : A → B, m_{f} = m_{g} implies f = g. If an acyclic matching from A to B exists, we say that A is acyclically matched to B. A group G exhibits the acyclic matching property if for any pair of subsets A and B in G with |A| = |B| and 0 ∉ B, there is at least one acyclic matching from A to B. Alon et al. proved in [6] that the additive group ℤ^{n} possesses the acyclic matching property. Losonczy [13] extended this result to all abelian torsionfree groups by exploiting a total ordering compatible with the structure of abelian torsion-free groups, established by Levi [12].

2020 Mathematics Subject Classification. Primary: 05E16; Secondary: 20N02.

Key words and phrases. abelian groups, acyclic matching property, weak acyclic matching property.

1Department of Mathematics, Clayton State University, 2000 Clayton State Boulevard, Morrow, GA 30260, USA. maliabadisr@clayton.edu, ORCID: 0000-0001-5331-2540 2Independent researcher, Valencia, Spain. pjt33@cantab.net, ORCID: 0000-0002-0556-5524 .

In [1], it was noted that primes p for which ℤ/pℤ lacks the acyclic matching property have a density of at least \frac{7}{24}. Moreover, building upon the rectification principle introduced by [11], which suggests that a sufficiently small subset of ℤ/pℤ can be embedded in the integers while preserving certain additive properties, it was demonstrated in [1] that for sets A, B ⊂ ℤ/pℤ, A is acyclically matched to B provided that 0 is not an element of B and |A| = |B| ≤ \sqrt{log_{2} p} − 1.

The present authors [4] provided a necessary and sufficient condition for abelian groups to possess the acyclic matching property: Theorem 1.2. An abelian group G possesses the acyclic matching property if and only if either G is torsion-free or G = ℤ/pℤ, where p ∈ {2, 3, 5}.

See [9] for insights into the enumeration aspects of matchings. Linear analogues of matching theory are developed in [7], while a matroidal version is presented in [5]. In particular, the linear version of acyclic matchings is studied in [1]. From the viewpoint of additive number theory, connections to matching theory can also be found in [10].

Acyclic matchings for specific sets: When discussing matchings between two sets A and B within G, two scenarios represent the extremes of the spectrum in terms of the number of matchings:

(1) A + B = A: In this case A is not matched to B. This case is treated in [3, Lemma 2.3] where it is proved that in this situation B must be a subgroup of G, and A is a coset of B.

(2) A∩(A+B) = ∅: In this case, not only is A matched to B but every bijection from A to B constitutes a matching, resulting in the maximum number of matchings.

Motivated by the preceding discussion, the acyclic matching problem arises for sets A and B where A ∩ (A + B) = ∅. Intuitively, the situation might be complex when A ∩ (A + B) = ∅ because there could be as many as |A|! matchings, increasing the probability of at least one acyclic matching existing. On the other hand, the number of matchings may grow faster than the number of multiplicity functions, so the average number of matchings per multiplicity function may be large reducing the probability of at least one acyclic matching existing. The following special cases of acyclic matching were proved in [1]: Theorem 1.3. Let A be a subset of the cyclic group ℤ/pℤ where p is a prime number. Suppose A satisfies A ∩ 2A = ∅ where 2A = {2a | a ∈ A}and A is of size k with k · 2^{k−1} < p. Then A is acyclically matched to itself via the identity map. Theorem 1.4. Let A and B be subsets of an abelian group G. Suppose A and B are of the same size satisfying A ∩ (A + B) = ∅. Then there exists an acyclic matching f : A → B if B is a Sidon set. (That is, the equation x + y = z + w has no solution in B with {x, y} ∩ {z, w} = ∅.)

Following [2], we define an abelian group G to possess the weak acyclic matching property if, for every finite nonempty subsets A and B of G with |A| = |B| and A ∩ (A + B) = ∅, A is acyclically matched to B. In [2], the following conjecture concerning the weak acyclic matching property was proposed.

Conjecture 1.5. There are infinitely many n for which ℤ/nℤ has the weak acyclic matching property.

The following question was also raised in [1].

Question 1.6. Does ℤ/pℤ possess the weak acyclic matching property for every prime p?

In this note, our main result, stated as Theorem 2.3, provides an affirmative answer to Conjecture 1.5 and thoroughly addresses Question 1.6. Furthermore, Theorem 2.3 classifies all abelian groups with respect to their adherence to the weak acyclic matching property.

Remark 1.7. It is worth noting that while the matching theory developed in this paper is related to the classical theory introduced by Philip Hall in 1935, the two are conceptually distinct. In particular, to address a linear algebra problem posed by Wakeford [14], Fan [8] constructed a bipartite graph G = (V (G), E(G)) based on two sets A, B ⊂ ℤ^{n}, which may overlap. Each element a ∈ A is assigned a symbol x_{a}, and each b ∈ B a symbol y_{b}, forming vertex sets

X = {x_{a} : a ∈ A} and Y = {y_{b} : b ∈ B}.

The graph has vertex set V (G) = X ∪ Y, with an edge between x_{a} ∈ X and y_{b} ∈ Y if and only if a + b ∉ A.

In graph-theoretic terms, a matching is a set of edges with no shared endpoints, and a perfect matching is one that covers all vertices. In the bipartite graph associated with A and B, perfect matchings correspond to bijections f : A → B such that a + f(a) ∉ A for all a ∈ A. Wakeford’s question thus reduces to determining the existence of such perfect matchings, known as acyclic matchings from A to B, discussed earlier.

2. Main results

Multiplicity functions in a more general setting: We begin with a few definitions. Let A, B and C be three nonempty sets. An operator ⊕ : A × B → C is said to possess the left cancellation property provided:

a ⊕ b_{1} = a ⊕ b_{2} ⟺ b_{1} = b_{2},

for every a ∈ A and b_{1}, b_{2} ∈ B. It will be convenient to define also the operator ⊖ : C × A → B as an inverse operation:

c ⊖ a = b ⟺ a ⊕ b = c,

where a ∈ A, b ∈ B and c ∈ C. Previously, we introduced a multiplicity function associated with a matching. We may consider a similar definition of a multiplicity function associated with a bijection. Let A, B and C be three nonempty sets. Let ⊕ : A × B → C be an operator. Given a bijection f : A → B, the associated multiplicity function m_{f} : C → ℤ_{≥0} is defined as

for all x ∈ C, m_{f}(x) = |{a ∈ A : a ⊕ f(a) = x}|.

In the following lemma, we obtain a bijection with a unique multiplicity function.

Lemma 2.1. Let A, B be finite sets of the same cardinality. Let C be a set. Let ⊕ : A × B → C be an operator with the left cancellation property and also the operator ⊖ as an inverse operation. Consider the set F of bijections f : A → B with corresponding multiplicity functions m_{f}(c) = |{a ∈ A : a ⊕ f(a) = c}|. Then there exists an element f_{0} ∈ F which has a unique m_{f_{0}}. That is, if g ∈ F and m_{g} = m_{f_{0}} then g = f_{0}.

Proof. The proof begins by constructing such an f_{0}. Let C′ = {a⊕b : (a, b) ∈ A×B} be the image of ⊕. Since A and B are finite, C′ is also finite and we can label its elements c_{1}, …, c_{k} where k = |C′|.

Let A_{1} = A, B_{1} = B. For each 1 ≤ j ≤ k, let

A′_{j} = {a ∈ A_{j} : there exists b ∈ B_{j} with a ⊕ b = c_{j}}.

For each a ∈ A′_{j} we assign f_{0}(a) = c_{j} ⊖ a. For the next iteration we define A_{j+1} = A_{j} \ A′_{j} and B_{j+1} = B_{j} \ {c_{j} ⊖ a : a ∈ A′_{j}}.

Since the paired elements of A and B are removed from the active subsets A_{j+1}, B_{j+1} it is evident that no element is paired twice. Since |A| = |B| and |A′_{j}| = |B′_{j}|, by induction we always have |A_{j}| = |B_{j}|. We claim that |A_{k+1}| = 0. Suppose for contradiction that |A_{k+1}| > 0. Then, we can arbitrarily choose a′ ∈ A_{k+1} and b′ ∈ B_{k+1}. Since there exists j ≤ k for which a′ ⊕b′ = c_{j}, at least one of them should have been removed no later than at step j, which leads to a contradiction. Hence |A_{k+1}| = 0. Therefore f_{0} is a bijection A → B, as claimed.

We show the uniqueness of m_{f_{0}} by assuming that g : A → B is a bijection and proving the property

(m_{g}(c_{i}) = m_{f_{0}}(c_{i}), for all i and j with 1 ≤ i < j)

implies (g(a) = f_{0}(a), for all a ∈ A′_{i}, and for all i and j with 1 ≤ i < j)

by induction on j.

When j = 1 the right-hand side of the implication is trivially true, giving the base case.

For the inductive step we note that, by construction, f_{0} maximizes m_{f_{0}}(j) subject to the assignments made in steps 1 to j − 1. Therefore if g agrees with f_{0} on all the assignments made in those steps and m_{g}(c_{j}) = m_{f_{0}}(c_{j}), g must make the same assignments as those made for f_{0} in step j. It cannot assign an a which is not in A_{j} because it is already assigned; the values in A_{j} that can potentially be assigned to yield c_{j} are precisely those in A′_{j}; and each has a unique b ∈ B_{j} (and, indeed, b ∈ B) to which it can be assigned in order to yield c_{j}, because of the left cancellation property. Therefore, this property holds for all j, and we observe that when specialized to j = k + 1, it implies that if m_{g} = m_{f_{0}}, then g = f_{0}.

□

Example 2.2. We implement the construction described in Lemma 2.1 to find the acyclic matching f_{0} : A → B, where A = {0, 1, 2, 7} and B = {3, 4, 9, 10} are considered as subsets of ℤ/13ℤ with ⊕ as the usual group operation. Then C′ = {3, 4, 5, 6, 9, 10, 11, 12} and we can take the natural ordering.

A_{1} = {0, 1, 2, 7}, B_{1} = {3, 4, 9, 10}, c_{1} = 3. We obtain A′_{1} = {0, 7} and assign f_{0}(0) = 3 and f_{0}(7) = 9.

A_{2} = {1, 2}, B_{2} = {4, 10}, c_{2} = 4. We obtain A′_{2} = ∅ and make no assignments. A_{3} = {1, 2}, B_{3} = {4, 10}, c_{3} = 5. We obtain A′_{3} = {1} and assign f_{0}(1) = 4. For 4 ≤ j ≤ 8 we have A_{j} = {2}, B_{j} = {10}. Finally, with c_{8} = 12 we obtain

A′_{7} = {2} and assign f_{0}(2) = 10.

In the following theorem, we will establish that all abelian groups possess the weak acyclic matching property.

Theorem 2.3. Every abelian group possesses the weak acyclic matching property.

Proof. Let G be an abelian group. Let A and B be nonempty finite subsets of G with |A| = |B| and A ∩ (A + B) = ∅. Since the bijections A → B are precisely the matchings and the group operation is cancellative, we can apply Lemma 2.1 to obtain an acyclic matching from A to B, completing the proof. □

Remark 2.4. In the case that A ⊆ C and B ⊆ C, any operation ⊕ : A × B → C for which (C, ⊕) is a quasigroup has the left cancellation property. The definition of matching generalizes straightforwardly to quasigroups, and so does the proof of Theorem 2.3. With that in mind, one might explore the properties of matchings in broader contexts beyond abelian groups, such as quasigroups. Delving further into this line of research could prove to be worthwhile.

References

[1] M. Aliabadi, K. Filom. Results and questions on matchings in abelian groups and vector subspaces of fields. Journal of Algebra 598 (2022), 85–104.

[2] M. Aliabadi, M. Janardhanan. On matchable subsets in abelian groups and their linear analogues. Linear Algebra and Its Applications 582 (2019), 138–155.

[3] M. Aliabadi, J. Kinseth, C. Kunz, H. Serdarevic, C. Willis. Conditions for matchability in groups and field extensions. Linear and Multilinear Algebra 71(7) (2023), 1182–1197.

[4] M. Aliabadi, P. Taylor. Classifying abelian groups through acyclic matchings. To appear in Annals of Combinatorics.

[5] M. Aliabadi, S. Zerbib. Matching matroids over abelian groups. Journal of Algebraic Combinatorics 59 (2024), 761–785.

[6] N. Alon, C. K. Fan, D. Kleitman, J. Losonczy. Acyclic matchings. Advances in Mathematics 122(2) (1996), 234–236.

[7] S. Eliahou, C. Lecouvey. Matching subspaces in a field extension. Journal of Algebra 324(12) (2010), 3420–3430.

[8] C. K. Fan, J. Losonczy. Matchings and canonical forms for symmetric tensors. Advances in Mathematics 117(2) (1996), 228–238.

[9] Y. O. Hamidoune. Counting certain pairings in arbitrary groups. Combinatorics, Probability and Computing 20(6) (2011), 855–865.

[10] V. F. Lev. Small doubling in groups with moderate torsion. SIAM J. Discrete Mathematics 36(1) (2022) 315–335.

[11] V. F. Lev. The rectifiability threshold in abelian groups. Combinatorica 28(4) (2008), 491–497.

[12] F. W. Levi. Ordered groups. Proceedings of the Indian Academy of Sciences 16 (1942), 256– 263.

[13] J. Losonczy. On matchings in groups. Advances in Applied Mathematics 20(3) (1998), 385– 391.

[14] E. K. Wakeford. On canonical forms. Proceedings of the London Mathematical Society (2) 18 (1920), 403–410.