pith. sign in

arxiv: 2501.18030 · v2 · submitted 2025-01-29 · 🧮 math.CO

Kohnert posets and polynomials of northeast diagrams

Aram Bingham , Beth Anne Castellano , Kimberly P. Hadaway , Reuven Hodges , Yichen Ma , Alex Moon , Kyle Salois This is my paper

Pith reviewed 2026-05-23 04:54 UTC · model grok-4.3

classification 🧮 math.CO
keywords Kohnert posetsnortheast diagramsbounded posetsranked posetsmultiplicity-free posetslock diagramspolynomial-time classification
0
0 comments X

The pith

Northeast diagrams permit polynomial-time classification of their Kohnert posets as bounded, ranked, or multiplicity-free.

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

Kohnert polynomials and their posets generalize Schubert polynomials and type A Demazure characters. The paper restricts attention to those indexed by northeast diagrams and supplies separate classifications for the cases in which the poset is bounded, in which it is ranked, and in which it is multiplicity-free. Each classification runs in time polynomial in the number of cells of the diagram. A sympathetic reader would care because these objects link combinatorics to geometry and representation theory, so efficient recognition of special cases could simplify explicit computations. The same classifications specialize to elementary criteria when the diagrams are further restricted to lock diagrams.

Core claim

The paper establishes separate classifications of the bounded, ranked, and multiplicity-free Kohnert posets for northeast diagrams. These classifications can each be computed in polynomial time with respect to the number of cells in the diagram. The results are then specialized to obtain simple criteria for lock diagrams.

What carries the argument

The Kohnert poset of a northeast diagram, which encodes the covering relations among the Kohnert tableaux used to expand the associated polynomial.

If this is right

  • Algorithms exist that decide in polynomial time whether any given northeast diagram yields a bounded Kohnert poset.
  • Analogous polynomial-time decision procedures exist for the ranked and multiplicity-free properties.
  • When the northeast diagram is a lock diagram the membership tests reduce to elementary combinatorial conditions.
  • These decision procedures apply directly to the computation of the corresponding Kohnert polynomials.

Where Pith is reading between the lines

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

  • The structural simplicity that makes the classifications polynomial-time may indicate that northeast diagrams occupy a sweet spot between arbitrary diagrams and even more rigid families.
  • The same decision procedures could be used as filters when enumerating or sampling diagrams for larger-scale representation-theoretic calculations.
  • Geometric or representation-theoretic consequences of the bounded or multiplicity-free cases might now be studied by generating only those northeast diagrams that satisfy the criteria.

Load-bearing premise

The restriction to northeast diagrams is what permits the stated polynomial-time classifications to exist.

What would settle it

A northeast diagram whose cell count is small yet for which deciding whether its Kohnert poset is bounded requires superpolynomial time, or for which the given classification rule returns the wrong answer.

Figures

Figures reproduced from arXiv: 2501.18030 by Alex Moon, Aram Bingham, Beth Anne Castellano, Kimberly P. Hadaway, Kyle Salois, Reuven Hodges, Yichen Ma.

Figure 1
Figure 1. Figure 1: The diagram D = {(2, 2),(3, 1),(4, 1),(4, 2)} moves to the position directly below itself, not jumping over any other cells. Otherwise, it is called a jump Kohnert move. The Kohnert poset of a diagram D, denoted by P(D), is the set of all diagrams that can be obtained from D via a sequence of Kohnert moves. It is the transitive closure of the relations D2 < D1 for D1, D2 ∈ P(D) if D2 is the result of apply… view at source ↗
Figure 2
Figure 2. Figure 2: P(D) where D = {(2, 1),(2, 2),(3, 1),(3, 2)} Let Compn := Z n ≥0 be the set of weak compositions of length n. The row weight of a diagram D, denoted by rwt(D), is the weak composition (α1, . . . , αℓ) such that αi is the number of cells in row i, and ℓ is the maximum row index such that row ℓ is nonempty. The column weight cwt(D) is the composition (β1, . . . , βm) such that βi is the number of cells in co… view at source ↗
Figure 3
Figure 3. Figure 3: Two diagrams The naming of these diagrams arises from intuition relating to the cardinal directions. In a northeast diagram, for every two cells where one cell (in position (r1, c1)) is strictly northwest of the other (in position (r2, c2)), there is a cell located at the “northeast corner” of the rectangle formed by the two cells, i.e., the position (r1, c2). Similarly, in a southeast diagram, for every t… view at source ↗
Figure 4
Figure 4. Figure 4: The lock diagram D(α) for α = (1, 3, 1, 0, 2) . Proof. Assume that D has m columns. (Proof of ⇒) Suppose D satisfies both the northeast and southeast conditions and that (r, c) ∈ D for some 1 ≤ c < m. Column c + 1 is nonempty, so there exists some r ′ such that (r ′ , c + 1) ∈ D. We have three cases. Case 1: r ′ > r. Then (r, c + 1) ∈ D by the southeast condition. Case 2: r ′ = r. Then (r, c + 1) ∈ D by co… view at source ↗
Figure 5
Figure 5. Figure 5: Three diagrams with labelings. Definition 2.5. The column content CL = (C1, C2, . . .) of a strict labeling L is the sequence such that Ci ⊆ Z≥0 is set of labels of cells in column i. Two labelings L,L ′ are said to be column-equivalent if CL = CL′ . In other words, two labelings are column-equivalent if they have the same set of labels in each fixed column. We refer to the pair of a diagram and its labeli… view at source ↗
Figure 6
Figure 6. Figure 6: The standard labelings of two diagrams (center, right) with respect to a diagram with a super-standard labeling (left). In a diagram with a standard labeling, we refer to a cell with the label i as an i-cell. Definition 2.8. Let D be a diagram. A northeast labeling L : D → N is a labeling which satisfies the following properties: (1) L is strict. (2) Each label in row i is at least i. (3) If cell x ′ is to… view at source ↗
Figure 7
Figure 7. Figure 7: A pair of northeast tableaux where (b) is the initial tableau of (a). Lemma 2.13. Let T = (D,L) be a northeast tableau, and let T0 = (D0,L0) be the initial northeast tableau of T . If D′ is a diagram obtained by performing a single Kohnert move on D, then the standard labeling L ′ of D′ with respect to D0 is a northeast labeling. Proof. By Remark 2.7, the standard labeling of D′ may be constructed from the… view at source ↗
Figure 8
Figure 8. Figure 8: depicts what the diagram D must have looked like at the conclusion of Step (4). The red cells are the ones where the existence is inferred by the northeast property of the labeling. The cell x is the top left cell, labeled Lk. It clearly cannot be the subject of a Kohnert move, as it is not the rightmost cell in its row. Since L ′ satisfies the four properties of Definition 2.8, it is a northeast labeling.… view at source ↗
Figure 9
Figure 9. Figure 9: If (rk−1, ck−1) with label e = move(Dk−1, Dk) were not rightmost in Ek (black boxes), then it would need to be blocked by a box with label e ′ = move(Db, Db+1). But then this cell would not be rightmost when it is at (rk−1 + 1, ck−1) in Dq (red boxes) in the case of a ≤ q ≤ k − 1. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
Figure 11
Figure 11. Figure 11: The relative positions of cells y1, y2 in D and y ′ 1 , y′ 2 in D′ , respectively. Note that y ′ 1 is strictly below and to the left of y ′ 2 . By Property (4) of Definition 2.8, L1 6= L2. Moreover, L1 > L2 would contradict Lemma 2.9. Therefore, L1 < L2. Define x2 = (L2, c2) ∈ D0. Let x1 = (L1, c˜1) be the cell in D0 such that ˜c1 < c2 and ˜c1 is maximal. Such a choice of cell exists because (L1, c1) ∈ D0… view at source ↗
Figure 14
Figure 14. Figure 14: An example of constructing the canonical minimal element Dcan from an ini￾tial northeast diagram D0 with the super-standard labeling. Note that the edges do not necessarily represent covering relations, for example in the lowest two diagrams. For the remainder of this section, we let Dcan denote the minimal element of P(D0) obtained using the canonical procedure. We refer to Dcan as the canonical minimal … view at source ↗
Figure 15
Figure 15. Figure 15: An example of a lock diagram that yields a ranked and bounded Kohnert poset. Proof. For P( D(α)) to be bounded, recall that α must be such that the nonzero entries that follow the first αi = 0 are weakly increasing. Thus, α is such that α1 through αi−1 are greater than 0, αi = 0, and for each αj 6= 0 with j > i and αk being the next nonzero entry following αj , we have αj ≤ αk. Recall also that for P( D(α… view at source ↗
read the original abstract

Kohnert polynomials and their associated posets are combinatorial objects with deep geometric and representation theoretic connections, generalizing both Schubert polynomials and type A Demazure characters. In this paper, we explore the properties of Kohnert polynomials and their posets indexed by northeast diagrams. We give separate classifications of the bounded, ranked, and multiplicity-free Kohnert posets for northeast diagrams, each of which can be computed in polynomial time with respect to the number of cells in the diagram. As an initial application, we specialize these classifications to simple criteria in the case of lock diagrams.

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

0 major / 3 minor

Summary. The manuscript classifies the bounded, ranked, and multiplicity-free Kohnert posets indexed by northeast diagrams. It asserts that each of these three classifications admits a polynomial-time algorithm in the number of cells of the diagram. The classifications are then specialized to obtain simple criteria in the case of lock diagrams.

Significance. If the stated classifications and their polynomial-time claims hold, the work supplies practical combinatorial criteria for three fundamental poset properties in a geometrically and representation-theoretically significant family of diagrams. The explicit restriction to northeast diagrams is acknowledged and the polynomial-time results constitute a concrete algorithmic contribution that could be used to test conjectures or compute examples in the broader theory of Kohnert polynomials.

minor comments (3)
  1. The abstract states that the classifications 'can be computed in polynomial time'; the main text should include an explicit complexity analysis (e.g., a theorem stating the running time in terms of the number of cells) rather than leaving the claim implicit after the combinatorial description.
  2. The specialization to lock diagrams is described as yielding 'simple criteria'; a short table or enumerated list of the resulting conditions for each of the three properties would improve readability.
  3. Notation for northeast diagrams and lock diagrams should be introduced with a single running example that is carried through the three classification sections to illustrate each criterion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment of the significance of the classifications and polynomial-time algorithms, and recommendation of minor revision. The report raises no specific major comments or requests for changes.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states direct combinatorial classifications of bounded, ranked, and multiplicity-free Kohnert posets specifically for northeast diagrams, each computable in polynomial time in the number of cells. No derivation chain is presented that reduces a claimed result to a fitted parameter, self-definition, or load-bearing self-citation; the northeast restriction is stated explicitly as the domain of the results. The abstract and skeptic analysis indicate independent combinatorial criteria rather than any renaming, ansatz smuggling, or uniqueness imported from prior author work. This is the normal case of a self-contained classification result.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no information on free parameters, axioms, or invented entities; none can be identified from the given text.

pith-pipeline@v0.9.0 · 5630 in / 931 out tokens · 29326 ms · 2026-05-23T04:54:38.196886+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

15 extracted references · 15 canonical work pages

  1. [1]

    A bijective proof of Kohnert’s rule for Schubert p olynomials

    Sami Assaf. “A bijective proof of Kohnert’s rule for Schubert p olynomials”. Comb. Theory 2.1 (2022), Paper No. 5, 9. doi: 10.5070/c62156877

    work page doi:10.5070/c62156877 2022

  2. [2]

    Demazure crystals for Kohnert polynomials

    Sami Assaf. “Demazure crystals for Kohnert polynomials”. Trans. Amer. Math. Soc. 375.3 (2022), pp. 147–2186. doi: 10.1090/tran/8560

    work page doi:10.1090/tran/8560 2022

  3. [3]

    Kohnert Polynomials

    Sami Assaf and Dominic Searles. “Kohnert Polynomials”. Experimental Mathematics 31.1 (2022), pp. 93–119. doi: 10.1080/10586458.2019.1588180

    work page doi:10.1080/10586458.2019.1588180 2022

  4. [4]

    Kohnert tableaux and a lifting of quasi-Schur functions

    Sami Assaf and Dominic Searles. “Kohnert tableaux and a lifting of quasi-Schur functions”. Journal of Combinatorial Theory, Series A 156 (2018), pp. 85–118. issn: 0097-3165. doi: 10.1016/j.jcta.2018.01.001

    work page doi:10.1016/j.jcta.2018.01.001 2018

  5. [5]

    On ranked and bounded Kohnert posets

    Laura Colmenarejo, Felix Hutchins, Nicholas Mayers, and Etienne Phillips. On ranked and bounded Kohnert posets . 2023. arXiv: 2309.07747

    work page arXiv 2023

  6. [6]

    Zero-one S chubert polynomials

    Alex Fink, Karola M´ esz´ aros, and Avery St. Dizier. “Zero-one S chubert polynomials”. Math. Z. 297.3-4 (2021), pp. 1023–1042. doi: 10.1007/s00209-020-02544-2 . 24

    work page doi:10.1007/s00209-020-02544-2 2021

  7. [7]

    Classification of Levi-spherical Schubert Varieties

    Yibo Gao, Reuven Hodges, and Alexander Yong. “Classification of Levi-spherical Schubert Varieties”. Selecta Mathematica 29.4 (2023), Paper No. 55. doi: 10.1007/s00029-023-00856-9

    work page doi:10.1007/s00029-023-00856-9 2023

  8. [8]

    Coxeter Combinatorics an d Spherical Schubert Geometry

    Reuven Hodges and Alexander Yong. “Coxeter Combinatorics an d Spherical Schubert Geometry”. Journal of Lie Theory 32.2 (2022), pp. 447–474

    work page 2022

  9. [9]

    Multiplicity-Free Key Polyno mials

    Reuven Hodges and Alexander Yong. “Multiplicity-Free Key Polyno mials”. Annals of Combinatorics 27.2 (June 2023), pp. 387–411. doi: 10.1007/s00026-022-00574-7

    work page doi:10.1007/s00026-022-00574-7 2023

  10. [10]

    Weintrauben, Polynome, Tableaux

    Axel Kohnert. “Weintrauben, Polynome, Tableaux”. PhD thes is. Universit¨ at Bayreuth, 1991

    work page 1991

  11. [11]

    What is a combinatorial interpretation?

    Igor Pak. “What is a combinatorial interpretation?” Open problems in algebraic combinatorics. Vol. 110. Proc. Sympos. Pure Math. Amer. Math. Soc., Providence, RI, 202 4, pp. 191–260

    work page

  12. [12]

    Positivity problems and conjectures in alge braic combinatorics

    Richard P. Stanley. “Positivity problems and conjectures in alge braic combinatorics”. Mathematics: frontiers and perspectives . Amer. Math. Soc., Providence, RI, 2000, pp. 295–319

    work page 2000

  13. [13]

    Locks fit into keys: a crystal analysis of lock po lynomials

    George Wang. “Locks fit into keys: a crystal analysis of lock po lynomials”. Annals of Combinatorics 24 (2020), pp. 767–789. doi: 10.1007/s00026-020-00513-4

    work page doi:10.1007/s00026-020-00513-4 2020

  14. [14]

    A derivation of Kohnert’s algorithm from Monk’s ru le

    Rudolf Winkel. “A derivation of Kohnert’s algorithm from Monk’s ru le”. S´ em. Lothar. Combin. 48 (2002), Art. B48f, 14

    work page 2002

  15. [15]

    Diagram rules for the generation of Schubert po lynomials

    Rudolf Winkel. “Diagram rules for the generation of Schubert po lynomials”. J. Combin. Theory Ser. A 86.1 (1999), pp. 14–48. doi: 10.1006/jcta.1998.2931. (A. Bingham) Department of Mathematics, IIT Bombay, Pow ai, Mumbai 400 07 6, India Email address : aram@matmor.unam.mx (B. A. Castellano) Department of Mathematics, Dartmouth College, Hanover, NH 03 755 ...

    work page doi:10.1006/jcta.1998.2931 1999