ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let SS be the set of square-free integers in [2,n][2, n] and G=PR[S]G = PR[S] the graph on SS in which two integers are adjacent when they are not coprime. From the cases n≤100n \le 100 and about twenty further values n≤200n \le 200, Graffiti conjectured that the largest adjacency eigenvalue λ1(G)\lambda_1(G) is at most the number of distinct vertex degrees.

False. At n=51n = 51 the graph has 3131 vertices, 1111 distinct degrees and λ1>11.846\lambda_1 > 11.846; the conjecture fails again for every nn from 786786 to 50005000, and the deficit λ1−D\lambda_1 - D grows roughly linearly in nn, so no additive correction λ1≤D+C\lambda_1 \le D + C survives either.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.