Pith. sign in

REVIEW 3 minor 29 references

Universal probability bounds for partial Latin squares

T0 review · 0 major / 3 minor · reviewed 2026-06-26 · grok-4.3

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

Pith's one-line read If 2α + β < 1 then any partial Latin square with k cells in at most αn rows and βn columns appears in a random Latin square of order n with probability between (δ/n)^k and (Δ/n)^k for positive constants δ, Δ.

desk verdict The paper gives a new uniform probability sandwich for embedding sparse partial Latin squares and uses it for the first proof that expected 3-subsquares stay bounded away from zero. read the letter →

arxiv 2606.18174 v2 pith:MU7YOBP2 submitted 2026-06-16 math.CO

Jack Allsop , Patrick Morris This is my paper
classification math.CO
keywords partialLatinsquaresrandomprobabilityboundssubsquaressquarecompletionsexpectedcountscombinatorialcounting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves that under a condition limiting how many rows and columns a partial Latin square uses, its appearance probability in a random Latin square is bounded above and below by constants times (1/n) to the power of the number of filled cells. This uniform bound holds for all such partial squares when the row and column fractions satisfy 2α + β < 1. The bound is then applied to show that the expected count of 3 by 3 subsquares stays positive as the order n grows large, and to improve estimates for the expected number of larger subsquares. A reader would care because it provides a tool for studying the typical structure of random Latin squares without needing exact counts.

What carries the argument

The combinatorial counting argument that produces uniform positive constants δ and Δ for the probability sandwich under the row-column density condition 2α + β < 1.

What would settle it

A sequence of partial Latin squares obeying the row and column bounds for which the containing probability lies outside every interval of the form [(δ/n)^k, (Δ/n)^k] for fixed positive δ and Δ would falsify the universal bound.

Watch

Extended reading notes

Core claim

If α, β > 0 satisfy 2α + β < 1, then there exist positive constants δ = δ(α, β) and Δ = Δ(α, β) such that for any partial Latin square P of order n with k non-empty cells occupying at most αn rows and βn columns, the probability that a random Latin square of order n contains P lies between (δ/n)^k and (Δ/n)^k.

Load-bearing premise

The combinatorial counting argument succeeds in producing positive constants δ and Δ that work uniformly for all partial Latin squares meeting the row/column occupancy bounds whenever 2α+β<1.

Editorial extensions

If this is right

  • The expected number of subsquares of order 3 in a random Latin square of order n remains bounded away from zero as n tends to infinity.
  • The expected number of subsquares of order a admits improved asymptotics when 2 < a = o(n^{1/2}).
  • The same probability bounds apply directly to other sparse configurations inside random Latin squares and to questions about completability of partial Latin squares.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The counting technique might extend to bound the probability of containing other sparse combinatorial objects such as partial designs or graphs with similar density restrictions.
  • Higher moments or concentration results for the number of subsquares could follow from iterating the same probability estimates.
  • The result suggests that the local structure of a typical Latin square resembles that of a random object once row and column occupancies stay below the given threshold.
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 / 3 minor

Summary. The manuscript proves that if α, β > 0 satisfy 2α + β < 1, then there exist δ = δ(α, β) > 0 and Δ = Δ(α, β) > 0 such that any partial Latin square P of order n with k filled cells occupying at most αn rows and βn columns occurs in a uniform random Latin square of order n with probability between (δ/n)^k and (Δ/n)^k. The result is applied to show that the expected number of order-3 subsquares in a random Latin square of order n is Θ(1) as n → ∞, and to obtain the best-known asymptotics for the expected number of order-a subsquares when 2 < a = o(n^{1/2}).

Significance. If the central counting argument is correct, the theorem supplies uniform, n-independent constants that control embedding probabilities for sparse partial Latin squares. This immediately yields the first proof that E[number of 3×3 subsquares] is bounded away from both 0 and ∞, together with improved asymptotics for larger but still sub-square-root subsquares. The approach is combinatorial and avoids model-specific approximations, which strengthens its applicability to other configurations and to completion problems.

minor comments (3)
  1. [Abstract] Abstract, line on order-3 subsquares: the claim of 'the first proof' is strong; a brief parenthetical reference to the nearest prior upper or lower bounds would help readers assess novelty.
  2. The dependence of δ and Δ solely on α and β (and not on n or the particular symbol set) is stated in the theorem but could be reiterated once more explicitly in the statement of the main result.
  3. In the application to subsquares of order a, the range 2 < a = o(n^{1/2}) is given; it would be useful to note whether a must be integer or whether the argument extends verbatim to real a in that range.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, the assessment of its significance, and the recommendation for minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The derivation consists of a direct combinatorial counting argument that produces n-independent positive constants δ(α,β) and Δ(α,β) whenever 2α+β<1, then applies the resulting sandwich bound to obtain expectations for subsquares. No equations reduce a claimed prediction to a fitted input by construction, no load-bearing premise rests on a self-citation chain, and no ansatz or uniqueness theorem is smuggled in; the central claim is self-contained against the stated density threshold and the explicit counting procedure.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The paper introduces no free parameters, invented entities, or non-standard axioms. It operates entirely within the standard framework of Latin squares and uniform random models.

assumptions (1)
  • standard math Existence of Latin squares of every order n and the uniform probability space over all Latin squares of order n.
    These are background facts from the theory of Latin squares invoked to define the random model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Universal probability bounds for partial Latin squares." pith.science (2026). https://pith.science/paper/MU7YOBP2

@misc{pith2026260618174,
  author       = {Pith},
  title        = {Pith review of: Universal probability bounds for partial Latin squares},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MU7YOBP2}},
  note         = {Machine review of arXiv:2606.18174}
}
abstract

This paper studies the probability of substructures occurring in random Latin squares. Our main result states that if $\alpha,\beta>0$ are such that $2\alpha+\beta<1$, then there are positive constants $\delta = \delta(\alpha, \beta)$ and $\Delta = \Delta(\alpha, \beta)$ such that if $P$ is a partial Latin square of order $n$ with $k = k(n)$ non-empty cells occupying at most $\alpha n$ rows and $\beta n$ columns, the probability that a random Latin square of order $n$ contains $P$ lies between $(\delta/n)^k$ and $(\Delta/n)^k$. We apply this result to subsquares in random Latin squares to obtain the first proof of the fact that the expected number of subsquares of order $3$ in a random Latin square of order $n$ is non-vanishing as $n \to \infty$. We are also able to provide the best known asymptotics for the expected number of subsquares of order $a$ in a random Latin square of order $n$ when $2<a=o(n^{1/2})$. Finally, we discuss the implications of our result on other configurations in random Latin squares as well as on completions of partial Latin squares.

Figures

Figures reproduced from arXiv: 2606.18174 by the authors.

Figure 1
Figure 1. The highlighted entries in the Latin square L on the left form the row cycle ρ = ρL(2, 6, 1), which has length 4. The Latin square on the right is obtained from L by switching on ρ. Fact 2.1 (Reversibility of row cycle switches). Let L be a Latin square of order n and let {r, r′ , c} ⊆ [n] with r ≠ r ′ . If L is obtained from some Latin square L ′ by switching on ρL′(r, r′ , c), then L ′ is uniquely determined: it i… view at source ↗
Figure 2
Figure 2. An example of a row cycle ρL(r, r′ , c) (in blue/grey) before and after a switch along column cycle γL(c ′ , c′′, r) (in orange/grey) as in Lemma 2.3 (1) with m = 7, c ′ = c3 and c ′′ = c6. An example of the first situation (1) is shown in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. An example of a column cycle γL(c, c′ , r) (in blue/grey) before and after a switch along row cycle ρL(r ′ , r′′, c) (in orange/grey) as in Lemma 2.4 (2) with m = 4 and r ′ = r3. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: A partial row cycle ρL(r, r′ , c → c ′ ) with d ρ L (r, r′ , c → c ′ ) = 4. r r 0 c c 0 s y2 s 00 y7 r2 r3 r4 r5 r7 r8 y4 y5 y3 y4 y2 y3 y8 s y7 y8 y5 s 00 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: A partial column cycle γL(c, c′ , r → r ′ ) with d γ L (c, c′ , r → r ′ ) = 5. We will also need the analogous notion of a partial column cycle. Let {c, c′ } ⊆ [n] with c ≠ c ′ and let π γ c,c′ be the column permutation of L defined by these columns. Let r ∈ [n] and le…
Figure 6
Figure 6. Figure 6: The highlighted entries in the Latin square L on the left form the substruc￾ture ζ = ζL(c, c′ , r, r′ ). The Latin square on the right is obtained from L by switching on ζ. Let R be the set of rows other than r hit by γL(c, c′ , r → r ′ ) and let C be the set of column…
Figure 7
Figure 7. Figure 7: An example of a row cycle ρL(r4, r8, c) (in orange/grey) before and after a cross-switch on ζL(c, c′ , r, r′ ) (in blue/grey). 2.4. η-switching. We are now ready to define our final switching procedure, which we call η-switching. Let {r, r′ , c} ⊆ [n] with r ≠ r ′ . We…
Figure 8
Figure 8. Figure 8: Examples of the three types of η = ηL(r, r′ , c). Next, we define how to switch on the substructure η. Type One: To switch on η, we simply switch on the row cycle ρL(r, r′ , c). Type Two: To switch on η, we first switch on ρL(r ′ , r′′, c′ ) to create the intermediate …
Figure 9
Figure 9. Figure 9: The examples from [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 10
Figure 10. Figure 10: The highlighted entries in the Latin square L on the left form the substruc￾ture η = ηL(8, 3, 2), which is of Type Two. The Latin square on the right is obtained from L by switching on η. obtained by switching on ηL′(r, r′ , c). If ηL(r, r′ , c) is not of Type One, th…
Figure 11
Figure 11. Figure 11: An example of a Latin square L ∈ X3 ⊆ Y2. Here we have r0 = r, r1 = r ′ , c0 = c and s2 = s3 = s. The first claim in our proof is the following. Claim 1. For all 1 ⩽ j < n(1 − 2α − β)/3, pj−1 ⩽ npj + 1 n(1 + pj − 2α − β) − 3j − 2 . Proof of claim. We prove the claim u…
Figure 12
Figure 12. Figure 12: An example of a switch from the Latin square L ∈ X3 ⊆ Y2 from [PITH_FULL_IMAGE:figures/full_fig_p015_12.png]
Figure 13
Figure 13. Figure 13: The functions c(α) and c ′ (α) for 0 < α < 1/2. non-empty cells induce a Latin square of order a = αn, then this limit is equal to c(α) discussed above. Define P ′ to be the partial Latin square of order n defined by: ● P ′ [1, i] = i for all i ∈ [a], ● P ′ [i, 1] = i…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 3 canonical work pages

  1. [1]

    Latin subrectangles

    J. Allsop. “Latin subrectangles”. PhD thesis. Monash University, 2025

    2025

  2. [2]

    Subsquares in random Latin rectangles

    J. Allsop and I. M. Wanless. “Subsquares in random Latin rectangles”.Combinatorica45.3 (2025). Paper No. 29, 18pp

    2025

  3. [3]

    Almost every Latin square has a decomposition into transversals

    C. Bowtell and R. Montgomery. “Almost every Latin square has a decomposition into transversals”. arXiv:2501.05438(2025)

    work page arXiv 2025

  4. [4]

    The theory and application of Latin bitrades: a survey

    N. J. Cavenagh. “The theory and application of Latin bitrades: a survey”.Math. Slovaca58.6 (2008), pp. 691–718

    2008

  5. [5]

    The cycle structure of two rows in a random Latin square

    N. J. Cavenagh, C. Greenhill, and I. M. Wanless. “The cycle structure of two rows in a random Latin square”.Random Structures Algorithms33.3 (2008), pp. 286–309

    2008

  6. [6]

    Subsquares in Random Latin Squares and Rect- angles

    A. Divoux, T. Kelly, C. Kennedy, and J. Sidhu. “Subsquares in Random Latin Squares and Rect- angles”.J. Combin. Des.34.4 (2026), pp. 184–197

    2026

  7. [7]

    The completion of partial Latin squares

    D. Donovan. “The completion of partial Latin squares”.Australas. J. Combin.22 (2000), pp. 247– 264

    2000

  8. [8]

    Thresholds versus fractional expectation- thresholds

    K. Frankston, J. Kahn, B. Narayanan, and J. Park. “Thresholds versus fractional expectation- thresholds”.Ann. of Math. (2)194.2 (2021), pp. 475–495

    2021

Show all 29 references
  1. [9]

    Canonical labeling of Latin squares in average-case polynomial time

    M. J. Gill, A. Mammoliti, and I. M. Wanless. “Canonical labeling of Latin squares in average-case polynomial time”.Random Structures Algorithms66.4 (2025). Paper No. e70015, 23pp

    2025

  2. [10]

    Asymptotic enumeration of Latin rectangles

    C. D. Godsil and B. D. McKay. “Asymptotic enumeration of Latin rectangles”.J. Combin. Theory Ser. B48.1 (1990), pp. 19–44

    1990

  3. [11]

    Combinatorial estimates by the switching method

    M. Hasheminezhad and B. D. McKay. “Combinatorial estimates by the switching method”.Combi- natorics and graphs. Vol. 531. Contemp. Math. Amer. Math. Soc., Providence, RI, 2010, pp. 209– 221

    2010

  4. [12]

    Generating uniformly distributed random Latin squares

    M. T. Jacobson and P. Matthews. “Generating uniformly distributed random Latin squares”.J. Combin. Des.4.6 (1996), pp. 405–437. 35

    1996

  5. [13]

    OptimalthresholdsforLatinsquares,Steinertriplesystems,andedgecol- orings

    V.JainandH.T.Pham.“OptimalthresholdsforLatinsquares,Steinertriplesystems,andedgecol- orings”.Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 2024, pp. 1425–1436

    2024

  6. [14]

    Janson, T

    S. Janson, T. Łuczak, and A. Ruciński.Random graphs. Wiley-Interscience, 2000

    2000

  7. [15]

    Thresholds for Latin squares and Steiner triple systems: bounds within a logarithmic factor

    D. Y. Kang, T. Kelly, D. Kühn, A. Methuku, and D. Osthus. “Thresholds for Latin squares and Steiner triple systems: bounds within a logarithmic factor”.Trans. Amer. Math. Soc.376.9 (2023), pp. 6623–6662

    2023

  8. [16]

    The optimal edge-colouring threshold

    P. Keevash. “The optimal edge-colouring threshold”.arXiv:2212.04397(2022)

    2022

  9. [17]

    Nibble Methods in Graph Theory

    T. Kelly. “Nibble Methods in Graph Theory.” In Topics in Probabilistic Graph Theory, edited by R. J. Wilson, L. W. Beineke, and C. McDiarmid. Cambridge University Press. Forthcoming

  10. [18]

    Almost all Steiner triple systems have perfect matchings

    M. Kwan. “Almost all Steiner triple systems have perfect matchings”.Proc. Lond. Math. Soc. (3) 121.6 (2020), pp. 1468–1495

    2020

  11. [19]

    Parities in random Latin squares

    M. Kwan, K. Petrova, and M. Sawhney. “Parities in random Latin squares”.arXiv:2509.13125 (2025)

    2025

  12. [20]

    Large deviations in random Latin squares

    M. Kwan, A. Sah, and M. Sawhney. “Large deviations in random Latin squares”.Bull. Lond. Math. Soc.54.4 (2022), pp. 1420–1438

    2022

  13. [21]

    Substructures in Latin squares

    M. Kwan, A. Sah, M. Sawhney, and M. Simkin. “Substructures in Latin squares”.Israel J. Math. 256.2 (2023), pp. 363–416

    2023

  14. [22]

    Intercalates and discrepancy in random Latin squares

    M. Kwan and B. Sudakov. “Intercalates and discrepancy in random Latin squares”.Random Struc- tures Algorithms52.2 (2018), pp. 181–196

    2018

  15. [23]

    J. H. van Lint and R. M. Wilson.A course in combinatorics. Second. Cambridge University Press, Cambridge, 2001, pp. xiv+602

    2001

  16. [24]

    OnthethresholdproblemforLatinboxes

    Z.LuriaandM.Simkin.“OnthethresholdproblemforLatinboxes”.Random Structures Algorithms 55.4 (2019), pp. 926–949

    2019

  17. [25]

    Most Latin squares have many subsquares

    B. D. McKay and I. M. Wanless. “Most Latin squares have many subsquares”.J. Combin. Theory Ser. A86.2 (1999), pp. 322–347

    1999

  18. [26]

    Mappings of Latin squares

    A. O. Pittenger. “Mappings of Latin squares”.Linear Algebra Appl.261 (1997), pp. 251–268

    1997

  19. [27]

    A combinatorial theorem with an application to Latin rectangles

    H. J. Ryser. “A combinatorial theorem with an application to Latin rectangles”.Proc. Amer. Math. Soc.2.4 (1951), pp. 550–552

    1951

  20. [28]

    Threshold for Steiner triple systems

    A. Sah, M. Sawhney, and M. Simkin. “Threshold for Steiner triple systems”.Geom. Funct. Anal. 33.4 (2023), pp. 1141–1172

    2023

  21. [29]

    Cycle switches in Latin squares

    I. M. Wanless. “Cycle switches in Latin squares”.Graphs Combin.20.4 (2004), pp. 545–570. (J. Allsop)Institut für Mathematik, Freie Universität Berlin, Germany Email address:allsop@mi.fu-berlin.de (P. Morris)Departament de Matemàtiques, Universitat Politècnica de Catalunya (UPC...

    2004

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.