Pith. sign in

REVIEW 2 major objections 6 minor 30 references

High predictability does not guarantee that a tournament is the majority of three or five voters.

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-30 23:52 UTC pith:TEF3AUXF

load-bearing objection Clean structural theorem plus three real conjecture refutations, capped by an explicit Paley(43) non-5-inducibility proof whose only soft spot is a large but carefully cross-checked enumeration. the 2 major comments →

arxiv 2607.26690 v1 pith:TEF3AUXF submitted 2026-07-29 cs.DM

Tournaments determined by three and five voters

Leonid Chindelevitch , Ararat Harutyunyan This is my paper
classification cs.DM MSC 05C2091B1268Q17
keywords tournamentsKemeny medianfeedback arc setMcGarvey numberpredictabilitymajority dimensionPaley tournamentinducibility
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.

The paper studies when a tournament (a complete set of pairwise rankings) can arise as the majority outcome of a few voters. A natural numerical condition, predictability, says every arc is supported by a large enough supermajority in some weighted population of rankings. The authors show this condition is not enough. For three voters it fails exactly on the boundary value 2/3, with more than a thousand ten-vertex counterexamples and a unique regular eleven-vertex witness. For five voters it fails strictly: the Paley tournament on 43 vertices has predictability above the 3/5 threshold yet is not inducible by any five linear orders. Along the way they strengthen a structural fact about feedback arc sets and refute two earlier conjectures that linked minimum reversals only to 3-cycles. The results give the first explicit tournament of modest size that five voters cannot realize, tightening the known bounds on the smallest order where five-voter inducibility fails.

Core claim

Predictability at or above the natural majority threshold does not imply m-inducibility for m=3 or m=5. For three voters the implication fails exactly when predictability equals 2/3; for five voters the Paley tournament of order 43 supplies an explicit counterexample whose predictability 181/301 exceeds 3/5. In addition, every minimum feedback arc set of any tournament is already a minimal 3-cycle hitting set, yet the equality of their sizes fails for some 3-inducible tournaments at order 11, and the locality conjecture that medians reverse only 3-cycle arcs fails for every odd number of voters at least 5.

What carries the argument

The co-backing lemma plus a thin-slack shell argument: in any five-voter profile the double-back sets of cyclic triangles must be pairwise disjoint, while the predictability excess of Paley(43) forces at least two voters into the level-≤1 shell of near-maximum acyclic orders; an exhaustive automorphism-reduced screen shows no such pair is double-back-disjoint.

Load-bearing premise

The claim that Paley(43) is not five-inducible rests on a large computer enumeration that no two near-maximum orders have disjoint double-back sets, together with a dynamic-programming computation of its maximum acyclic subgraph size.

What would settle it

Exhibit either a five-voter profile whose majority tournament is Paley(43), or a pair of level-≤1 linear orders on 43 vertices whose sets of double-backed cyclic triangles are disjoint.

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

If this is right

  • The threshold conjecture A(m) is false for m=3 (on the boundary) and for m=5 (strictly).
  • N(5), the smallest order of a non-5-inducible tournament, satisfies 12≤N(5)≤38 non-constructively and N(5)≤43 with an explicit witness.
  • FAS=HS3 holds for every tournament on at most 10 vertices but already fails for some 3-inducible tournaments on 11 vertices.
  • Medians of five or more odd numbers of voters can reverse arcs that lie in no directed 3-cycle.
  • The margin hierarchy I_{m,t} is already strict at m=3; the paper conjectures it remains strict for every odd m.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Because five-inducibility is upward-closed, any future refutation of the threshold at seven or more voters must begin among non-5-inducible tournaments; Paley(43) is currently the only explicit specimen of reasonable size.
  • The same thin-slack-plus-co-backing template may decide the still-open status of the smaller Paley tournaments of orders 23, 27 and 31.
  • Closing the gap 12≤N(5)≤38 would settle whether the counting bound or the explicit Paley witness is closer to the true threshold.

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

2 major / 6 minor

Summary. The paper studies majority tournaments induced by few voters and the reduction of the Kemeny median problem to weighted feedback arc set. It strengthens Milosz–Hamel–Pierrot by proving that in every tournament a minimum FAS is a minimal 3-cycle hitting set (Theorem 2.1), then recovers their 3-voter weighted statement. It refutes both of their conjectures: the “only 3-cycle arcs reverse” property fails for every odd m≥5 (minimal counterexamples at (7,4), (9,4), (5,6)), and FAS=HS3 fails for a unique 3-inducible regular 11-vertex tournament T* (and six self-converse ones). It refutes the Shepardson–Tovey threshold conjecture A(m): for m=3 exactly on the boundary α*=2/3 (1,013 ten-vertex examples; unique regular cA3 on 11 vertices), and for m=5 strictly via Paley(43), which has α*=181/301>3/5 yet is not 5-inducible (Theorem 7.1). Counting via completion uniqueness improves N(5)≤38 non-constructively and sharpens Bachmeier et al.’s bounds for all odd m≤21; Paley(43) gives the first explicit modest-size witness N(5)≤43. Extensive ILP/LP censuses, obstacle catalogues at n=9, and a reproducibility package support the computational claims.

Significance. If correct, the work cleanly settles three open conjectures in tournament inducibility and Kemeny structure, supplies the first explicit non-5-inducible tournament near the counting scale (43 vs prior ~6×10^8), and improves all ten majoritarian-expressiveness bounds of Bachmeier et al. The analytic pillars—Theorem 2.1, co-backing (Lemma 7.2), slack forcing, completion uniqueness (Proposition 6.1)—are written proofs. Computational claims are backed by dual ILP encodings (CPLEX + CP-SAT), exact rational arithmetic, Aut-reduced orbit DP for MAS, a public GitHub verifier, and multiple sanity checks (MAS gauntlet, positive-detection count match, Aut-equivariance). That combination of refutation-by-counterexample, hereditary censuses, and reproducible large-scale search is a genuine advance for cs.DM / social-choice combinatorics.

major comments (2)
  1. [§7.3, Appendix E–F, Theorem 7.1] Theorem 7.1’s non-inducibility half is analytic once MAS(P)=543 and Lemma 7.2 are granted, but the decisive step is the negative exhaustive screen (§7.3, Appendix F): ~1.66×10^9 level-≤1 orders, razor to 538 triangles in W=[23], one-sided Aut reduction, ~4.38×10^9 candidate pairs, reported minimum DB-overlap 68. Completeness is certified only by the authors’ pipeline plus sanity checks (positive-detection equality, level-0 exhaustive pair check, Aut-equivariance over 903 maps). For a load-bearing claim that strictly refutes A(5) and gives the explicit N(5)≤43 bound, the manuscript should state more explicitly what a third party must re-run or re-derive to accept the empty-screen result (e.g., independent recomputation of the orbit census identity, hash/checksum of the dangerous-pair stream, or a short machine-checkable certificate of shell cardinality). The analytic reductions and razor
  2. [§4, Counterexample 4.2, Appendix B.2–B.3, C] Counterexample 4.2 and Theorem 4.1 assert FAS(T*)=17>16=HS3(T*) on a unique 3-inducible regular 11-vertex tournament, with FAS=HS3 for all n≤10. The ILP formulations (Appendix B.2–B.3) and Aut-orbit of the 9 minimum hitting sets are described, but the paper should record the explicit 16-arc hitting set (or a stable identifier into McKay’s catalogue plus the witness order already given) in the main text or a short appendix table so the FAS–HS3 gap is checkable without re-solving the ILP. The same applies to the six self-converse violators (Figure 4 / Appendix C): inducing profiles are given, but the numerical FAS and HS3 values per tournament are not tabulated.
minor comments (6)
  1. [§1 Definitions / Conjecture 8.1] Notation for Im,t and the margin hierarchy is introduced early and used in Conjecture 8.1; a one-line display of the chain I_{m,1}⊆⋯⊆I_{m,m} near the first use would help readers who skip the definitions block.
  2. [Figure 4] Figure 3 and Figure 5 are clear; Figure 4’s six panels are dense. Adding the FAS and HS3 numbers in each panel caption (or a small table) would make the Conjecture 2 refutation self-contained at a glance.
  3. [Table 2, Theorem 6.3] Table 2 improves Bachmeier et al.; citing the exact multiset count versus their Stirling estimate in one sentence in the table caption would clarify why three entries already improve under “exact” alone.
  4. [§8.2, Appendix D] The phrase “strike-a-voter argument” (§8.2 item 4, Appendix D) is used before it is fully glossed; a brief parenthetical on first use would help.
  5. [§3, §5, Appendix G.4] Minor typography: “aminimum-weight” (missing space) in Counterexample 3.1; “| solution” stray bar in the A(m) integrality-gap paragraph; “gained g≥ 4” double quote artifact in Appendix G.4.
  6. [Motivation and statement of AI use] The AI-use table is unusually transparent and welcome; consider moving the one-line “full responsibility” statement into the acknowledgments so the contribution table can stay in a supplement if the journal prefers.

Circularity Check

0 steps flagged

No significant circularity: refutations rest on explicit counterexamples, combinatorial proofs, and exhaustive computational certificates, not on fitted inputs or self-definitional loops.

full rationale

The paper’s load-bearing claims are (i) a pure combinatorial strengthening that every minimum FAS is a minimal 3-cycle hitting set (Theorem 2.1), (ii) explicit small counterexamples to two conjectures of Milosz–Hamel–Pierrot, certified by ILP, (iii) an exhaustive census refuting the m=3 threshold conjecture exactly on the boundary α*=2/3, and (iv) the analytic-plus-enumeration argument that Paley(43) has α*=MAS/C=181/301>3/5 yet admits no 5-voter inducing profile (Theorem 7.1). Predictability is the value of a standard zero-sum LP; m-inducibility is integral feasibility of the same covering program. Neither quantity is fitted to a target and then re-predicted. The co-backing lemma, slack arithmetic, and razor reduction are ordinary proofs; the billion-scale shell screen is a negative exhaustive search whose residual risk is verification completeness, not definitional circularity. Self-citations are absent from the load-bearing chain; prior work is cited as the source of the conjectures being refuted. No step reduces by construction to its own input.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 3 invented entities

The work sits on standard tournament/digraph combinatorics, LP duality for predictability, and classical facts about Paley tournaments and McGarvey numbers. No physical constants or data-fitted scales appear. Load-bearing extra structure is definitional (slack, level shells, double-back sets, Im,t hierarchy) plus reliance on external solvers and McKay’s tournament catalogues for censuses.

axioms (5)
  • standard math Von Neumann minimax / strong LP duality equates the two formulations of predictability α*(D) for finite digraphs.
    Used to define α* and to certify dual obstacle certificates throughout §§1,5,7.
  • domain assumption McGarvey’s theorem and subsequent quantitative bounds: every tournament is majority-inducible by finitely many (odd) voters.
    Background guaranteeing McGarvey numbers exist; cited from McGarvey, Stearns, Erdős–Moser, Bachmeier et al.
  • standard math Schrijver’s lower bound on the number of Eulerian orientations of Kn supplies the counting lower bound on labelled regular tournaments used for N(m) upper bounds.
    Invoked in Theorems 6.2–6.3 to beat profile-count upper bounds.
  • domain assumption Branch-and-cut ILP solvers (CPLEX) and CP-SAT return certified optimality/infeasibility for the stated formulations on the instance sizes used.
    Underpins all census and minimality claims in §§3–6 and Appendices B,G; not a mathematical axiom but a tooling premise.
  • standard math For q≡3 (mod 4) prime, the Paley construction on GF(q) is a well-defined arc-transitive tournament with known automorphism group of order q(q−1)/2.
    Used for Paley(43) structure, α*=MAS/C, and automorphism reduction in §7.
invented entities (3)
  • Double-back set DB(O) and co-backing lemma for 5-voter profiles independent evidence
    purpose: Finite certificate that two level-≤1 orders cannot both appear in any 5-inducing profile of Paley(43).
    Defined in §7.2; the disjointness criterion turns non-inducibility into a finite screen. Standard combinatorial packaging rather than a new physical entity.
  • Margin hierarchy classes Im,t and Conjecture 8.1 no independent evidence
    purpose: Organize which tournaments need unanimous or high-margin arcs under m-voter induction.
    Introduced in §1 and §8; only I3,1⊊I3,3 is proved. Conjectural for m≥5.
  • Obstacle digraphs G8, G9 and the n=9 obstacle catalogue independent evidence
    purpose: Minimal dual supports certifying α*<2/3 and hence non-3-inducibility.
    G8 was known; the expanded catalogue and set-cover analysis are paper-specific computational objects with clear external meaning (subdigraph obstacles).

pith-pipeline@v1.2.0-daily-grok45 · 35509 in / 3451 out tokens · 61209 ms · 2026-07-30T23:52:44.542813+00:00 · methodology

0 comments
read the original abstract

The Kemeny median problem asks for a linear order minimizing the total pairwise disagreement with $m$ given rankings of $n$ options; it is NP-hard for every even $m \ge 4$ and every odd $m \ge 7$, while $m = 3$ and $m = 5$ remain open. Weighting each arc of the majority tournament by its margin reduces the problem to minimum-weight feedback arc set (FAS). The fewest voters inducing a tournament is its McGarvey number, and its predictability $\alpha^{*}(T)$ is the largest supermajority threshold at which $T$ is inducible. We refute three conjectures on inducibility. (i) In any tournament, every minimum FAS is a minimal hitting set of the directed 3-cycles, strengthening a theorem of Milosz, Hamel and Pierrot; both of their conjectures fail: the 3-cycle extension for all odd $m \ge 5$, and the equality $\mathrm{FAS} = \mathrm{HS}_3$ at $n = 11$. (ii) The threshold conjecture proposed by Shepardson and Tovey fails for $m = 3$, exactly on the boundary (predictability $= 2/3$). (iii) For $m = 5$ it fails strictly: the Paley tournament on 43 vertices, with predictability $181/301 > 3/5$, is not the majority of any 5 voters, making it the first explicit tournament of modest size beyond the reach of five voters.

Figures

Figures reproduced from arXiv: 2607.26690 by Ararat Harutyunyan, Leonid Chindelevitch.

Figure 1
Figure 1. Figure 1: The weighted majority tournament of Counterexample 3.1 (the tournament [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The weighted majority tournament of Counterexample 3.2 ( [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The tournament T ∗ of Counterexample 4.2, drawn with the vertices on a circle in the witness order (4, 5, 6, 11, 8, 9, 10, 1, 2, 3, 7), clockwise from the top. (a) A minimum 3-cycle hitting set (blue): 16 arcs meeting every one of the 55 cyclic triangles. (b) A minimum feedback arc set (red): the 17 arcs backward in the witness order. integral | solution is a fractional one, and A(m) is precisely the asser… view at source ↗
Figure 4
Figure 4. Figure 4: The six 3-inducible self-converse tournaments on 11 vertices violating Conjecture 2 (panels (a)–(f)). [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The counterexample cA3 (Counterexample 5.2): the circulant tournament on [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: G8 (a) and G9 (b) side by side: an acyclic core of 4 vertices, a triangle-free group of vertices, and a single 4-cycle (thick red) joining them. α ∗ (G8) = 13/20, α ∗ (G9) = 15/23. tournament on ≤ 9 vertices with α ∗ = 2/3 can fail to be 3-inducible [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The four tournaments on 10 vertices with a forced arc (thick black) whose reversal remains [PITH_FULL_IMAGE:figures/full_fig_p027_7.png] view at source ↗

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

30 extracted references · 2 linked inside Pith

  1. [1]

    N. Alon. Voting paradoxes and digraphs realizations.Advances in Applied Mathematics29 (2002), 126–135

    2002

  2. [2]

    Bachmeier, F

    G. Bachmeier, F. Brandt, C. Geist, P. Harrenstein, K. Kardel, D. Peters, H. G. Seedig.k-Majority digraphs and the hardness of voting with a constant number of voters.Journal of Computer and System Sciences105 (2019), 130–157

    2019

  3. [3]

    G. Blin, M. Crochemore, S. Hamel, S. Vialette. Medians of an odd number of permutations.Pure Mathematics and Applications21(2) (2011), 161–175

    2011

  4. [4]

    Charbit, S

    P. Charbit, S. Thomassé, A. Yeo. The minimum feedback arc set problem is NP-hard for tournaments. Combinatorics, Probability and Computing16 (2007), 1–4

    2007

  5. [5]

    Dwork, R

    C. Dwork, R. Kumar, M. Naor, D. Sivakumar. Rank aggregation methods for the Web.Proc. WWW10 (2001), 613–622

    2001

  6. [6]

    Eggermont, C

    C. Eggermont, C. Hurkens, G. J. Woeginger. Realizing small tournaments through few permutations. Acta Cybernetica21 (2013), 267–271

    2013

  7. [7]

    Erdős, L

    P. Erdős, L. Moser. On the representation of directed graphs as unions of orderings.Publ. Math. Inst. Hung. Acad. Sci.9 (1964), 125–132

    1964

  8. [8]

    I. Gilboa. A necessary but insufficient condition for the stochastic binary choice problem.Journal of Mathematical Psychology34 (1990), 371–392

    1990

  9. [9]

    Grötschel, M

    M. Grötschel, M. Jünger, G. Reinelt. Facets of the linear ordering polytope.Mathematical Programming 33 (1985), 43–60

    1985

  10. [10]

    Hemaspaandra, H

    E. Hemaspaandra, H. Spakowski, J. Vogel. The complexity of Kemeny elections.Theoretical Computer Science349 (2005), 382–391

    2005

  11. [11]

    Isaev, B

    M. Isaev, B. D. McKay, R.-R. Zhang. Cumulant expansion for counting Eulerian orientations. arXiv:2309.15473 (2024)

    Pith/arXiv arXiv 2024

  12. [12]

    J. G. Kemeny. Mathematics without numbers.Daedalus88 (1959), 577–591

    1959

  13. [13]

    Kenyon-Mathieu, W

    C. Kenyon-Mathieu, W. Schudy. How to rank with few errors: a PTAS for weighted feedback arc set on tournaments.Proc. STOC(2007), 95–103

    2007

  14. [14]

    J. Mala. Onλ-majority voting paradoxes.Mathematical Social Sciences37 (1999), 39–44

    1999

  15. [15]

    D. C. McGarvey. A theorem on the construction of voting paradoxes.Econometrica21 (1953), 608–610

    1953

  16. [16]

    B. D. McKay. Combinatorial data: digraphs (tournament catalogues). https://users.cecs.anu.edu.au/~bdm/data/digraphs.html, last checked July 13, 2026

    2026

  17. [17]

    Milosz, S

    R. Milosz, S. Hamel, A. Pierrot. Median of 3 permutations, 3-cycles and 3-hitting set problem.Proc. IWOCA 2018, LNCS 10979, Springer (2018), 224–236

    2018

  18. [18]

    Schrijver

    A. Schrijver. Bounds on the number of Eulerian orientations.Combinatorica3 (1983), 375–380. 28

    1983

  19. [19]

    Shepardson, C

    D. Shepardson, C. A. Tovey. Smallest tournaments not realizable by2 3-majority voting.Social Choice and Welfare33 (2009), 495–503

    2009

  20. [20]

    R. Stearns. The voting problem.American Mathematical Monthly66 (1959), 761–763

    1959

  21. [21]

    L. A. Wolsey.Integer Programming. 2nd edition, Wiley (2020)

    2020

  22. [22]

    H. P. Young, A. Levenglick. A consistent extension of Condorcet’s election principle.SIAM Journal on Applied Mathematics35 (1978), 285–300

    1978

  23. [23]

    Antonov, G

    M. Antonov, G. Csárdi, S. Horvát, K. Müller, T. Nepusz, D. Noom, M. Salmon, V. Traag, B. F. Welles, F. Zanini. igraph enables fast and robust network analysis across programming languages. arXiv:2311.10260 (2023)

    Pith/arXiv arXiv 2023

  24. [24]

    D. Fidler. A recurrence for bounds on dominating sets ink-majority tournaments.The Electronic Journal of Combinatorics18 (2011), #P166

    2011

  25. [25]

    M. Held, R. M. Karp. A dynamic programming approach to sequencing problems.Journal of the Society for Industrial and Applied Mathematics10 (1962), 196–210

    1962

  26. [26]

    A. B. Kahn. Topological sorting of large networks.Communications of the ACM5 (1962), 558–562

    1962

  27. [27]

    Burnside.Theory of Groups of Finite Order

    W. Burnside.Theory of Groups of Finite Order. 2nd edition, Cambridge University Press (1911)

    1911

  28. [28]

    Chindelevitch, J

    L. Chindelevitch, J. P. P. Zanetti, J. Meidanis. On the rank-distance median of 3 permutations.BMC Bioinformatics19 (Suppl. 6) (2018), #142

    2018

  29. [29]

    de Moraes, J

    V. de Moraes, J. Meidanis. Time complexity and relaxation gap for the rank median of three genomes. Comparative Genomics, LNBI 16569, Springer (2026), 3–28

    2026

  30. [30]

    J. W. Moon.Topics on Tournaments. Holt, Rinehart and Winston (1968). 29

    1968