pith. sign in

arxiv: 2604.09290 · v1 · submitted 2026-04-10 · 🧮 math.CO

More Vertices of the Tristochastic Polytope

Nati Linial , Zur Luria , Maya Trakhtman This is my paper

Pith reviewed 2026-05-10 16:49 UTC · model grok-4.3

classification 🧮 math.CO
keywords tristochastic polytopeLatin squaresverticesextreme pointsBirkhoff theoremdoubly stochastic matricesmultidimensional arrayscombinatorial constructions
0
0 comments X

The pith

The tristochastic polytope Δ_n has at least L_n^{2-o(1)} vertices, where L_n counts the Latin squares of order n.

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

The paper proves a lower bound on the number of vertices of the polytope Δ_n formed by n by n by n arrays with nonnegative entries that sum to one along every row, column, and shaft. While the L_n Latin squares are known to be vertices, the result shows there are asymptotically almost L_n squared many vertices in total. A sympathetic reader cares because this demonstrates that the direct analog of Birkhoff's theorem for doubly stochastic matrices fails in three dimensions, with Latin squares accounting for only a vanishingly small fraction of the extreme points. The work therefore reveals that the geometry of tristochastic polytopes is considerably richer than the two-dimensional case suggests.

Core claim

In analogy with Birkhoff's theorem, each of the L_n order-n Latin squares is a vertex of the tristochastic polytope Δ_n in R^{n^3}. In contrast to the two-dimensional case, however, Latin squares form a vanishingly small subset of Δ_n's vertex set. The paper shows that Δ_n has at least L_n^{2-o(1)} vertices.

What carries the argument

A combinatorial construction producing at least L_n^{2-o(1)} distinct extreme points of Δ_n beyond the Latin squares

If this is right

  • Latin squares constitute only a vanishingly small fraction of the vertices of Δ_n.
  • The vertex set of Δ_n is at least quadratically larger than the set of Latin squares.
  • Birkhoff's theorem does not generalize to three dimensions by simply replacing permutations with Latin squares.
  • The number of vertices of Δ_n is asymptotically at least L_n to the power 2 minus a lower-order term.

Where Pith is reading between the lines

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

  • For concrete small n one could enumerate the vertices of Δ_n and check whether the count meets or exceeds the stated lower bound.
  • The result may imply that linear optimization over tristochastic arrays requires algorithms that scale with a superlinear number of vertices.
  • Similar lower-bound techniques might apply to higher-dimensional multistochastic polytopes.

Load-bearing premise

There exists a construction that yields at least L_n^{2-o(1)} distinct points in Δ_n which are extreme and cannot be expressed as convex combinations of other points in the polytope.

What would settle it

An explicit count of all vertices of Δ_n for some moderate n where L_n is known, if the total falls below L_n^{2-o(1)}.

Figures

Figures reproduced from arXiv: 2604.09290 by Maya Trakhtman, Nati Linial, Zur Luria.

Figure 1
Figure 1. Figure 1: The Construction - It has 5 stages and proceeds from the bottom up. Stage 1 - generating [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Split H(1,k) into: P - the north-west  n 2  ×  n 2  × k subarray, Q - the south-east  n 2  ×  n 2  × k subarray, NE - the north-east  n 2  ×  n 2  × k subarray, SW - the south-west  n 2  ×  n 2  × k subarray. Proof. This is easily verified for N = 12, 13, 14, 15, 16. For larger N, argue by induction in steps of 5. We deal with Q likewise, with minor sizes 4 ≤ c ′ 1 ≤ c ′ 2 ≤ . . . ≤ c ′ k ≤… view at source ↗
Figure 3
Figure 3. Figure 3: Reserved places for the diagonal minors Ci of size ci × ci for layers i = 1, . . . , k in D(P). Next, we describe the construction of each layer in P. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: To start the construction of layer 3 (step 1), we place a standard cycle within minor [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The subarray S 3 ⊂ P (light green) defined by removing the x-walls and y-walls of P that intersect with the minor C3 (colored in gray and dark green), yielding the size  n 2  − c3  ×  n 2  − c3  ×k. Associate with S i a bipartite graph Gi = ⟨X ∪ Y, Ei ⟩, where the vertex sets X and Y represent the rows and columns of Di = D(S i ), respectively, thus |X| = |Y | =  n 2  − ci . An edge (x, y) ∈ X × Y … view at source ↗
Figure 6
Figure 6. Figure 6: A lower bound on the vertex degrees in Gi follows, provided that we find many 0 entries in each row of Di . Nonzero entries are marked in dark gray. A row in the sub-array S i has  n 2  − ci entries. At most 2(i − 1) non-zero entries in a row are due to choices made at lower layers. Also, each row meets some diagonal minor Cj (j ̸= i), and the corresponding cj cells do not count toward the degree. For ex… view at source ↗
Figure 7
Figure 7. Figure 7: Step 2 applied to layer 3. Circled in red - the sub-array [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: (x1, y1) is a fixed 1 2 -cell in Ci outside the main diagonal. X2 (Yellow) is the set of non-zero cells in column y1 (excluding Ci). Likewise, Y2 (Blue) is the set of non-zero cells in row x1 (excluding Ci). Arrows indicate how entries in X2 ∪Y2 eliminate potential swap candidates in the Hamiltonian cycle Li (in green) at their same columns or rows. The proof shows that green cells outnumber the eliminated… view at source ↗
Figure 9
Figure 9. Figure 9: With two 1 2 -cells (x1, y1) ∈ (Ci \ the main diagonal) and (x2, y2) ∈ Li , s.t. both (x1, y2) and (x2, y1) are 0-cells, we apply the switching operation indicated in red (step 3). 2.3 Stage 2 - Connecting the Construction: Layer k + 1 We have constructed so far L ′ 1 , L′ 2 , . . . , L′ k , disjoint Hamiltonian cycles in P, and, similarly, L ′′ 1 , L′′ 2 , . . . , L′′ k , disjoint Hamiltonian cycles in Q,… view at source ↗
Figure 10
Figure 10. Figure 10: The construction of layer k + 1 when n is even. If n is odd, the number of rows and columns in NE(k+1) and SW(k+1) differ by one. Therefore, to complete the cycle we must use a cell from Q(k+1). This is possible, as each row and column of Q(k+1) has available 0-cells. We omit the technical details and provide instead a graphical illustration of the necessary steps, see [PITH_FULL_IMAGE:figures/full_fig_p… view at source ↗
Figure 11
Figure 11. Figure 11: The construction of layer k + 1 when n is odd. In this case we use a 0-cell in Q. done. Otherwise, Uk+1 is a connected bipartite graph, whence, by proposition 1.1, it admits a unique 2-vertex-coloring (up to swapping the two colors), denoted by red and blue, see [PITH_FULL_IMAGE:figures/full_fig_p011_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The 2-coloring of Dk+1(H), the main diagonal consists of 1-cells and the corresponding vertices in Uk+1 are bi-colored. matrix of G. Similarly, let GR (resp. GB) be the subgraph of G that corresponds to the red (resp. blue) 1 2 -cells in Dk+1, with adjacency matrices MR and MB, respectively. Lemma 2.2. Asymptotically almost every permutation matrix supported on the 1 2 -cells in Dk+1 is bi￾colored. Proof.… view at source ↗
Figure 13
Figure 13. Figure 13: Left panel: the chosen bi-chromatic perfect matching [PITH_FULL_IMAGE:figures/full_fig_p013_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Layer k + 2: a bi-colored permutation of the 1 2 -cells (red and blue), and another permutation of the 0-cells (black) s.t. Uk+2 is not 2-colorable. We conclude that Uk+2 is not bipartite, as witnessed by the vertex that corresponds to the cell (x, y, k + 2), which cannot be colored in either blue or red. Consequently, Ui is not bipartite for all i ≥ k + 2. Additionally, the graph Uk+2 is connected, since… view at source ↗
Figure 15
Figure 15. Figure 15: The construction of slice (1, k + 2), dark purple represents the 1-cells, light purple represents the 1 2 -cells of Dk+2(H). 14 [PITH_FULL_IMAGE:figures/full_fig_p014_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Histograms of row support sizes for randomly sampled tri-stochastic vertices across dimensions [PITH_FULL_IMAGE:figures/full_fig_p018_16.png] view at source ↗
read the original abstract

The $n\times n$ doubly stochastic matrices constitute a polytope in $\mathbb{R}^{n^2}$, and by Birkhoff's theorem, its vertex set coincides with the set of order-$n$ permutation matrices.\\ A tristochastic array is an $n \times n\times n$ array of nonnegative reals, where each row, column, and shaft sums to one. These arrays constitute a polytope $\Delta_n$ in $\mathbb{R}^{n^3}$. In analogy, it is easy to see that each of the $L_n$ order-$n$ Latin squares is a vertex of $\Delta_n$, but in contrast to Birkhoff's theorem, Latin squares form a vanishingly small subset of $\Delta_n$'s vertex set. We show here that $\Delta_n$ has at least $L_n^{2-o(1)}$ vertices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves a new lower bound on the number of vertices of the tristochastic polytope Δ_n in R^{n^3}: at least L_n^{2-o(1)} vertices, where L_n is the number of Latin squares of order n. This is obtained by an explicit construction that produces many additional extreme points beyond the L_n Latin squares themselves, which are already known to be vertices by a direct analogue of Birkhoff's theorem.

Significance. If the construction and the accompanying extremality arguments are correct, the result substantially strengthens the known lower bounds on the vertex count of Δ_n and shows that Latin squares form a vanishingly small fraction of the vertices. The quantitative form of the bound (with the 2-o(1) exponent) is a concrete combinatorial statement that could guide further work on the facial structure of multi-stochastic polytopes.

major comments (2)
  1. [§3] §3 (Construction from Latin-square pairs): the argument that each generated array is extreme relies on the support admitting no nontrivial convex decomposition that preserves the three uniform marginals. The text must explicitly bound the number of pairs whose supports contain an alternating cycle (or other signed perturbation) that would place the point in the relative interior of a positive-dimensional face; without a quantitative estimate showing that the bad pairs are at most L_n^{o(1)}, the claimed exponent cannot be guaranteed.
  2. [Theorem 1.1] Theorem 1.1 (main lower bound): the derivation of the 2-o(1) exponent assumes that a (1-o(1))-fraction of the L_n^2 candidate arrays are extreme. A concrete estimate (or a probabilistic argument) establishing that the proportion of non-extreme outputs is o(1) is load-bearing for the stated result and is not yet visible in the provided argument.
minor comments (2)
  1. [Abstract] The abstract states the claim cleanly but does not indicate the construction method; a single sentence sketching the use of Latin-square pairs would improve readability.
  2. [§2] Notation for the three marginals (row, column, shaft) should be introduced once and used uniformly; occasional shifts between “line sums” and “shaft sums” are minor but distracting.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for greater explicitness in the quantitative aspects of our extremality arguments. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [§3] §3 (Construction from Latin-square pairs): the argument that each generated array is extreme relies on the support admitting no nontrivial convex decomposition that preserves the three uniform marginals. The text must explicitly bound the number of pairs whose supports contain an alternating cycle (or other signed perturbation) that would place the point in the relative interior of a positive-dimensional face; without a quantitative estimate showing that the bad pairs are at most L_n^{o(1)}, the claimed exponent cannot be guaranteed.

    Authors: We agree that the current presentation does not supply an explicit quantitative bound on the proportion of pairs whose supports admit alternating cycles (or other signed perturbations). In the revised version we will insert a new subsection in §3 that provides a probabilistic estimate: for a uniformly random pair of Latin squares, the probability that the union of their supports contains a nontrivial alternating cycle compatible with the marginal constraints is o(1). The argument proceeds by a union bound over potential cycle lengths together with the known asymptotic enumeration and mixing properties of Latin squares; this shows that the number of affected pairs is at most L_n^{o(1)}. Consequently the construction still yields L_n^{2-o(1)} distinct extreme points. revision: yes

  2. Referee: [Theorem 1.1] Theorem 1.1 (main lower bound): the derivation of the 2-o(1) exponent assumes that a (1-o(1))-fraction of the L_n^2 candidate arrays are extreme. A concrete estimate (or a probabilistic argument) establishing that the proportion of non-extreme outputs is o(1) is load-bearing for the stated result and is not yet visible in the provided argument.

    Authors: The referee is correct that the proportion of extreme outputs must be shown to be 1-o(1) for the exponent to follow. We will revise the proof of Theorem 1.1 to cite the new estimate from the revised §3, explicitly stating that the fraction of pairs producing non-extreme arrays is o(1) and that the generated arrays remain distinct for all but o(L_n^2) pairs. This makes the load-bearing step fully visible and rigorous. revision: yes

Circularity Check

0 steps flagged

No circularity; lower bound obtained by explicit combinatorial construction

full rationale

The paper establishes a lower bound on the number of vertices of Δ_n by constructing a family of at least L_n^{2-o(1)} distinct extreme points (extending the known Latin-square vertices). This is a direct existence proof via combinatorial construction rather than any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation. The derivation chain is self-contained against external benchmarks such as Birkhoff's theorem and the definition of the tristochastic polytope; no step reduces the claimed count to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available, so the precise axioms, parameters, and entities used in the proof cannot be audited. The claim rests on the existence of an unspecified construction that produces many additional vertices.

axioms (2)
  • standard math Birkhoff's theorem identifies the vertices of the doubly stochastic polytope with permutation matrices
    Invoked as the two-dimensional analogy.
  • domain assumption Every Latin square corresponds to a vertex of the tristochastic polytope
    Stated as easy to see.

pith-pipeline@v0.9.0 · 5445 in / 1245 out tokens · 66613 ms · 2026-05-10T16:49:03.169235+00:00 · methodology

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

12 extracted references · 12 canonical work pages

  1. [1]

    Tres observaciones sobre el algebra lineal.Univ

    Garrett Birkhoff. Tres observaciones sobre el algebra lineal.Univ. Nac. Tucuman, Ser. A, 5:147–154, 1946

    work page 1946

  2. [2]

    Some properties of nonnegative matrices and their permanents.Soviet Mathematics Doklady, 14:945–949, 1973

    Lev Meerovich Br` egman. Some properties of nonnegative matrices and their permanents.Soviet Mathematics Doklady, 14:945–949, 1973

    work page 1973

  3. [3]

    Hamiltonian cycles in Dirac graphs.Combinatorica, 29(3):299–326, 2009

    Bill Cuckler and Jeff Kahn. Hamiltonian cycles in Dirac graphs.Combinatorica, 29(3):299–326, 2009

    work page 2009

  4. [4]

    Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81, 1952

    Gabriel Andrew Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81, 1952

    work page 1952

  5. [5]

    Egorychev

    Gregory P. Egorychev. The solution of Van der Waerden’s problem for permanents.Advances in Mathematics, 42(3):299–305, 1981

    work page 1981

  6. [6]

    Falikman

    Dmitry I. Falikman. Proof of the Van der Waerden conjecture regarding the permanent of a doubly stochastic matrix.Mathematical notes of the Academy of Sciences of the USSR, 29(6):475–479, 1981

    work page 1981

  7. [7]

    P.M. Hummel. A note on Stirling’s formula.The American Mathematical Monthly, 47(2):97–99, 1940

    work page 1940

  8. [8]

    An upper bound on the number of high-dimensional permutations

    Nathan Linial and Zur Luria. An upper bound on the number of high-dimensional permutations. Comb., 34(4):471–486, 2014

    work page 2014

  9. [9]

    On the vertices of the d-dimensional Birkhoff polytope.Discrete & Computational Geometry, 51(1):161–170, 2014

    Nathan Linial and Zur Luria. On the vertices of the d-dimensional Birkhoff polytope.Discrete & Computational Geometry, 51(1):161–170, 2014

    work page 2014

  10. [10]

    Upper bounds for permanents of (0,1)-matrices.Bulletin of the American Mathematical Society, 69:789–791, 1963

    Henryk Minc. Upper bounds for permanents of (0,1)-matrices.Bulletin of the American Mathematical Society, 69:789–791, 1963

    work page 1963

  11. [11]

    On Hamiltonian bipartite graphs.Israel Journal of Mathematics, 1(3):163–165, 1963

    John Moon and Leo Moser. On Hamiltonian bipartite graphs.Israel Journal of Mathematics, 1(3):163–165, 1963

    work page 1963

  12. [12]

    Cambridge university press, 2001

    Jacobus Hendricus Van Lint and Richard Michael Wilson.A course in combinatorics. Cambridge university press, 2001. 19

    work page 2001