An improved minimum degree threshold for fractional clique decompositions in partite graphs

arXiv:2611.08432 · math.CO · Submitted 2026-11-05 · Read on arXiv

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

Where the paper says it

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.

p. 2
Where the paper says it

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.

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

Where the paper says it

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.

Kr-divisibility in this setting is defined by the condition that degj(v) = degk(v) for all distinct i, j, k ∈ [r] and every v ∈ Vi. p. 2
Where the paper says it

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).

The asymptotic r-partite Kr-decomposition threshold is defined as ˆδKr = lim sup n→∞ ˆδKr(n). p. 2
Where the paper says it

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).

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

Where the paper says it

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 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. p. 1
Where the paper says it

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.

The best upper bound for general r prior to the work was by Montgomery [21] who showed that, for every integer r ≥ 3, ˆδ∗Kr ≤ 1 − 1/106r cubed. p. 2
Where the paper says it

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 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. p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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 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

Where the paper says it

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.

p. 4
Where the paper says it

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.

The adjustments are guided by edge-adjusters based on cycles of length four between two parts paired with a Kr−2. p. 4
Where the paper says it

(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.

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

Where the paper says it

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.

The initial weighting ωinit is adjusted to a vertex-balanced weighting ω0, where the change in weight is bounded by Corollary 4. p. 4
Where the paper says it

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.

9. Subsequent edge adjustments are designed to reduce the maximum edge-discrepancy δ∞ i by a factor of ε, leading to the desired limit ω∞. p. 5
Where the paper says it

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.

Conclusion and Final Bound

The final step involves showing that ω∞ is non-negative for every r-clique R. p. 0

Where the paper says it

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.

By using Corollary 4. p. 6
Where the paper says it

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.

p. 6
Where the paper says it

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.

9, Lemma 5. p. 7
Where the paper says it

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 .

p. 7
Where the paper says it

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 .

18, and Lemma 5. p. 7
Where the paper says it

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 .

p. 7
Where the paper says it

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 .

16, the authors prove that ω∞(R) ≥ 0 for r ≥ 3 provided that α = 30, β = 10. p. 0
Where the paper says it

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.

p. 0
Where the paper says it

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.

This establishes Theorem 1.1: Every balanced, Kr-divisible, r-partite graph G with n vertices in each part and ˆδ(G) ≥ (1 − ε)n admits a fractional Kr-decomposition for sufficiently large n. p. 0
Where the paper says it

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.

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

Where the paper says it

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.

1 may be replaced by 18 by being more efficient in some of our arguments but we decided to keep our original proof. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

A 151 (2017), 146–201

[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

Where the paper says it

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.

2, 255–282

[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

Where the paper says it

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.

127–132

[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

Where the paper says it

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.

1, 597–610

[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

Where the paper says it

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.

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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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

Related papers