An improved minimum degree threshold for fractional clique decompositions in partite graphs
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "An improved minimum degree threshold for fractional clique decompositions in partite graphs".
Emmy: Here's the gist of the paper. An improved minimum degree threshold for fractional clique decompositions in partite graphs proves that every sufficiently large r-partite graph with n vertices in each part and partite minimum degree at least (1−1/30r 2)n admits a fractional Kr-decomposition, which implies the same upper bound on the asymptotic minimum degree threshold for r-partite graphs to admit a Kr-decomposition The paper defines several parameters related to graph decompositions, specifically focusing on the minimum degree required for a graph to admit a fractional Kr-decomposition, denoted as δKr(n) and its asymptotic limit δKr The fractional Kr-decomposition is defined by a function ω: Kr(G) → R≥0 satisfying X K∈Kr(G):e∈E(K) ω(K) = 1 for every e ∈ E(G).
Ada: The asymptotic fractional Kr-decomposition threshold is defined as δ∗Kr = lim sup n→∞ δ∗Kr(n).
Emmy: Defining the Partite Setting The research shifts to the partite setting, where G is an r-partite graph with vertex partition V1 ∪ · · · ∪ Vr.
Ada: A balanced graph has equal part sizes, and its partite minimum degree is defined as ˆδ(G) = min i̸=j min v∈Vi degj(v).
Title and authors: Ada: Let's talk about who wrote this. The authors are Sean Longbrake, Michael Simkin, and Liana Yepremyan, with Michael Zheng as well on the team. They are clearly specialists in the intersection of extremal combinatorics and graph decomposition problems.
Emmy: I see them focusing on partite graphs specifically because that structure adds a layer of complexity—the vertex sets are partitioned into r distinct groups. It’s not just any graph; it’s one with this specific, highly structured layout.
Kolya: From a probabilistic viewpoint, I'm interested in how they handle the structure imposed by those partite constraints when you move into the fractional setting. Are we talking about bounds that hold for typical graphs or just very dense ones?
Ada: They are looking at sufficiently large graphs, which is standard for asymptotic results. The paper establishes a Dirac-type condition for an r-partite graph to admit a fractional clique decomposition: every sufficiently large r-partite graph with n vertices in each part and partite minimum degree at least one minus one over three times r squared n admits a fractional Kr-decomposition, subject to necessary divisibility conditions.
Emmy: That specific degree bound, one minus one over three times r squared n, is the core of the result they are highlighting. It’s a concrete number that dictates how dense the graph needs to be for this decomposition to exist in the fractional sense.
Kolya: So if we think about this in terms of what it means for random graphs, does this threshold suggest something about when random structures will exhibit these decompositions? I mean, what kind of tail behavior are we seeing here?
Ada: The paper implies that this bound holds even under the divisibility conditions which are crucial for the structure to work out properly. They are showing that if those structural constraints on how edges connect between parts aren't too bad, this degree requirement is enough.
Emmy: It’s about ensuring that for every vertex in one part, its connections to all other parts are balanced enough relative to the total number of vertices in each part. That balance is what allows the fractional weighting process to work out without any cliques being left empty or over-weighted in a way that breaks the decomposition.
Kolya: And those divisibility conditions are where I think things get tricky, because they link the local degree requirements across different parts together. Does the paper give an example of a graph that barely misses this threshold?
The paper's summary: Ada: This section boils down to what they actually proved. They defined several parameters, including delta Kr n and its asymptotic limit delta Star Kr, and they showed these two are equal, which is a significant structural finding. They then established that for r greater than three, there exists some constant c greater than one such that there are infinitely many Kr-divisible graphs with minimum degree at least one minus one over c times r plus one n and no fractional Kr-decomposition.
Emmy: So they're essentially saying that the asymptotic fractional Kr-decomposition threshold for the partite setting is equal to the general asymptotic threshold, delta Star Kr equals delta Kr. That connects two different ways of looking at the decomposition problem.
Kolya: The summary also touches on how they build a fractional decomposition using an explicit limiting process. They start with an initial weighting, then adjust vertices and edges iteratively until they reach the final desired fractional decomposition. It sounds like a constructive approach to proving existence.
Ada: That's right, it's not just a non-existence result; it shows *how* to construct one when the degree is high enough. The process involves two phases: first, adjusting vertices to get a vertex-balanced weighting, and then refining the edge weights based on cycles of length four between two parts paired with a Kr minus two clique.
Emmy: That iterative refinement sounds like it’s using local information—like small cycles—to nudge the weights in the right direction towards zero discrepancy. It’s a very localized way to handle global structure problems.
Kolya: I wonder about those cycle adjustments, especially with kr minus two cliques involved. What does that specific geometric relationship tell us about the necessary constraints on the graph's local topology? Does it simplify things substantially?
Ada: It simplifies the analysis by providing a mechanism to control the edge discrepancy. The initial edge discrepancy is bounded by something involving n minus one over two times epsilon n squared, and they show subsequent edge adjustments can reduce this maximum error by a factor of epsilon, leading to the desired limit weighting omega infinity.
The paper's improvements: Ada: The main improvement here is in tightening the upper bound for the asymptotic fractional Kr-decomposition threshold. Previously, Montgomery had an upper bound of one minus one over one hundred times r <ref:2611.08432#pg2>. This paper improves that to one minus one over thirty times r squared n.
Emmy: That’s a significant shift because it increases the order of magnitude of the deficit from something related to r minus three to something related to r minus two in the partite setting. It's a more precise statement about how much density you need.
Kolya: So, what does this mean for those who are studying these thresholds? If we want to guarantee a decomposition for a given graph structure, this new bound gives us a better target for how dense that structure needs to be.
Ada: It means the minimum degree deficit required is now of order r minus two instead of r minus three. This is more stringent because it requires the graph to be denser relative to those constraints. They show that for r greater than three, there exist infinitely many Kr-divisible graphs with minimum degree at least one minus one over c times r plus one n and no fractional Kr-decomposition.
Emmy: The construction of those counterexamples is what makes this result so powerful; it shows that the previous, weaker bounds were not tight. This new bound is the best upper bound for general r prior to this work, which was by Montgomery at one minus one over one hundred times r <ref:2611.08432#pg2>.
Kolya: I'm curious about the mechanism behind why they can prove this improved bound. Is it because of some specific property of fractional decompositions that we are overlooking?
Ada: The proof relies on showing that the final weighting, omega infinity, is non-negative for every r clique R. They use specific tools like Corollary four point nine and Lemma five point one eight and Lemma five point one six to establish this non-negativity for any r greater than three, provided alpha is thirty and beta is ten <ref:2611.08432#pg1>.
Conclusion: Ada: To wrap up, the paper "An improved minimum degree threshold for fractional clique decompositions in partite graphs" shows that we can prove a Dirac-type condition for an r-partite graph to admit a fractional clique decomposition. They establish that every sufficiently large r-partite graph with n vertices in each part and partite minimum degree at least one minus one over three times r squared n admits a fractional Kr-decomposition, subject to necessary divisibility conditions.
Emmy: And they confirm that this result sets the asymptotic minimum degree threshold for these graphs equal to the general threshold, delta Star Kr equals delta Kr. They also show how to construct a fractional decomposition through an explicit limiting process involving vertex and edge adjustments guided by cycle information.
Kolya: I’m just interested in the implication for applications—if we need these decompositions in something real, like network design or scheduling, what does this threshold tell us about the practical minimum requirements? Does this mean we can actually use these bounds to build something useful?
Ada: It tells us that for dense multipartite structures, if you meet that degree requirement of one minus one over three times r squared n, you have a solid mathematical guarantee of finding a fractional Kr-decomposition. That's the practical takeaway.
Emmy: And the fact that they managed to push Montgomery’s upper bound down to one minus one over thirty times r squared n is important for understanding the fundamental limits of these decomposition problems in multipartite settings.
Kolya: So, ultimately, this paper gives us a better density requirement and a clearer constructive path for these fractional decompositions in graphs with multiple parts.
Ada: Exactly. We're talking about more precise bounds on how dense these structures must be to guarantee the existence of these fractional decompositions in partite settings. That’s what this paper is all about.
Sean Longbrake, Michael Simkin, Liana Yepremyan, Michael Zheng
Department of Mathematics, Emory University · Hebrew University of Jerusalem
math.CO
Submitted: 2026-11-05
Updated: 2026-11-05
Comments: 33 pages, 2 figures
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Importance score: 72/100
The gist: An improved minimum degree threshold for fractional clique decompositions in partite graphs proves that every sufficiently large r-partite graph with n vertices in each part and partite minimum…
Key concepts
- Fractional Kr-decomposition
- This is a mathematical function that assigns non-negative weights ($\omega$) to cliques in a graph such that every edge belongs to at least one clique with a total weight of 1. It is used to show if the graph can be covered by cliques in a fractional sense.
- Partite Setting
- This refers to graphs where the vertices are divided into $r$ distinct sets (parts), $V_1, V_2, \dots, V_r$. The specific condition for Kr-divisibility means that every vertex in any part has the same degree to vertices in every other part.
- Asymptotic Threshold ($\delta^*Kr$)
- This is the limit of the minimum degree required for a graph to admit a fractional Kr-decomposition as the number of vertices ($n$) grows infinitely large. The paper focuses on finding this sharp threshold, showing it is equal to $\delta_{Kr}$ in this partite setting.
- Minimum Degree Threshold ($\hat{\delta}Kr$)
- This is the specific minimum degree required for an r-partite graph to guarantee the existence of a fractional Kr-decomposition. The paper establishes that this threshold is bounded by $1 - 1/30r^2$, which is a significant improvement over prior bounds.
Terminology
Summary
An improved minimum degree threshold for fractional clique decompositions in partite graphs proves that every sufficiently large r-partite graph with n vertices in each part and partite minimum degree at least (1−1/30r 2)n admits a fractional Kr-decomposition, which implies the same upper bound on the asymptotic minimum degree threshold for r-partite graphs to admit a Kr-decomposition
Introduction to Thresholds
The paper defines several parameters related to graph decompositions, specifically focusing on the minimum degree required for a graph to admit a fractional Kr-decomposition, denoted as δKr(n) and its asymptotic limit δKr The fractional Kr-decomposition is defined by a function ω: Kr(G) → R≥0 satisfying X K∈Kr(G):e∈E(K) ω(K) = 1 for every e ∈ E(G). The asymptotic fractional Kr-decomposition threshold is defined as δ∗Kr = lim sup n→∞ δ∗Kr(n). p. 2 The asymptotic r-partite
Kr-decomposition threshold is then defined as ˆδKr = lim sup
n→∞
ˆδKr
(n). Let ˆδ
∗
Kr
(n) be the least δ > 0 such that every balanced, Kr-divisible, r-partite graph G with n
vertices in each part and ˆδ(G) ≥ δn admits a fractional Kr-decomposition. The asymptotic r-partite
Kr-decomposition threshold is then defined as ˆδKr = lim sup
n→∞
ˆδKr
(n). Let ˆδ
∗
Kr
(n) be the least δ > 0 such that every balanced, Kr-divisible, r-partite graph G with n
vertices in each part and ˆδ(G) ≥ δn admits a fractional Kr-decomposition.Where the paper says it
Where the paper says it
Defining the Partite Setting
The research shifts to the partite setting, where G is an r-partite graph with vertex partition V1 ∪ · · · ∪ Vr. A balanced graph has equal part sizes, and its partite minimum degree is defined as ˆδ(G) = min i̸=j min v∈Vi degj(v). p. 1 We call G balanced if |V1| =
· · · = |Vr|, and define its partite minimum degree by
ˆδ(G) = min
i̸=j
min
v∈Vi
degj
(v)
where degj
(v) := |N(v) ∩ Vj |. 1
In addition to equal part sizes, the partite setting has a local bal1One could also consider our problem in a more general partite setting. Following Montgomery [21] and with slight abuse of wording, we say that G is Kr-divisible if
degj
(v) = degk
(v) for all distinct i, j, k ∈ [r] and every v ∈ Vi
. (1)
Throughout the partite setting, Kr-divisibility refers to (1). Let ˆδKr
(n) be the least δ > 0 such that every Kr-divisible r-partite graph G
with n vertices in each part and ˆδ(G) ≥ δn admits a Kr-decomposition. The asymptotic r-partite
Kr-decomposition threshold is then defined as ˆδKr = lim sup
n→∞
ˆδKr
(n).Where the paper says it
Where the paper says it
Where the paper says it
Improving the Upper Bound
The paper establishes that the asymptotic fractional Kr-decomposition threshold in the partite setting is equal to the asymptotic Kr-decomposition threshold, i.e., δKr = δ∗Kr. p. 0 The question then is to find the right minimum degree lower bound which
guarantees that every Kr-divisible graph with that minimum degree admits a Kr-decomposition. Formally, let δKr
(n) be the least δ > 0 such that every Kr-divisible graph G with n vertices and
δ(G) ≥ δn has a Kr-decomposition. The conjecture said
that every sufficiently large Kr-divisible graph G with δ(G) ≥ (1 −
1
r+1 )n has a Kr-decomposition. The results in [10] disproved this conjecture in the stronger setting by showing that for every r ≥ 4,
there exists some c > 1 such that there exist infinitely many Kr-divisible graphs G with minimum
degree at least
1 −
1
c(r+1)
n and no fractional Kr-decomposition. Consequently,
ˆδ
∗
Kr ≥ δ
∗
Kr > 1 −
1
r + 1
for every r ≥ 4. The best upper bound for general r prior to our work was by Montgomery [21] who showed that,
for every integer r ≥ 3,
ˆδ
∗
Kr ≤ 1 −
1
106r
3 . The best upper bound for general r prior to our work was by Montgomery [21] who showed that,
for every integer r ≥ 3,
ˆδ
∗
Kr ≤ 1 −
1
106r
3 . Our main result improves Montgomery’s upper bound to
ˆδ
∗
Kr ≤ 1 −
1
30r
2 , increasing the minimum degree deficit from order r
−3
to order r
−2
in the partite
setting. The best upper bound for general r prior to our work was by Montgomery [21] who showed that,
for every integer r ≥ 3,
ˆδ
∗
Kr ≤ 1 −
1
106r
3 . Our main result improves Montgomery’s upper bound to
ˆδ
∗
Kr ≤ 1 −
1
30r
2 , increasing the minimum degree deficit from order r
−3
to order r
−2
in the partite
setting.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The Proof Strategy
The proof sketch involves building a fractional Kr-decomposition for G via an explicit limiting process starting from an initial weighting ωinit. This process involves two main phases: Phase 1, which is vertex adjustment to achieve a vertex-balanced weighting ω0, and Phase 2, which is edge adjustment to refine the weights iteratively towards the desired fractional decomposition. p. 4 For that, we will use vertex-adjusters which only change the weights of two specified vertices in
some part so that the weight is “moved” from one to the other, see Figure 1; in particular, the total
amount of weight remains unchanged. Let us call the weighting that we find after vertex adjustment
ω0. For that, we will use vertex-adjusters which only change the weights of two specified vertices in
some part so that the weight is “moved” from one to the other, see Figure 1; in particular, the total
amount of weight remains unchanged. Let us call the weighting that we find after vertex adjustment
ω0. (3)
Thus, if we were to take the limit of these weightings, we obtain a weighting ω∞ of G where the
weight of every edge is exactly kr(G)/e[(G). To build this sequence, we will make use of edge-adjusters, whose supports are made of cycles
of length four between two parts paired with a Kr−2 such that any edge of the cycle induces a Kr
with the Kr−2, see Figure 2.Where the paper says it
Where the paper says it
Where the paper says it
Bounding Discrepancies and Adjustments
The initial edge-discrepancy δinit(e) is bounded by kr(e) − kr(G)/e[(G) ≤ 2(r − 2)εnr−2. The vertex-discrepancy δvert(v) is bounded by δvert(v) ≤ 2ε(r − 2)n/r−1. p. 8 2 Bounding initial discrepancies
Before getting into vertex adjustment in Section 4, we first make some observations about how far
away the constant weighting ωinit is from being a fractional Kr-decomposition. To make this formal,
we will consider the edge-discrepancies of ωinit, denoted δinit, and the vertex-discrepancy δvert. So in the first step, we aim towards
the necessary condition by adjusting our initial weighting ωinit to one that satisfies this property. For that, we will use vertex-adjusters which only change the weights of two specified vertices in
some part so that the weight is “moved” from one to the other, see Figure 1; in particular, the total
amount of weight remains unchanged. This shows that the maximum discrepancy drops by
about a factor of ε, in particular that it goes to zero as i → ∞. Vi Vj V \ (Vi ∪ Vj )
e
−
−
Kr−2
+
+ −
−
+
+
⇝ Kr−2
e
Figure 2: Edge-adjuster for an edge e ∈ E(Vi
, Vj )
It then suffices to show that ωi(K) is at least zero for every clique K and index i.Where the paper says it
Where the paper says it
Where the paper says it
Conclusion and Final Bound
The final step involves showing that ω∞ is non-negative for every r-clique R. p. 0 After much progress in the last half a century [18, 25, 3, 16, 13, 14, 11], Delcourt and Postle [12]
recently proved this conjecture. A central ingredient is their resolution of its fractional relaxation:
every graph with minimum degree at least 3n/4 admits a non-negative weighting of its triangles in
which the total weight on each edge is one. and one-by-one splitting Vi
into (Vi∩(N(e)∩N(f))) and (Vi∩(N(e)
c∪N(f)
c
)). Using the fact that
deg( \v) ≥ (1 − ε)n for any v ∈ V (G), we obtain bounds of order O(εrnr−2
), see again Corollary 4. and one-by-one splitting Vi
into (Vi∩(N(e)∩N(f))) and (Vi∩(N(e)
c∪N(f)
c
)). Using the fact that
deg( \v) ≥ (1 − ε)n for any v ∈ V (G), we obtain bounds of order O(εrnr−2
), see again Corollary 4. A balanced, r-partite, Kr-divisible graph G is (ε, r)-minimal if ˆδ(G) = (1 − ε)n
and for every K ∈ Kr(G),
min
v∈V (K)
deg( \v) = (1 − ε)n. The next lemma justifies why it will be sufficient to only consider (ε, r)-minimal G for our
algorithm where from now on, we will additionally assume that ε = α
−1
r
−2
. A balanced, r-partite, Kr-divisible graph G is (ε, r)-minimal if ˆδ(G) = (1 − ε)n
and for every K ∈ Kr(G),
min
v∈V (K)
deg( \v) = (1 − ε)n. The next lemma justifies why it will be sufficient to only consider (ε, r)-minimal G for our
algorithm where from now on, we will additionally assume that ε = α
−1
r
−2
. A balanced, r-partite, Kr-divisible graph G is (ε, r)-minimal if ˆδ(G) = (1 − ε)n
and for every K ∈ Kr(G),
min
v∈V (K)
deg( \v) = (1 − ε)n. The next lemma justifies why it will be sufficient to only consider (ε, r)-minimal G for our
algorithm where from now on, we will additionally assume that ε = α
−1
r
−2
. A balanced, r-partite, Kr-divisible graph G is (ε, r)-minimal if ˆδ(G) = (1 − ε)n
and for every K ∈ Kr(G),
min
v∈V (K)
deg( \v) = (1 − ε)n. The next lemma justifies why it will be sufficient to only consider (ε, r)-minimal G for our
algorithm where from now on, we will additionally assume that ε = α
−1
r
−2
. An improved minimum degree threshold for fractional clique
decompositions in partite graphs
Sean Longbrake∗ Michael Simkin† Liana Yepremyan∗ Michael Zheng∗
November 5, 2026
Abstract
We prove a Dirac-type condition for an r-partite graph to admit a fractional clique decomposition: every sufficiently large r-partite graph with n vertices in each part and partite minimum
degree at least (1−
1
30r
2 )n admits a fractional Kr-decomposition, subject to necessary divisibility
conditions. This implies the same upper bound on the asymptotic minimum degree threshold
for r-partite graphs to admit a Kr-decomposition, using a well-known reduction. An improved minimum degree threshold for fractional clique
decompositions in partite graphs
Sean Longbrake∗ Michael Simkin† Liana Yepremyan∗ Michael Zheng∗
November 5, 2026
Abstract
We prove a Dirac-type condition for an r-partite graph to admit a fractional clique decomposition: every sufficiently large r-partite graph with n vertices in each part and partite minimum
degree at least (1−
1
30r
2 )n admits a fractional Kr-decomposition, subject to necessary divisibility
conditions. This implies the same upper bound on the asymptotic minimum degree threshold
for r-partite graphs to admit a Kr-decomposition, using a well-known reduction. An improved minimum degree threshold for fractional clique
decompositions in partite graphs
Sean Longbrake∗ Michael Simkin† Liana Yepremyan∗ Michael Zheng∗
November 5, 2026
Abstract
We prove a Dirac-type condition for an r-partite graph to admit a fractional clique decomposition: every sufficiently large r-partite graph with n vertices in each part and partite minimum
degree at least (1−
1
30r
2 )n admits a fractional Kr-decomposition, subject to necessary divisibility
conditions. This implies the same upper bound on the asymptotic minimum degree threshold
for r-partite graphs to admit a Kr-decomposition, using a well-known reduction.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Acknowledgements
All statements and proofs were developed and completed by the authors in the traditional way, without any use of AI tools. The authors used ChatGPT (GPT-6.1 Sol) for assistance with proofreading only. It also pointed out that the constant 30 in Theorem 1. p. 5 Vi Vj V \ (Vi ∪ Vj )
e
−
−
Kr−2
+
+ −
−
+
+
⇝ Kr−2
e
Figure 2: Edge-adjuster for an edge e ∈ E(Vi
, Vj )
It then suffices to show that ωi(K) is at least zero for every clique K and index i. We do this
by showing that the change in weight of K for vertex balancing is no more than O(εr2
), and when
passing from ωi to ωi+1 for i ≥ 1, the change of weight caused by the edge-adjusters is no more
than O(εr3
(cε)
i
) for some absolute constant c > 0. There exists some n0 = n0(ε, r)
such that for every n ≥ n0, every balanced, Kr-divisible, r-partite graph G with rn vertices and
ˆδ(G) ≥ (1 − ε)n admits a Kr-decomposition. 1 Organization
Section 2 discusses the general outline of our proof strategy.Where the paper says it
Where the paper says it
References
[1] Jack Allsop, Candida Bowtell, Thomas Lesgourgues, and Kalina Petrova, Improved bounds on completion of partial Latin squares, arXiv preprint arXiv:2609.37877 (2026)
[2] Ben Barber, Daniela Kühn, Allan Lo, Richard Montgomery, and Deryk Osthus, Fractional clique decompositions of dense graphs and hypergraphs, Journal of Combinatorial Theory, Series B 127 (2017), 148–186
[3] Ben Barber, Daniela Kühn, Allan Lo, and Deryk Osthus, Edge-decompositions of graphs with high minimum degree, Advances in Mathematics 288 (2016), 337–385
[4] Ben Barber, Daniela Kühn, Allan Lo, Deryk Osthus, and Amelia Taylor, Clique decompositions of multipartite graphs and completion of Latin squares, J. Combin. Theory Ser. p. 0 1 Introduction
A Kr-decomposition of a graph is a partition of its edges into copies of Kr. A basic problem
in extremal design theory is to determine how large the minimum degree must be in a graph to
guarantee such a decomposition, subject to the necessary divisibility conditions.Where the paper says it
[5] Padraic Bartlett, Completions of ε-dense partial Latin squares, Journal of Combinatorial Designs 21 (2013), no. 10, 447–463
[6] Carlo Bonferroni, Teoria statistica delle classi e calcolo delle probabilità, Pubblicazioni del R istituto superiore di scienze economiche e commericiali di Firenze 8 (1936), 3–62
[7] Flora C. Bowditch and Peter J. Dukes, Fractional triangle decompositions of dense 3-partite graphs, Journal of Combinatorics 10 (2019), no. p. 0 An improved minimum degree threshold for fractional clique
decompositions in partite graphs
Sean Longbrake∗ Michael Simkin† Liana Yepremyan∗ Michael Zheng∗
November 5, 2026
Abstract
We prove a Dirac-type condition for an r-partite graph to admit a fractional clique decomposition: every sufficiently large r-partite graph with n vertices in each part and partite minimum
degree at least (1−
1
30r
2 )n admits a fractional Kr-decomposition, subject to necessary divisibility
conditions. This implies the same upper bound on the asymptotic minimum degree threshold
for r-partite graphs to admit a Kr-decomposition, using a well-known reduction.Where the paper says it
[8] Amanda Chetwynd and Roland Häggkvist, Completing partial n × n Latin squares where each row, column and symbol is used at most Cn times, Stockholm University, Department of Mathematics, 1985
[9] David E. Daykin and Roland Häggkvist, Completion of sparse partial latin squares, Graph theory and combinatorics, Academic Press, London, 1984, pp. p. 1 In fact, their results also imply
the existence of such counterexamples even in the r-partite setting which will be the focus of our
paper. This setting is closely related to completion problems for combinatorial designs: triangle decompositions of the complete balanced tripartite graph correspond to Latin squares, and Krdecompositions of the complete balanced r-partite graph correspond to systems of r − 2 mutually
orthogonal Latin squares.Where the paper says it
[10] Michelle Delcourt, Cicely Henderson, Thomas Lesgourgues, and Luke Postle, Beyond NashWilliams: Counterexamples to clique decomposition thresholds for all cliques larger than triangles, Proceedings of the American Mathematical Society 154 (2026), 4107–4125
[11] Michelle Delcourt and Luke Postle, Progress towards Nash-Williams’ conjecture on triangle decompositions, Journal of Combinatorial Theory, Series B 146 (2021), 382–416
[12], A proof of Nash-Williams’ conjecture, arXiv preprint arXiv:2606.11178 (2026)
[13] François Dross, Fractional triangle decompositions in graphs with large minimum degree, SIAM Journal on Discrete Mathematics 30 (2016), no. 1, 36–42
[14] Peter J. Dukes and Daniel Horsley, On the minimum degree required for a triangle decomposition, SIAM Journal on Discrete Mathematics 34 (2020), no. p. 0 A basic problem
in extremal design theory is to determine how large the minimum degree must be in a graph to
guarantee such a decomposition, subject to the necessary divisibility conditions. For triangles, NashWilliams [23] conjectured that every sufficiently large n-vertex graph with minimum degree at least
3n/4, even vertex degrees, and an edge count divisible by three admits a triangle decomposition.Where the paper says it
[15] Tao Feng, Hengrui Liu, and Shikang Yu, Fractional clique decompositions of dense balanced multipartite graphs, arXiv preprint arXiv:2604.25206 (2026)
[16] Kseniya Garaschuk, Linear methods for rational triangle decompositions, Ph.D. thesis, University of Victoria, 2014
[17] Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery, and Deryk Osthus, On the decomposition threshold of a given graph, Journal of Combinatorial Theory, Series B 139 (2019), 47–127
[18] Torbjörn Gustavsson, Decompositions of large graphs and digraphs with high minimum degree, Ph.D. thesis, Stockholm University, 1991
[19] Hengzhi He and Guang Cheng, Fractional triangle decompositions at partite minimum degree 4n/5, arXiv preprint arXiv:2609.31758 (2026)
[20] Matthew Kwan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin, Substructures in Latin squares, Israel J. Math. 256 (2023), no. 2, 363–416
[21] Richard Montgomery, Fractional clique decompositions of dense partite graphs, Combinatorics, Probability and Computing 26 (2017), no. 6, 911–943
[22], Fractional clique decompositions of dense graphs, Random Structures & Algorithms 54 (2019), no. 4, 779–796
Pruning redundant reasoning tokens
The paper defines the fractional Kr-decomposition as a function ω: Kr(G) → R≥0 satisfying X K∈Kr(G):e∈E(K) ω(K) = 1 for every e ∈ E(G). The asymptotic fractional Kr-decomposition threshold is defined as δ∗Kr = lim sup n→∞ δ∗Kr(n). The paper shows that for r ≥ 4, there exists some c > 1 such that there exist infinitely many Kr-divisible graphs G with minimum degree at least 1 − 1/c(r+1)n and no fractional Kr-decomposition. p. 1 The results in [10] disproved this conjecture in the stronger setting by showing that for every r ≥ 4,
there exists some c > 1 such that there exist infinitely many Kr-divisible graphs G with minimum
degree at least
1 −
1
c(r+1)
n and no fractional Kr-decomposition. In fact, their results also imply
the existence of such counterexamples even in the r-partite setting which will be the focus of our
paper.Where the paper says it
How the training signal is built
The proof sketch involves building a fractional Kr-decomposition for G via an explicit limiting process starting from an initial weighting ωinit. This process involves two main phases: Phase 1, which is vertex adjustment to achieve a vertex-balanced weighting ω0, and Phase 2, which is edge adjustment to refine the weights iteratively towards the desired fractional decomposition.
Where the gains come from
The authors show that for r ≥ 4, there exists some c > 1 such that there exist infinitely many Kr-divisible graphs G with minimum degree at least 1 − 1/c(r+1)n and no fractional Kr-decomposition. The main result improves Montgomery’s upper bound to ˆδ∗Kr ≤ 1 − 1/30r squared, increasing the minimum degree deficit from order r−3 to order r−2 in the partite setting. The final step involves showing that ω∞ is non-negative for every r-clique R. By using Corollary 4.9, Lemma 5.18, and Lemma 5.16, the authors prove that ω∞(R) ≥ 0 for r ≥ 3 provided that α = 30, β = 10.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved AI can solve fractional clique decomposition problems for sufficiently large r-partite graphs by finding a fractional Kr-decomposition if every vertex degree is at least (1 minus 1 over 30r over 2)n, subject to necessary divisibility conditions.
-
The improved system can determine the asymptotic minimum degree threshold for r-partite graphs to admit a Kr-decomposition by using the result that deltaKr equals deltaStarKr and providing a refined upper bound of deltaStarKr less than or equal to 1 minus 1 over 30r over 2.
-
The AI can construct vertex-balanced fractional Kr-decompositions for balanced, Kr-divisible r-partite graphs by iteratively adjusting weights using edge adjusters derived from cycles of length four and kr minus two cliques.
-
The system can establish a lower bound on the weight of an r-clique R, denoted as omega0(R), which is greater than or equal to 1 minus 1 over alpha, provided that alpha is greater than 1, for any r-clique R.
-
The improved AI can analyze and bound the edge discrepancy of a fractional Kr-decomposition weighting omega0 for any edge uv in G by using Corollary 4.9 and Lemma 4.8 to show delta0(uv) is bounded by terms involving the initial edge discrepancy and vertex discrepancies times n minus one over alpha, plus an error term.
-
The system can iteratively refine the fractional decomposition weighting from omega i to omega i plus one, showing that the maximum edge discrepancy tends to zero at a rate of 12 epsilon times delta infinity i when epsilon is less than or equal to 1/36.
Abstract
We prove a Dirac-type condition for an r-partite graph to admit a fractional clique decomposition: every sufficiently large r-partite graph with n vertices in each part and partite minimum degree at least (1 - 1 over 30r squared) n admits a fractional K r-decomposition, subject to necessary divisibility conditions. This implies the same upper bound on the asymptotic minimum degree threshold for r-partite graphs to admit a K r-decomposition, using a well-known reduction.
Sources
- A Proof of Nash-Williams' Conjecture
- Fractional clique decompositions of dense balanced multipartite graphs
- On the completion of $\epsilon$-dense partial Latin squares
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality