The independence and clique cover numbers of the squarefree graph

Boris Alexeev; Dustin G. Mixon; Will Sawin

REVIEW 1 major objections 4 minor 3 references

The independence and clique cover numbers of the squarefree graph

T0 review · 1 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper proves that the even squarefree numbers up to n form a largest independent set in the squarefree graph, resolving a 1992 problem of Erdős and Sárközy with the answer they guessed.

desk verdict Theorem 2 is a real new structural result; the large-n proof is rigorous, but the small-n case rests on an unspecified computation that may not certify its own prefixes. read the letter →

arxiv 2507.01928 v2 pith:CBFI35L2 submitted 2025-07-02 math.CO math.NT

Boris Alexeev , Dustin G. Mixon , Will Sawin This is my paper

classification math.COmath.NT MSC 05C6905C7011N25

keywords squarefreegraphindependencenumbercliquecoverErdős–SárközyproblemLovásznumberscoprimenegativemomentmethod

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper resolves a 1992 problem of Erdős and Sárközy: among all subsets $A$ of $\{1,\dots,n\}$ in which every pair multiplies to a non-squarefree number, which subset is largest? It proves the answer the two authors guessed — take all even numbers together with the odd non-squarefree numbers, equivalently delete precisely the odd squarefree numbers. The proof goes through a stronger structural statement, Theorem 2: the squarefree graph, whose vertices are the squarefree numbers up to $n$ with an edge between coprime pairs, can be partitioned into cliques each containing exactly one even vertex. Because the even vertices form an independent set, such a partition simultaneously pins the independence number, the clique cover number, and the Lovász number (the relaxation that the Lovász sandwich theorem places between them), all equal to the number of even squarefree numbers up to $n$. Asymptotically the winning set occupies $(1 - 4/\pi^2)n \approx 59.5\%$ of the integers up to $n$.

What carries the argument

The carrying mechanism is the clique cover of the squarefree graph, viewed as a map from the odd squarefree vertices to the even squarefree vertices whose fibers are cliques (sets of pairwise coprime numbers). To build such a cover, the paper compares three assignment strategies: a plain greedy rule, a capped greedy rule that declares an even vertex full after three assigned odd vertices, and a most-constrained-first rule that processes odd vertices in increasing order of the number of even vertices coprime to them. The proof of Theorem 2 splits at $n = 10^{10}$: for small $n$ the capped greedy rule is asserted to succeed computationally, while for $n \ge 10^{10}$ the most-constrained-first rule is shown to succeed using Lemma 4, which asserts a threshold $K \approx 0.672 \cdot c(1,n)$ such that for every $k \le K$ at most $k$ odd vertices are coprime to at most $k$ even vertices, and every odd vertex coprime to more than $K$ even vertices shares a factor with at most that many odd vertices. Lemma 4 is proved from explicit estimates on the degree of an odd vertex, obtained by inclusion–exclusion with errors of order $\sqrt{n}$, and from the negative moment method, the inequality $P\{X \le s\} \le (E[X^{-1}] - b^{-1})/(s^{-1} - b^{-1})$ for $0 \le X \le b$, applied after conditioning on whether $3$ divides the vertex.

What would settle it

Run an independent implementation of the capped greedy rule up to $n = 10^{10}$, checking at each step that every odd squarefree vertex is assigned to an unfilled coprime even vertex; the first $n$ where the rule gets stuck — or where some fiber fails to be a clique — refutes the small-$n$ case of the proof. A direct search for an independent set larger than the even vertices at any single $n$ would refute the theorem itself.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 2, is that the vertices of the squarefree graph can be partitioned into cliques each containing exactly one even vertex; in other words, every odd squarefree vertex can be assigned to an even squarefree vertex so that each fiber consists of pairwise coprime numbers. The partition is produced by two complementary strategies whose domains meet at $n = 10^{10}$: a fast capped greedy rule, asserted to succeed computationally for every $n < 10^{10}$ (the paper reports running it up to $3.5 \times 10^{10}$), and a most-constrained-first rule, proved analytically for every $n \ge 10^{10}$ via a counting lemma (Lemma 4). Lemma 4 rests on explicit nonasymptotic estimates, built from an inclusion–exclusion formula for the degree of a vertex, $\deg(\ell,n) \approx f(\ell) v(n)$ with $f(\ell) = \prod_{p \mid \ell}(1 - 1/(p+1))$ and $v(n) = (6/\pi^2) n$, sharpened by divisor-product bounds and the negative moment method. Since the even vertices form an independent set, a clique cover of the same size forces the independence number, the clique cover number, and the Lovász number of the squarefree graph to coincide, resolving the Erdős–Sárközy problem as a corollary.

Load-bearing premise

The proof's small-$n$ half rests on an unverified computational assertion: the capped greedy assignment is claimed to succeed for every $n < 10^{10}$ (and is reported to run up to $3.5 \times 10^{10}$), yet the manuscript supplies no code, data, or certificates, so this range cannot be independently checked from the paper alone.

Editorial extensions

If this is right

The Erdős–Sárközy problem is settled: the largest subset of $\{1,\dots,n\}$ with no squarefree pairwise products is the complement of the odd squarefree numbers, of asymptotic size $(1 - 4/\pi^2)n \approx 59.5\%$ of $n$.
The independence number, the clique cover number, and the Lovász number of the squarefree graph all coincide, each equal to the number of even squarefree numbers up to $n$; asymptotically that is about one third of the graph's vertices and $2n/\pi^2 \approx 20.3\%$ of all integers up to $n$.
The same equalities hold for the full graph on $\{1,\dots,n\}$ that includes non-squarefree vertices, since those vertices are isolated.
The clique cover is produced explicitly: the most-constrained-first strategy always succeeds for $n \ge 10^{10}$, and the two greedy rules, if they always succeed, would define a single clique cover shared by all initial segments of the positive integers.

Reading between the lines

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

The equality $\alpha = \theta = \vartheta$ for the whole squarefree graph invites a stronger question the paper does not pose: whether the squarefree graph is perfect, meaning every induced subgraph also has independence number equal to its clique cover number.
The analytic threshold $K = 0.672 \cdot c(1,n)$ sits well below the value $0.874$ that the paper's own Figure 3 suggests is asymptotically attainable, so sharper negative-moment estimates might push Lemma 4 into the medium range and eventually remove the computational case from the proof.
Because the error bounds in Lemmas 5, 7, and 8 are explicit numerical constants, the analytic half of the argument is machine-checkable; pairing a formalized proof with verified computation or certificates for all $n < 10^{10}$ would make the two-case proof a fully verifiable certificate for every $n$.
The canonical nature of the greedy cover, should it always exist, hints at a purely combinatorial proof of Theorem 1 that avoids number-theoretic estimates; the paper's closing question about a clique-cover analogue of the intersecting-family theorem points in the same direction.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing to know: this paper's genuine contribution is Theorem 2, the clique cover with one even vertex per clique. It is new, it is strong, and it immediately implies equality of alpha, clique cover, and Lovasz number. The paper is also honest that Theorem 1—the original Erdos–Sarkozy problem—follows from Chvatal's 1974 theorem, as Weisenberg observed. That does not make the paper redundant; the clique-cover result is strictly stronger and not in the prior literature.

What the paper does well: the n≥10^10 proof is self-contained and explicit. Lemma 5's error bounds, Lemma 8's divisor estimates, and the negative-moment argument are all checkable. The constants are not fitted; they are chosen to make the inequalities close. For that half of the theorem, I have no serious complaint.

Where it gets soft: Case I, n<10^10, is delegated to the sentence "We ran the faster greedy strategy to find the desired partition for all such n." No code, data, or certificates. That would already be a gap. The stress-test note adds a sharper point that I think lands: a single run up to 3.5e10 with the faster greedy does not automatically certify every prefix n≤3.5e10, because for a prefix n the available even vertices are only those ≤n, while a run at N has access to evens above n. Unless the assignment of each odd ℓ uses an even m≤ℓ, the run up to N could succeed while some prefix fails. The manuscript does not state that a prefix condition was checked. So the computational claim is both unverified and ambiguous. This is load-bearing: without it, the theorem is proved only for n≥10^10.

Secondary: Lemma 4's proof says "one may verify" for a numerical inequality. Minor, since the surrounding estimates are explicit, but it's another uncheckable step. And the abstract omits that the independence part was already a corollary of Chvatal; the text admits it, so this is a presentation issue.

None of this is fatal. The large-n proof is rigorous and the small-n computation is likely correct, but it needs to be made reproducible—code, certificates, or at minimum a clear statement of the prefix condition and the run protocol.

Who this is for: people working on extremal combinatorics, squarefree numbers, graph invariants. A serious referee should see it, conditional on the authors providing the computational artifacts. I'd take it to the reading group: the gap is instructive.

Recommendation: send to peer review, not desk reject, because the main contribution is substantial and the fix is straightforward.

Referee Report

1 major / 4 minor

Summary. The paper claims to resolve a 1992 problem of Erdős and Sárközy by proving that, in the squarefree graph on {1,...,n} (where vertices are squarefree numbers and edges join coprime numbers), the even squarefree vertices form a maximum independent set. The main new contribution is a stronger result, Theorem 2: the vertex set of the squarefree graph can be partitioned into cliques, each containing exactly one even vertex. This yields equality of the independence number, clique cover number, and Lovász number. The proof splits into a computational check for n < 10^10 using a 'faster greedy strategy' and an analytic proof for n ≥ 10^10 via a 'most-constrained-first' strategy. The analytic part relies on explicit non-asymptotic estimates (Lemmas 4–8) and the negative moment method. An independent proof of Theorem 1 via Chvátal's theorem is also presented.

Significance. If the computational case is properly certified, the paper settles a long-standing problem and goes substantially beyond it by establishing a clique-cover structure that determines several graph invariants simultaneously. The analytic argument for large n is a notable technical achievement: it uses fully explicit error bounds and constants, making it checkable in principle. The paper also nicely connects to prior work of Chvátal, which already gave a short proof of the independence-number claim. However, the completeness of the main theorem currently hinges on an unverified computational assertion and on a 'one may verify' numerical inequality, so the contribution is not yet fully reproducible from the manuscript.

major comments (1)

[Section 3, Proof of Lemma 4] The step 'One may verify that for all t ≤ 0.672, the right-hand side is less than t/(2(1+ε_a))' is a load-bearing numerical inequality in the proof of condition (a) of Lemma 4, and hence for the entire analytic proof of Theorem 2 for n ≥ 10^10. The constants are explicit, so a derivation or a reproducible computer-assisted verification should be included. As written, this step is not independently verifiable from the manuscript.

minor comments (4)

[References] Reference [2] is used both for the erdosproblems.com website and for 'Weisenberg [2]' in Subsection 1.1; please provide a distinct citation for Weisenberg's observation or clarify that it appears on the website.
[Section 2.1] The sentence 'The vertices assigned to the even vertex 2 are all of the prime numbers' is inaccurate because the odd vertex 1 (and the even vertex 2 itself as the clique's label) also belong to that clique; please rephrase.
[Section 2.3] The example 'despite the hypothesis n ≥ 10^10, we may take K(15)=2' is confusing because n=15 does not satisfy the lemma's hypothesis; consider labelling it as a purely illustrative check.
[Section 3, Lemma 6] In the proof of Lemma 6, the display following 'Markov's inequality gives' appears to be missing a division symbol; the inequality should be P{X ≤ s} ≤ E[Y]/t. Please correct the typesetting.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main derivation is self-contained, with computational checks used as evidence rather than as inputs renamed as predictions.

full rationale

The paper's central claim (Theorem 2) is proved by exhibiting an explicit clique cover construction. Case II (n ≥ 10^10) is a rigorous analytic argument: Lemma 4 is derived from the explicit nonasymptotic estimates in Lemma 5, which in turn follow from Lemma 7 (an inclusion–exclusion degree bound), Lemma 8 (a divisor-product bound), and explicit constant verification for n ≥ 10^10. The constants, such as 0.672 and the epsilon values, are chosen to satisfy the displayed inequalities, not fitted to the target independence number or to the conclusion of Theorem 2. Case I (n < 10^10) relies on a computational run of the faster greedy strategy; while this is an unverifiable and load-bearing computational claim, it is not circular—the greedy partition is a constructive certificate for each n, and no parameter of the theorem is fitted from the data it is then said to predict. The invocation of Chvátal's theorem for Theorem 1 is an independent external result, and the paper explicitly notes that its own proof of Theorem 1 proceeds through the stronger Theorem 2. The statement 'one may verify' in the proof of Lemma 4 is a missing certificate rather than a circular reduction. Overall, no step reduces, by the paper's own equations or by self-citation, to its own inputs.

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

The proof introduces one hand-chosen constant (0.672) and relies on a finite computational claim that is not reproducible from the manuscript. No new mathematical entities are postulated.

free parameters (1)

threshold factor in Lemma 4 = 0.672
Hand-chosen constant in the definition of K to make the inequalities in the proof of Lemma 4 hold. It is not fitted to data.

assumptions (2)

ad hoc to paper The faster greedy strategy successfully produces the desired clique cover for all n < 10^10.
The paper asserts this based on an unprovided computation. This is load-bearing for the small-n case of Theorem 2.
standard math Inclusion-exclusion and Markov's inequality are used without proof.
Standard tools in combinatorics and probability, used throughout Sections 3 and 4.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The independence and clique cover numbers of the squarefree graph." pith.science (2026). https://pith.science/paper/CBFI35L2

@misc{pith2026250701928,
  author       = {Pith},
  title        = {Pith review of: The independence and clique cover numbers of the squarefree graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CBFI35L2}},
  note         = {Machine review of arXiv:2507.01928}
}

abstract

We determine the largest subset $A\subseteq \{1,\dotsc,n\}$ such that for all $a,b\in A$, the product $ab$ is not squarefree. Specifically, the maximum size is achieved by the complement of the odd squarefree numbers. This resolves a problem of Paul Erd\H{o}s and Andr\'as S\'ark\"ozy from 1992.