Hostname: page-component-74656f9884-6grmk Total loading time: 0 Render date: 2026-11-06T05:14:50.766Z Has data issue: false hasContentIssue false
  • English
  • Français

Counting Certain Pairings in Arbitrary Groups

Published online by Cambridge University Press:  11 October 2011

Y. O. HAMIDOUNE
Y. O. HAMIDOUNE*
Affiliation:
Université Pierre et Marie Curie (Paris 6), Institut de Mathématiques de Jussieu, Combinatoire et Optimisation, Case 189, 4 Place Jussieu, 75005 Paris, France
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper, we study certain pairings which are defined as follows: if A and B are finite subsets of an arbitrary group, a Wakeford–Fan–Losonczy pairing from B onto A is a bijection φ : B → A such that bφ(b) ∉ A, for every b ∈ B. The number of such pairings is denoted by μ(B, A).

We investigate the quantity μ(B, A) for A and B, two finite subsets of an arbitrary group satisfying 1 ∉ B, |A| = |B|, and the fact that the order of every element of B is ≥ |B| + 1. Extending earlier results, we show that in this case, μ(B, A) is never equal to 0. Furthermore we prove an explicit lower bound on μ(B, A) in terms of |B| and the cardinality of the group generated by B, which is valid unless A and B have a special form explicitly described. In the case A = B, our bound holds unless B is a translate of a progression.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 6 , November 2011 , pp. 855 - 865
Copyright
Copyright © Cambridge University Press 2011

References

[1]Chowla, S. (1935) A theorem on the addition of residue classes: Applications to the number Γ(k) in Waring's problem. Proc. Indian Acad. Sci. 2 242–243.CrossRefGoogle Scholar
[2]Eliahou, S. and Lecouvey, C. (2008) Matchings in arbitrary groups. Adv. Appl. Math. 40 219–224.CrossRefGoogle Scholar
[3]Erdős, P. and Heilbronn, H. (1964) On the addition of residue classes mod p. Acta Arith. 9 149–159.Google Scholar
[4]Fan, C. K. and Losonczy, J. (1996) Matchings and canonical forms in symmetric tensors. Adv. Math. 117 228–238.Google Scholar
[5]Fournier, J. C. (2003) Combinatorics of perfect matchings in plane bipartite graphs and application to tilings. Theoret. Comput. Sci. 303 333–351.Google Scholar
[6]Hall, P. (1935) On representatives of subsets. J. London Math. Soc. 10 26–30.Google Scholar
[7]Hamidoune, Y. O. (1984) On the connectivity of Cayley digraphs. Europ. J. Combin. 5 309–312.CrossRefGoogle Scholar
[8]Hamidoune, Y. O. (1996) An isoperimetric method in additive theory. J. Algebra 179 622–630.Google Scholar
[9]Hamidoune, Y. O. (1997) On subsets with a small sum in abelian groups I: The Vosper property. Europ. J. Combin. 18 541–556.CrossRefGoogle Scholar
[10]Hamidoune, Y. O. (1999) On small subset product in a group. In Structure Theory of Set-Addition, Vol. 258 of Astérisque, pp. 281–308.Google Scholar
[11]Hamidoune, Y. O. (2000) Some results in additive number theory I: The critical pair theory. Acta Arith. 96 97–119.Google Scholar
[12]Hamidoune, Y. O. (2008) On group bijections φ with φ(B) = A and ∀a ∈ B, aφ(a) ∉ A. arXiv:0812.2522.Google Scholar
[13]Hamidoune, Y. O. Hyper-atoms and the Kemperman's critical pair theory, arXiv.0708.3581.Google Scholar
[14]Hamidoune, Y. O. Hyper-atoms applied to the critical pair theory. Submitted. arXiv:1102.2099v1Google Scholar
[15]Kemperman, J. H. B. (1956) On complexes in a semigroup. Nederl. Akad. Wetensch. Proc. Ser. A 59 247–254.Google Scholar
[16]Kneser, M. (1953) Abschätzung der asymptotischen Dichte von Summenmengen. Math. Z. 58 459–484.CrossRefGoogle Scholar
[17]Losonczy, J. (1998) On matchings in groups. Adv. Appl. Math. 20 385–391.CrossRefGoogle Scholar
[18]Lovász, L. and Plummer, M. D. (1986) Matching theory. Ann. Discrete Math. 29.Google Scholar
[19]Olson, J. E. (1975/76) Sums of sets of group elements. Acta Arith. 28 147–156.Google Scholar
[20]Olson, J. E. (1984) On the sum of two sets in a group. J. Number Theory 18 110–120.Google Scholar
[21]Plagne, A. (2011) Yahya ould Hamidoune, grand Mauritanien, homme singulier, mathématicien d'exception. Gaz. Math. 129 123–129.Google Scholar
[22]Plagne, A. (2011) Yahya ould Hamidoune, the Mauritanian mathematician. Combin. Probab. Comput. 20 641–645.Google Scholar
[23]Scherk, P. and Moser, L. (1955) Advanced problems and solutions: Solutions, 4466. Amer. Math. Monthly 62 46–47.Google Scholar
[24]Wakeford, E. K. (1918/1919) On canonical forms. Proc. London Math. Soc. 18 403–410.Google Scholar