On the completion of $\epsilon$-dense partial Latin squares

Shikang Yu; Tao Feng

arxiv: 2606.31143 · v1 · pith:TDZQU6ETnew · submitted 2026-06-30 · 🧮 math.CO

On the completion of ε-dense partial Latin squares

Shikang Yu , Tao Feng This is my paper

Pith reviewed 2026-07-01 05:09 UTC · model grok-4.3

classification 🧮 math.CO

keywords partial Latin squarescompletabledense partial Latin squarestriangle decompositiontripartite graphsLatin squares

0 comments

The pith

For all large n, every 2/25-dense partial Latin square of order n can be completed.

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

The paper proves that for all sufficiently large n, any partial Latin square of order n is completable whenever each row, column, and symbol appears in at most 2n/25 filled cells. This bound improves on earlier results and moves toward the conjecture that the same holds at density 1/4. The argument reduces the completion task to the existence of fractional triangle decompositions in balanced tripartite graphs whose minimum degree is slightly below 23n/25. Establishing a positive η for which the degree condition guarantees such a decomposition then yields the Latin-square result.

Core claim

For all sufficiently large integers n, every 2/25-dense partial Latin square of order n is completable. The proof is obtained by establishing that there exists an η > 0 such that every triangle-divisible balanced tripartite graph on 3n vertices with partite minimum degree at least (23/25 − η)n admits a fractional triangle decomposition.

What carries the argument

Reduction of Latin-square completion to the existence of fractional triangle decompositions in balanced tripartite graphs with minimum degree (23/25 − η)n.

If this is right

Completing a 2/25-dense partial Latin square reduces directly to finding a fractional triangle decomposition in an associated tripartite graph.
The same graph-theoretic statement immediately implies completability for all densities below 2/25.
Any improvement in the allowable η would raise the density threshold for which completion is guaranteed.
The tripartite decomposition result applies uniformly once n exceeds some fixed threshold.

Where Pith is reading between the lines

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

The same reduction technique might extend to other Latin-square variants such as Latin rectangles or orthogonal arrays.
Computational checks of the graph condition for moderate n could indicate how far the density bound can be pushed before a counterexample appears.
If the fractional decomposition threshold can be lowered further, the original 1/4 conjecture would become reachable by the same method.

Load-bearing premise

There exists some η > 0 making every sufficiently dense, triangle-divisible balanced tripartite graph admit a fractional triangle decomposition.

What would settle it

A single 2/25-dense partial Latin square of some large order that cannot be completed would falsify the claim.

read the original abstract

A partial Latin square of order $n$ is called $\epsilon$-dense if each row and each column contains at most $\epsilon n$ filled cells, and each symbol occurs at most $\epsilon n$ times. A partial Latin square is said to be completable if its empty cells can be filled to obtain a Latin square. Daykin and H\"{a}ggkvist conjectured that every $\frac{1}{4}$-dense partial Latin square is completable. In this paper, we show that for all sufficiently large integers $n$, every $\frac{2}{25}$-dense partial Latin square of order $n$ is completable. The proof is obtained by establishing that there exists an $\eta > 0$ such that every triangle-divisible balanced tripartite graph on $3n$ vertices with partite minimum degree at least $(\frac{23}{25}-\eta)n$ admits a fractional triangle decomposition.

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.

Desk Editor's Note private letter to a colleague

The paper improves the explicit threshold for completable partial Latin squares to 2/25 density for large n by reducing the problem to a fractional triangle decomposition in tripartite graphs.

read the letter

The main point is that for all large enough n, any partial Latin square where each row, column, and symbol has at most 2/25 n entries filled can be completed to a full Latin square. The authors reach this by showing the corresponding balanced tripartite graph on 3n vertices with minimum degree at least (23/25 - η)n has a fractional triangle decomposition whenever it is triangle-divisible.

The reduction itself is clean. The density bound on the partial Latin square maps straight to the degree condition, and triangle-divisibility holds automatically from the Latin square axioms, so no extra hypotheses are needed. This is a direct application of graph decomposition methods to the completion question, and it produces a concrete constant that improves on earlier explicit results even if it remains below the 1/4 target in the Daykin-Häggkvist conjecture.

The supporting lemma on fractional decompositions is the actual new piece. If that lemma holds with the stated parameters, the Latin square claim follows without circularity or mismatched constants.

The obvious limitation is that the soundness of the whole argument depends on the details of the decomposition proof, which the abstract only outlines. Any looseness in how they obtain the fractional packing or in the choice of η would cap how far the bound can be pushed. That part needs careful checking.

This is a paper for people already working on Latin squares or on triangle decompositions in multipartite graphs. A reader tracking progress toward the conjecture will get a usable new threshold and a clear reduction to check against. It has enough structure and a precise claim to merit sending out for peer review rather than a desk rejection.

Referee Report

0 major / 2 minor

Summary. The paper claims that for all sufficiently large integers n, every 2/25-dense partial Latin square of order n is completable. The proof proceeds by reducing the problem to the existence of a fractional triangle decomposition in a balanced tripartite graph on 3n vertices that is triangle-divisible and has partite minimum degree at least (23/25 - η)n for some η > 0.

Significance. If the central reduction and the supporting fractional decomposition result hold, the work improves the known density threshold for completability of partial Latin squares from prior bounds toward the Daykin-Häggkvist conjecture (which posits the threshold 1/4). The approach leverages standard tools from extremal graph theory and design theory, and the explicit mapping from the Latin-square density parameter 2/25 to the graph degree threshold 23/25 is a clear strength.

minor comments (2)

[Abstract] The abstract states the reduction but does not indicate where in the manuscript the fractional triangle decomposition theorem is proved; adding a brief outline of the sections would improve readability.
The manuscript should include a short comparison paragraph situating the 2/25 result against earlier partial results on the conjecture, even if only citing the relevant literature.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending minor revision. No specific major comments were provided in the report, so we have no points requiring point-by-point rebuttal at this stage. We will incorporate any minor editorial suggestions in the revised version.

Circularity Check

0 steps flagged

No significant circularity; reduction to independent graph problem

full rationale

The paper's central claim reduces the ε-dense partial Latin square completion problem to proving an auxiliary statement on fractional triangle decompositions in balanced tripartite graphs with minimum degree (23/25 − η)n. This graph-theoretic result is presented as independently established, with the 2/25 density threshold mapping directly onto the degree condition and triangle-divisibility inherited automatically from the Latin square structure. No self-definitional steps, fitted parameters renamed as predictions, load-bearing self-citations, uniqueness theorems imported from the authors' prior work, or ansatzes smuggled via citation appear in the provided abstract or derivation outline. The chain is self-contained and does not reduce any claimed prediction to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard mathematical axioms in graph theory and combinatorics, with the new contribution being the specific density bound and the existence of η for the decomposition.

axioms (2)

standard math Definitions and basic properties of partial Latin squares and Latin squares
The paper uses standard combinatorial objects.
standard math Properties of balanced tripartite graphs and triangle divisibility
Invoked in the graph theoretic reformulation.

pith-pipeline@v0.9.1-grok · 5682 in / 1294 out tokens · 51959 ms · 2026-07-01T05:09:50.636273+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 2 canonical work pages · 1 internal anchor

[1]

Anderson and A.J.W

L.D. Anderson and A.J.W. Hilton, Thank Evans!, Proc. Lond. Math. Soc., 47 (1983), 507– 522

1983
[2]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, D. Osthus and A. Taylor, Clique decompositions of multipartite graphs and completion of Latin squares, J. Comb. Theory, Ser. A, 151 (2017), 146–201

2017
[3]

Bartlett, Completions ofϵ-dense partial Latin squares, J

P. Bartlett, Completions ofϵ-dense partial Latin squares, J. Comb. Des., 21 (2013), 447–463

2013
[4]

Bowditch and P

F. Bowditch and P. Dukes, Fractional triangle decompositions of dense 3-partite graphs, J. Comb., 10 (2019), 255–282

2019
[5]

Chetwynd and R

A.G. Chetwynd and R. H¨ aggkvist, Completing partialn×nLatin squares where each row, column and symbol is used at mostcntimes, Reports, Dept. of Mathematics, University of Stockholm, 1985. 15

1985
[6]

Daykin and R

D.E. Daykin and R. H¨ aggkvist, Completion of sparse partial Latin squares, Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, 1984, 127–132

1983
[7]

Delcourt and L

M. Delcourt and L. Postle, A proof of Nash-Williams’ conjecture, arXiv:2026.11178, 2026

work page arXiv 2026
[8]

Evans, Embedding incomplete Latin rectangles, Amer

T. Evans, Embedding incomplete Latin rectangles, Amer. Math. Monthly, 67 (1960), 958– 961

1960
[9]

T. Feng, H. Liu and S. Yu, Fractional clique decompositions of dense balanced multipartite graphs, arXiv:2604.25206v2, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[10]

Gustavsson, Decompositions of large graphs and digraphs with high minimum degree, Doctoral Dissertation, University of Stockholm, 1991

T. Gustavsson, Decompositions of large graphs and digraphs with high minimum degree, Doctoral Dissertation, University of Stockholm, 1991

1991
[11]

Hall, An existence theorem for Latin squares, Bull

M. Hall, An existence theorem for Latin squares, Bull. Amer. Math. Soc., 51 (1945), 387–388

1945
[12]

Haxell and V

P.E. Haxell and V. R¨ odl, Integer and fractional packings in dense graphs, Combinatorica, 21 (2001), 13–38

2001
[13]

Montgomery, Fractional clique decompositions of dense partite graphs, Comb

R. Montgomery, Fractional clique decompositions of dense partite graphs, Comb. Probab. Comput., 26 (2017), 911–943

2017
[14]

Ryser, A combinatorial theorem with an application to Latin rectangles, Proc

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

1951
[15]

Smetianuk, A new construction on Latin squares I

B. Smetianuk, A new construction on Latin squares I. A proof of the Evans conjecture, Ars Comb., 11 (1981), 155–172

1981
[16]

Wanless, A generalisation of transversals for Latin squares, Electron

I.M. Wanless, A generalisation of transversals for Latin squares, Electron. J. Comb., 9 (2002), #R12. 16

2002

[1] [1]

Anderson and A.J.W

L.D. Anderson and A.J.W. Hilton, Thank Evans!, Proc. Lond. Math. Soc., 47 (1983), 507– 522

1983

[2] [2]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, D. Osthus and A. Taylor, Clique decompositions of multipartite graphs and completion of Latin squares, J. Comb. Theory, Ser. A, 151 (2017), 146–201

2017

[3] [3]

Bartlett, Completions ofϵ-dense partial Latin squares, J

P. Bartlett, Completions ofϵ-dense partial Latin squares, J. Comb. Des., 21 (2013), 447–463

2013

[4] [4]

Bowditch and P

F. Bowditch and P. Dukes, Fractional triangle decompositions of dense 3-partite graphs, J. Comb., 10 (2019), 255–282

2019

[5] [5]

Chetwynd and R

A.G. Chetwynd and R. H¨ aggkvist, Completing partialn×nLatin squares where each row, column and symbol is used at mostcntimes, Reports, Dept. of Mathematics, University of Stockholm, 1985. 15

1985

[6] [6]

Daykin and R

D.E. Daykin and R. H¨ aggkvist, Completion of sparse partial Latin squares, Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, 1984, 127–132

1983

[7] [7]

Delcourt and L

M. Delcourt and L. Postle, A proof of Nash-Williams’ conjecture, arXiv:2026.11178, 2026

work page arXiv 2026

[8] [8]

Evans, Embedding incomplete Latin rectangles, Amer

T. Evans, Embedding incomplete Latin rectangles, Amer. Math. Monthly, 67 (1960), 958– 961

1960

[9] [9]

T. Feng, H. Liu and S. Yu, Fractional clique decompositions of dense balanced multipartite graphs, arXiv:2604.25206v2, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026

[10] [10]

Gustavsson, Decompositions of large graphs and digraphs with high minimum degree, Doctoral Dissertation, University of Stockholm, 1991

T. Gustavsson, Decompositions of large graphs and digraphs with high minimum degree, Doctoral Dissertation, University of Stockholm, 1991

1991

[11] [11]

Hall, An existence theorem for Latin squares, Bull

M. Hall, An existence theorem for Latin squares, Bull. Amer. Math. Soc., 51 (1945), 387–388

1945

[12] [12]

Haxell and V

P.E. Haxell and V. R¨ odl, Integer and fractional packings in dense graphs, Combinatorica, 21 (2001), 13–38

2001

[13] [13]

Montgomery, Fractional clique decompositions of dense partite graphs, Comb

R. Montgomery, Fractional clique decompositions of dense partite graphs, Comb. Probab. Comput., 26 (2017), 911–943

2017

[14] [14]

Ryser, A combinatorial theorem with an application to Latin rectangles, Proc

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

1951

[15] [15]

Smetianuk, A new construction on Latin squares I

B. Smetianuk, A new construction on Latin squares I. A proof of the Evans conjecture, Ars Comb., 11 (1981), 155–172

1981

[16] [16]

Wanless, A generalisation of transversals for Latin squares, Electron

I.M. Wanless, A generalisation of transversals for Latin squares, Electron. J. Comb., 9 (2002), #R12. 16

2002