Pith. sign in

REVIEW 4 minor 14 references

The number of stable matchings in a group-built preference template equals n exactly when every adjacent quotient generates the group.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-14 12:44 UTC pith:ZZNLATN6

load-bearing objection Clean group-theoretic characterization of a natural family of Latin SMP instances, with an exact generator criterion, its converse, and a sharp coset-index lower bound that recovers f(4)=10.

arxiv 2607.10306 v1 pith:ZZNLATN6 submitted 2026-07-11 math.CO

Regular anti-phase templates in the stable marriage problem: a generator criterion, its converse, and a counting bound

Yoshiteru Ishida This is my paper
classification math.CO MSC 05A0505E1891B6806D05
keywords stable marriage problemLatin preference profileanti-phase templateregular group actiongenerator criterionsex-equal matchingrotation poset
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper builds highly symmetric stable-marriage instances from any finite group of order n together with an ordering of its elements. The resulting regular anti-phase templates always possess n canonical stable matchings; the paper proves that these are the only stable matchings if and only if each successive “adjacent quotient” of the ordering generates the whole group. When some quotient generates only a proper subgroup, the paper constructs extra stable matchings by taking unions of left cosets, and thereby obtains a concrete lower bound on the size of the stable set. The bound is sharp for every group of order at most five and for both groups of order four; in particular it recovers the classical maximum of ten stable matchings for size-four instances via the Klein four-group. The same analysis shows that chain lattices appear for every ordering precisely when the group order is prime, not merely when the group is cyclic. The anti-phase construction itself is shown to be the unique choice, among all automorphism-maximal profiles, that forces every man–woman pair to have constant rank sum n+1.

Core claim

For every finite group G of order n and every ordering A of its elements, the regular anti-phase template P(G,A) has exactly n stable matchings if and only if every adjacent quotient qb generates G. When some qb fails to generate, an explicit family of non-canonical stable matchings can be built from the proper unions of left cosets of ⟨qb⟩, yielding the sharp lower bound |Stab|≥n+∑ b(2[G:⟨qb⟩]-2).

What carries the argument

The coset lemma: for any stable matching the top level set of its index function is a union of left cosets of the cyclic subgroup generated by the adjacent quotient at the maximal index. This single rigidity statement supplies both the sufficiency and the necessity of the generator criterion and the counting bound.

Load-bearing premise

Every stable matching’s highest-rank set of men must be a union of left cosets of the subgroup generated by the corresponding adjacent quotient; if a counter-example matching existed, both the converse and the lower bound would fail.

What would settle it

Exhibit any finite group G, any ordering A, and any stable matching of P(G,A) whose highest index level set is not a union of left cosets of ⟨qb⟩; or find a group of order ≤5 for which the counting lower bound is not attained.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies highly symmetric stable-marriage instances obtained from regular actions of a finite group G of order n together with an ordering A of its elements. It defines the regular anti-phase template P(G,A), shows that the anti-phase choice of women’s lists is the unique one among automorphism-maximal profiles that yields the constant rank-sum identity r_M + r_W = n+1, and proves that the n canonical matchings exhaust the stable set if and only if every adjacent quotient q_b generates G. The necessity direction is obtained by an explicit two-level construction of non-canonical stable matchings indexed by proper nonempty unions of left cosets of ⟨q_b⟩. A counting lower bound |Stab| ≥ n + ∑_b (2[G:⟨q_b⟩]-2) follows at once; the bound is sharp for all groups of order ≤5 and both groups of order 4, recovering the classical maximum f(4)=10 for the Klein four-group. The paper also corrects an earlier impression that cyclicity alone forces a chain lattice: the phenomenon is governed by primality of |G| (or, for composite order, by the particular ordering A). All computational claims are verified by an accompanying pure-Python script.

Significance. The work supplies a clean group-theoretic characterization of a natural family of Latin, automorphism-maximal profiles and gives the first exact criterion (and its converse) for when such a profile has exactly n stable matchings. The coset lemma and the explicit two-level construction are elementary yet non-obvious; together they convert a previously ad-hoc generator criterion into a sharp if-and-only-if statement that holds for arbitrary finite groups. The counting bound is sharp in all small cases and furnishes a structural explanation of f(4)=10. The accompanying machine-checkable script and the careful correction of the cyclicity-versus-primality picture further strengthen the contribution. The results sit at a useful intersection of combinatorial matching theory, Latin squares, and finite-group actions, and they open several concrete open problems on exact counts and lattice structure.

minor comments (4)
  1. In the statement of Theorem 4.7 the re-indexing that converts b_s = a^{-1}_{n-1-s} into the displayed form is correct but slightly terse; a one-line intermediate equation would help a reader who is not already fluent with the normal form.
  2. Example 5.12 and Observation 7.2 both list concrete orderings of Z_4; it would be convenient to have a single table that also records the resulting rotation posets (or at least their heights) so that the dependence of lattice shape on A is visible at a glance.
  3. The product construction of Section 6 is standard and correctly stated, yet it is never used later; either a brief forward reference to a decomposition question or a one-sentence remark that it is recorded only for completeness would avoid the impression of an orphaned section.
  4. A few typographical inconsistencies remain (e.g., “anti-phase” versus “antiphase”, occasional missing spaces around mathematical operators). They do not affect readability but should be cleaned in the final version.

Circularity Check

0 steps flagged

No significant circularity: generator criterion, converse, and counting bound are derived from the blocking-pair definition and explicit constructions, not from fitted parameters or load-bearing self-citations.

full rationale

The paper defines regular anti-phase templates P(G,A) via group actions and orderings, then derives the coset lemma (Lemma 5.5) directly from the stability condition in coordinates (Lemma 5.3): for maximal index b the top level set Db is closed under right multiplication by qb, hence a union of left cosets of ⟨qb⟩. The sharpened generator criterion (Theorem 5.6) follows immediately. The converse (Theorem 5.7) constructs, for every proper nonempty union K of left cosets, an explicit two-level index function d(b,K) and verifies it yields a matching that is stable by the same blocking criterion; the families for distinct b are disjoint by their distinct value sets {b-1,b}. The counting lower bound (Theorem 5.8) simply enumerates these constructed matchings plus the n canonical ones. The anti-phase characterization (Theorem 4.7) is an if-and-only-if computation inside the regular normal form. All steps are self-contained elementary group-and-matching arguments; the only self-references are to earlier versions of the same manuscript whose open problems are now settled by the new proofs. Computational claims are independently verified by an accompanying pure-Python script. No fitted input is renamed a prediction, no uniqueness is imported from prior author work, and no known empirical pattern is merely renamed. Score 0 is therefore the correct finding.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 2 invented entities

The paper works entirely inside the classical Gale–Shapley model of strict complete preferences and the standard theory of finite groups acting regularly. No free parameters are fitted; the only background axioms are the definition of stability, the lattice structure of stable matchings, and elementary facts about left cosets and generation. The regular anti-phase templates themselves are defined constructs, not postulated physical entities.

axioms (3)
  • domain assumption A matching is stable precisely when no blocking pair exists (Gale–Shapley definition).
    Used throughout Sections 2–5 as the sole criterion for membership in Stab(S).
  • standard math The set of stable matchings under men-dominance forms a finite distributive lattice isomorphic to the ideal lattice of the rotation poset.
    Invoked for lattice-type statements (Corollaries 3.4–3.5, Observation 5.13); classical result of Gusfield–Irving.
  • standard math Left multiplication by a fixed group element is a bijection; the left cosets of any subgroup partition the group.
    Used in the proof that the two-level index functions define matchings and that top level sets are unions of cosets (Lemma 5.5, Theorem 5.7).
invented entities (2)
  • regular anti-phase template P(G,A) no independent evidence
    purpose: Canonical family of automorphism-maximal, constant-rank-sum preference profiles built from a finite group and an ordering of its elements.
    Defined in Definition 5.1; characterised among all regular normal forms by the constant rank-sum identity (Theorem 4.7). Purely combinatorial construct with no independent physical existence claimed.
  • adjacent quotients q_b = a_{b-1} a_b^{-1} no independent evidence
    purpose: Group elements whose generated subgroups control the size of the stable set.
    Introduced in Definition 5.1; the generator criterion and counting bound are expressed solely in terms of these elements.

pith-pipeline@v1.1.0-grok45 · 18257 in / 2726 out tokens · 22237 ms · 2026-07-14T12:44:40.616669+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Regular anti-phase templates in the stable marriage problem: a generator criterion, its converse, and a counting bound." pith.science (2026). https://pith.science/paper/ZZNLATN6

@misc{pith2026260710306,
  author       = {Pith},
  title        = {Pith review of: Regular anti-phase templates in the stable marriage problem: a generator criterion, its converse, and a counting bound},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZZNLATN6}},
  note         = {Machine review of arXiv:2607.10306}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We study a family of highly symmetric instances of the stable marriage problem built from regular actions of finite groups. Given a finite group G of order n and an ordering A of its elements, we define the regular anti-phase template P(G,A). These templates have n canonical stable matchings. We show that the anti-phase condition is canonical: among automorphism-maximal profiles, the anti-phase templates are exactly those satisfying a constant rank-sum identity. This gives a structural characterization rather than an ad hoc definition. We prove a generator criterion and its exact converse: the stable set has size n if and only if each adjacent quotient generates the group. This result holds for all finite groups and does not require commutativity. We further establish a counting lower bound for the number of stable matchings in terms of subgroup indices. The bound is sharp for groups of order at most 5 and for all groups of order 4; in particular, it yields at least 10 stable matchings for the Klein group, with equality confirmed by enumeration. Finally, we show that cyclic profiles do not always produce chains; the structure depends on the ordering. All computational claims are verified by an accompanying script.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 1 linked inside Pith

  1. [1]

    A. T. Benjamin, C. Converse, and H. A. Krieger,How do I marry thee? Let me count the ways, Discrete Appl. Math.59(1995), 285–292

    1995

  2. [2]

    Birkhoff,Lattice Theory, 3rd ed., Amer

    G. Birkhoff,Lattice Theory, 3rd ed., Amer. Math. Soc. Colloq. Publ.25, AMS, 1967

    1967

  3. [3]

    Borodin, E

    M. Borodin, E. Chen, A. Duncan, T. Khovanova, B. Litchev, J. Liu, V. Moroz, M. Qian, R. Raghavan, G. Rastogi, and M. Voigt,Sequences of the stable matching problem, J. Integer Seq.27(2024); also arXiv:2201.00645

    Pith/arXiv arXiv 2024

  4. [4]

    Bubboloni, M

    D. Bubboloni, M. Gori, and C. Meo,Resolute and symmetric mechanisms for two-sided matching problems, J. Math. Econom.118(2025), 103130

    2025

  5. [5]

    D´ enes and A

    J. D´ enes and A. D. Keedwell,Latin Squares and Their Applications, Academic Press, 1974

    1974

  6. [6]

    Faenza and X

    Y. Faenza and X. Zhang,Legal assignments and fast EADAM with consent via classical theory of stable matchings, preprint, 2018

    2018

  7. [7]

    Gale and L

    D. Gale and L. S. Shapley,College admissions and the stability of marriage, Amer. Math. Monthly69 (1962), 9–15

    1962

  8. [8]

    Gusfield and R

    D. Gusfield and R. W. Irving,The Stable Marriage Problem: Structure and Algorithms, MIT Press, 1989

    1989

  9. [9]

    R. W. Irving, P. Leather, and D. Gusfield,An efficient algorithm for the optimal stable marriage, J. ACM 34(1987), 532–543

    1987

  10. [10]

    A. R. Karlin, S. Oveis Gharan, and R. Weber,A simply exponential upper bound on the maximum number of stable matchings, in: Proc. 50th ACM STOC, 2018, pp. 920–925

    2018

  11. [11]

    Kato,Complexity of the sex-equal stable marriage problem, Japan J

    A. Kato,Complexity of the sex-equal stable marriage problem, Japan J. Indust. Appl. Math.10(1993), 1–19

    1993

  12. [12]

    D. E. Knuth,Mariages stables, Les Presses de l’Universit´ e de Montr´ eal, 1976

    1976

  13. [13]

    D. F. Manlove,Algorithmics of Matching Under Preferences, World Scientific, 2013

    2013

  14. [14]

    McDermid and R

    E. McDermid and R. W. Irving,Sex-equal stable matchings: complexity and exact algorithms, Algorithmica 68(2014), 545–570

    2014