arxiv: 2603.03086 · v2 · submitted 2026-03-03 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Resolving the Kohayakawa--Kreuter Conjecture for Families

Matthew Yancey

Authors on Pith no claims yet

Pith reviewed 2026-05-15 16:53 UTC · model grok-4.3

classification 🧮 math.CO

keywords sparse graphsedge partitionssparsity conditionsKohayakawa-Kreuter conjectureRamsey theoryrandom graphsgraph decompositions

0 comments

The pith

Every (m,0)-sparse graph can be edge-partitioned into a (1,1)-sparse graph and a (m,2m-1)-sparse graph.

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 any fixed positive integer m, if a graph has the property that every nonempty subgraph H satisfies e(H) at most m times v(H), then its edges can be split into two sets with controlled densities. One subset forms a (1,1)-sparse graph, meaning every subgraph has at most one fewer edge than vertices, while the other is (m,2m-1)-sparse. This partition result directly settles a conjecture of Kuperwasser, Samotij, and Wigderson. That conjecture was previously shown to be sufficient for establishing the Kohayakawa-Kreuter conjecture on the threshold for random graphs to be Ramsey with respect to arbitrary families of graphs.

Core claim

A graph G is (m,0)-sparse if and only if its edges can be partitioned into E(G1) union E(G2) such that G1 is (1,1)-sparse and G2 is (m,2m-1)-sparse. The proof establishes the partition for every (m,0)-sparse graph, confirming the full statement of the conjecture.

What carries the argument

The (a,b)-sparsity condition, under which every nonempty subgraph H obeys e(H) ≤ a v(H) - b, with the edge partition separating the input graph into two subgraphs whose sparsity parameters are (1,1) and (m,2m-1).

If this is right

The Kohayakawa-Kreuter conjecture for families holds, so n to the power -1 over m sub 2 is the threshold function for the random graph G(n,p) to be Ramsey almost surely for any given family of graphs.
Any (m,0)-sparse graph admits a decomposition that isolates a maximal forest-like subgraph from the remaining denser component.
The partition supplies an explicit structural decomposition that can be used to bound the Ramsey properties of graphs with bounded average degree.

Where Pith is reading between the lines

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

The same partition technique may extend to hypergraph sparsity or to partitions into more than two parts with adjusted parameters.
Algorithmic versions of the partition could yield polynomial-time methods for decomposing sparse graphs in network design or embedding problems.
The result tightens the connection between deterministic sparsity bounds and the emergence of monochromatic subgraphs in random edge colorings.

Load-bearing premise

The input graph must satisfy the (m,0)-sparsity condition globally, so that no subgraph has more than m edges per vertex.

What would settle it

An explicit (m,0)-sparse graph, for some fixed m, whose edges cannot be partitioned into any (1,1)-sparse subgraph and (m,2m-1)-sparse subgraph.

read the original abstract

A graph $G$ is $(a,b)$-sparse if every nonempty subgraph $H$ satisfies $e(H) \leq a v(H) - b$. We are interested in the conditions under which an $(a,b)$-sparse graph can be partitioned $E(G) = E(G_1) \cup E(G_2)$ such that for $i \in \{1,2\}$ we have that $G_i$ is $(a_i, b_i)$-sparse. Kuperwasser, Samotij, and Wigderson conjectured that a $(m,0)$-sparse graph can be partitioned into a $(1,1)$-sparse graph and a $(m,2m-1)$-sparse graph. We prove the conjecture in full. The Kohayakawa--Kreuter Conjecture for Families claims that $n^{-1/m_2}$ is the threshold function for the random graph being Ramsey a.a.s. for graph families $\mathcal{H}_1, \ldots \mathcal{H}_r$. Kuperwasser, Samotij, and Wigderson motivated their conjecture by proving that it is sufficient to establish the Kohayakawa--Kreuter Conjecture for Families.

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

Yancey gives a direct inductive proof of the Kuperwasser-Samotij-Wigderson partition conjecture, which settles the Kohayakawa-Kreuter conjecture for families.

read the letter

Yancey proves the Kuperwasser-Samotij-Wigderson conjecture outright: every (m,0)-sparse graph has an edge partition into a (1,1)-sparse graph and a (m,2m-1)-sparse graph. The argument is by induction on vertex count. Edges go into the (1,1) part only when they keep every subgraph within the bound; the remaining edges satisfy the second bound by a direct count that reuses the original (m,0) hypothesis. The stress-test note confirms the base case, inductive step, and disconnected components are all handled without gaps. This is the first complete proof, and it is self-contained combinatorial work rather than a reduction or asymptotic statement. The paper does well by keeping the constants explicit and the case analysis elementary. No free parameters or invented entities appear. The only soft spot worth noting is that the write-up is concise, so a referee might ask for one or two extra small-m examples to make the counting transparent, but the logic itself looks tight. This is for people working on sparse graph partitions or random-graph Ramsey thresholds. Anyone who has followed the Kuperwasser-Samotij-Wigderson conjecture or the larger Kohayakawa-Kreuter statement will get immediate value from the explicit construction. It deserves a serious referee.

Referee Report

0 major / 1 minor

Summary. The paper proves the Kuperwasser-Samotij-Wigderson conjecture that every (m,0)-sparse graph admits an edge-partition into a (1,1)-sparse graph and a (m,2m-1)-sparse graph. The proof is by induction on the number of vertices. In the inductive step, edges are assigned to the (1,1)-sparse part only when they do not violate the sparsity condition on any subgraph; the remaining edges are shown to satisfy the (m,2m-1) bound by a direct counting argument that invokes the original (m,0) hypothesis. The result is motivated by its sufficiency for establishing the Kohayakawa--Kreuter Conjecture for Families on Ramsey thresholds for graph families in random graphs.

Significance. If the proof holds, the manuscript resolves an open conjecture in sparse graph partitioning with a direct, constructive inductive argument that requires no external constants or reductions. This supplies the missing ingredient for the Kohayakawa--Kreuter Conjecture for Families, thereby linking (a,b)-sparsity decompositions to the asymptotic Ramsey behavior of random graphs. The explicit case analysis and counting argument provide a template that may extend to related partition problems in extremal graph theory.

minor comments (1)

[Abstract] The abstract states the main theorem but does not mention the inductive method or the vertex-count induction; adding one sentence on the proof technique would improve immediate readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recommending acceptance. The referee's summary correctly identifies the main result as a full proof of the Kuperwasser-Samotij-Wigderson conjecture via induction, together with its role in the Kohayakawa--Kreuter Conjecture for Families.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The manuscript establishes the Kuperwasser-Samotij-Wigderson conjecture via an explicit induction on vertex count. The inductive step performs a direct case analysis that assigns edges to the (1,1)-sparse part only when no subgraph violates the bound, then verifies the complementary (m,2m-1) bound by a counting argument that invokes only the global (m,0) hypothesis on the original graph. No parameter is fitted to data, no target quantity is renamed as a prediction, and no load-bearing step reduces to a self-citation or prior ansatz of the same authors. The derivation is therefore self-contained against the stated sparsity assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard definition of (a,b)-sparsity and the specific numerical parameters chosen in the conjecture; no new free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)

standard math Standard definitions and basic properties of (a,b)-sparse graphs in extremal graph theory
The paper invokes the established notion that every nonempty subgraph H satisfies e(H) ≤ a v(H) - b.

pith-pipeline@v0.9.0 · 5504 in / 1309 out tokens · 60844 ms · 2026-05-15T16:53:43.193579+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.2: Let m>1. If G is (m,0)-sparse, then there exists a partition G=F∪G′ such that F is (1,−1)-sparse and G′ is (m,1−2m)-sparse.
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Proof outline uses potential ρ(H)=av(H)−e(H) and submodularity to obtain matroid-union rank equality.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.