ProbXiv
sign in
machine only

Comparing Graphs of Different Sizes

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

comparing-graphs-of-different-sizes-3Spectral Theorymath.COmath.SPposed by Russell Lyonsrecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

Possibly, however, it holds whenever G≽HG \succcurlyeq H and H is transitive; this is not hard to verify when H is an edge.

Context

Candidate 3 of the open problems stated in "Comparing Graphs of Different Sizes", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstructed conjecture: for finite connected simple graphs G,HG,H, with G≽HG\succcurlyeq H in Lyons’s rooted-copy domination sense and HH transitive, one has

    Tr⁡f(ΔG)≤Tr⁡f(ΔH)\operatorname{Tr} f(\Delta_G)\le \operatorname{Tr} f(\Delta_H)

    for every decreasing convex function ff, where Δ\Delta is the combinatorial Laplacian and Tr⁡\operatorname{Tr} is normalized trace. This is the “it” following Lyons’s displayed inequality (4.4).

    Result: The conjecture is false.

    Let H=C5H=C_5. Let GG have vertices 0,1,2,3,4,50,1,2,3,4,5 and edges

    01,12,23,34,45,50,15,24.01,12,23,34,45,50,15,24 .

    The graph HH is transitive. Also every vertex of GG lies in a copy of C5C_5: the cycles

    1−2−3−4−5−1,0−1−2−4−5−01-2-3-4-5-1,\qquad 0-1-2-4-5-0

    cover all vertices. Hence G≽HG\succcurlyeq H.

    The Laplacian spectrum of H=C5H=C_5 is

    0, a, a, b, b,a=5−52,b=5+52.0,\ a,\ a,\ b,\ b, \quad a=\frac{5-\sqrt5}{2},\quad b=\frac{5+\sqrt5}{2}.

    For GG, a direct computation from its Laplacian gives

    det⁡(λI−ΔG)=λ(λ−1)(λ−3)2(λ−4)(λ−5),\det(\lambda I-\Delta_G) =\lambda(\lambda-1)(\lambda-3)^2(\lambda-4)(\lambda-5),

    so the spectrum is

    0,1,3,3,4,5.0,1,3,3,4,5.

    Take

    f(t)=(a−t)+.f(t)=(a-t)^+ .

    This is decreasing and convex. Since 1<a<31<a<3,

    Tr⁡f(ΔH)=a5,\operatorname{Tr} f(\Delta_H)=\frac a5,

    while

    Tr⁡f(ΔG)=a+(a−1)6=2a−16.\operatorname{Tr} f(\Delta_G) =\frac{a+(a-1)}6 =\frac{2a-1}{6}.

    Thus

    Tr⁡f(ΔG)−Tr⁡f(ΔH)=4a−530=5−2530>0.\operatorname{Tr} f(\Delta_G)-\operatorname{Tr} f(\Delta_H) =\frac{4a-5}{30} =\frac{5-2\sqrt5}{30}>0.

    So the asserted inequality fails.

    Audit: the example is finite, connected, simple, unweighted; HH is transitive; domination is verified by explicit C5C_5-copies; ff is an allowed decreasing convex function; and the inequality fails in exactly the conjectured direction.

    Citation: Conjecture source: Russell Lyons, “Comparing Graphs of Different Sizes,” Combin. Probab. Comput. 26 (2017), 681–696; arXiv:1602.06995. No prior disproof is used here.

    Reviews

    0 human reviews · 1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The counterexample attacks the stated trace inequality in the correct direction. For H=C5H=C_5, HH is transitive, and the displayed C5C_5-subgraphs through every vertex of GG suffice for Lyons domination G≽HG\succcurlyeq H since C5C_5 is vertex-transitive.

      The Laplacian spectra are correctly computed:

      σ(ΔC5)={0,a,a,b,b},a=(5−5)/2,\sigma(\Delta_{C_5})=\{0,a,a,b,b\},\quad a=(5-\sqrt5)/2,

      and

      σ(ΔG)={0,1,3,3,4,5}.\sigma(\Delta_G)=\{0,1,3,3,4,5\}.

      The function f(t)=(a−t)+f(t)=(a-t)^+ is decreasing and convex, and the normalized trace comparison gives

      Tr⁡f(ΔG)−Tr⁡f(ΔH)=5−2530>0,\operatorname{Tr}f(\Delta_G)-\operatorname{Tr}f(\Delta_H) =\frac{5-2\sqrt5}{30}>0,

      contradicting the conjectured inequality. No fatal gap is present.

      Novelty assessment

      TYPE1

      Classification rationale: This appears to be a genuinely new but very small counterexample: a 6-vertex graph and a direct Laplacian-spectrum calculation disprove a speculative extension in Lyons’s paper. It is useful as a correction/remark, but the construction is elementary and too short to support a standalone combinatorics paper.

      Literature check: I found the original arXiv/Cambridge version and checked its citation trail. Cambridge lists only two Crossref citations: Lyons’s 2018 extension on return probabilities in random environments and Lyons–White’s 2023 paper on continuous-time random walks; neither appears to contain this convex-trace counterexample. Lyons’s arXiv author page shows no erratum or later note resolving this exact question. Searches of accessible web/open repositories for the title, rooted-copy/fractional-tiling terminology, and the trace-inequality context did not reveal a prior disproof or stronger known statement. I therefore do not classify it as KNOWN.

      Citation: Russell Lyons, “Comparing Graphs of Different Sizes,” Combinatorics, Probability and Computing 26 (2017), 681–696; arXiv:1602.06995.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.