A random Hall-Paige conjecture
\(R\)-sequenceable groupcomplete mappinggroup absorberharmonious grouphypergraph matchingLatin squaresequenceable grouptransversalzero-sum subset
Orthogonal arrays, Latin squares, Room squares (05B15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Arithmetic and combinatorial problems involving abstract finite groups (20D60)
The classical conjecture by \textit{M. Hall} and \textit{L. Paige} [Pac. J. Math. 5, 541--549 (1955; Zbl 0066.27703)] states that a finite group \(G\) admits a complete mapping, i.e., a bijection \(\varphi \colon G \to G\) such that \(x \mapsto x\varphi(x)\) is also bijective, if and only if the product \(\prod_{x \in G} x\) is trivial in the abelianization \(G^{\mathrm{ab}}\). This conjecture was proved by \textit{S. Wilcox} [J. Algebra 321, No. 5, 1407--1428 (2009; Zbl 1172.20024)], \textit{A. B. Evans} [J. Algebra 321, No. 1, 105--116 (2009; Zbl 1166.20012)] and \textit{J. N. Bray} et al. [J. Algebra 545, 27--42 (2020; Zbl 1485.20002)] using the classification of finite simple groups.\N\NIn this paper, the authors establish a probabilistic generalization of the Hall-Paige conjecture. They prove that for any large finite group \(G\) and for most random-like equal-sized subsets \(A, B, C \subseteq G\), the Hall-Paige condition \(\prod A \cdot \prod B = \prod C\) in \(G^{\mathrm{ab}}\) is not only necessary but typically sufficient for the existence of a bijection \(\varphi \colon A \to B\) such that \(x \mapsto x\varphi(x)\) is a bijection from \(A\) to \(C\).\N\NTheir main result (Theorem 1.1) is formulated using random subsets and probabilistic bounds on the deviation of subset sums in the abelianization. As a consequence, the authors settle several longstanding open problems in the combinatorial theory of finite groups.\N\NFirst, they prove that all sufficiently large non-abelian finite groups are sequenceable, settling a problem by \textit{B. Gordon} [Pac. J. Math. 11, 1309--1313 (1961; Zbl 0103.26202)] and confirming a conjecture of \textit{A. D. Keedwell} [Discrete Math. 37, No. 2--3, 203--216 (1981; Zbl 1567.20069) ].\N\NSecond, they prove a strong asymptotic version of the challenging conjecture of \textit{H. S. Snevily} [Am. Math. Mon. 106, No. 6, 584--585 (1999; \url{doi:10.1080/00029890.1999.12005088})] concerning the existence of transversals in subsquares of multiplication tables of abelian groups, previously known only for groups of odd order by work by \textit{N. Alon} [Comb. Probab. Comput. 8, No. 1--2, 7--29 (1999; Zbl 0920.05026)], \textit{S. Dasgupta} et al. [Isr. J. Math. 126, 17--28 (2001; Zbl 1011.05014)] and \textit{I. Arsovski} [Isr. J. Math. 182, 505--508 (2011; Zbl 1241.20061)].\N\NThird, they solve a problem posed by \textit{P. Tannenbaum} [SIAM J. Algebraic Discrete Methods. 4, 22--29 (1983; Zbl 0521.20011)] concerning partitions of abelian groups into prescribed zero-sum subsets and confirm a conjecture of \textit{S.Cichacz} [Electron. J. Comb. 25, No. 1, Research Paper P1.20, 12 p. (2018; Zbl 1380.05099)].\N\NFourth, they characterize large finite groups admitting a harmonious ordering, solving a problem by \textit{A. B. Evans} [Quasigroups Relat. Syst. 23, No. 1, 5--30 (2015; Zbl 1328.05026)].\N\NThe proof strategy combines the absorption method, in the sense of \textit{V. Rödl} et al. [Combinatorica 28, No. 2, 229--260 (2008; Zbl 1164.05051)], with a detailed combinatorial construction of matchings in multiplication hypergraphs. The main innovation lies in adapting the absorption technique to the setting of group multiplication, treating both abelian and nonabelian cases via probabilistic and algebraic methods. A key ingredient is a representation-theoretic result bounding the commutator width logarithmically, used to handle cosets in the commutator subgroup.
- A Combinatorial Problem on Abelian Groups
- A lower bound for the n-queens problem
- A natural barrier in random greedy hypergraph matching
- A Note on Steiner Triple Systems.
- A proof of Ringel's conjecture
- A proof of Snevily's conjecture.
- A review of uniform cross-over designs
- Additive Latin transversals.
- All group‐based latin squares possess near transversals
- An approximate Dirac-type theorem for k-uniform hypergraphs
- An asymptotic for the Hall-Paige conjecture
- Applications of complete mappings and orthomorphisms of finite groups
- Binary labeling of graphs
- Combinatorial Nullstellensatz
- Complete mappings of finite groups
- Compositions and parities of complete mappings and of orthomorphisms
- Decompositions into spanning rainbow structures
- Dense expanders and pseudo-random bipartite graphs
- Differences of bijections
- Distinct Sums Modulo n and Tree Embeddings
- Graph labelings in elementary abelian 2-groups
- Group characters and commutators
- Harmonious groups
- scientific article; zbMATH DE number 3773888 (Why is no real title available?)
- Introduction to algorithms.
- Juggling mathematics and magic
- Near perfect coverings in graphs and hypergraphs
- Near-optimal list colorings
- New bounds for Ryser’s conjecture and related problems
- On Additive Bases and Harmonious Graphs
- On certain distributions of integers in pairs with given differences
- On the sequenceability of non-abelian groups of order pq
- On zero-sum partitions of abelian groups
- Orthogonal Latin squares based on groups
- Partitions of Z₂ⁿ
- Partitions of groups and complete mappings
- Probabilistic combinatorics and the recent work of Peter Keevash
- Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
- Reduction of the Hall-Paige conjecture to sporadic simple groups.
- Sequenceable groups and related topics.
- Sequences in groups with distinct partial products
- Sorting in \(c \log n\) parallel steps
- Spanning trees in random graphs
- The admissibility of sporadic simple groups.
- The existence of strong complete mappings of finite groups: a survey
- The Hall-Paige conjecture, and synchronization for affine and diagonal groups
- Transversals and multicolored matchings
- Transversals in Latin squares: a survey
- Transversals of additive Latin squares
- Vertex coverings by monochromatic cycles and trees
- Zero sum partition of abelian groups into sets of the same order and its applications
- Zero-sum partitions of Abelian groups of order 2ⁿ
- Complete mappings stabilizing a subgroup and their parities
- Nearly Hamilton cycles in sublinear expanders and applications
- Harmonious sequences in groups with a unique involution
- Spanning trees in pseudorandom graphs via sorting networks
- Irregular graph labelings in abelian groups
- Towards Graham's rearrangement conjecture via rainbow paths
- Symmetric harmoniousness of odd-order groups
This page was built for publication: A random Hall-Paige conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6985766)
