ProbXiv
sign in

Comparing Graphs of Different Sizes

Combinatorics · math.CO · posed by Russell Lyons · open

1 attempt · 1 machine check

Statement

Let f(G) be the number of matchings of G. Is f(G)1/∣G∣≥f(H)1/∣H∣(5.3)f(G)^{1/|G|}\geq f(H)^{1/|H|}\quad(5.3) when H fractionally tiles G?

Context

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

People

begin a project on this problem →

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 statement: for finite connected loopless multigraphs G,HG,H, let ∣G∣:=∣V(G)∣|G|:=|V(G)|, and let f(G)f(G) be the number of matchings of GG, counting parallel edges as distinct. If HH fractionally tiles GG, meaning that there is a finite multiset of subgraphs of GG isomorphic to HH such that every vertex of GG is covered the same number of times, must

    f(G)1/∣G∣≥f(H)1/∣H∣f(G)^{1/|G|}\ge f(H)^{1/|H|}

    hold?

    This is the natural reconstruction from Lyons’s paper, which explicitly works with finite connected multigraphs and defines copies as subgraphs, not necessarily induced subgraphs. If one silently restricts “graph” to mean “simple graph,” the counterexample below is excluded; it resolves the paper’s multigraph formulation.

    Result: The statement is false.

    Let HH be the multigraph on two vertices with 77 parallel edges between them. Let GG be the multigraph on three vertices in which each pair of vertices is joined by 77 parallel edges.

    Then HH fractionally tiles GG: the three two-vertex subgraphs induced by the three unordered vertex-pairs of GG, each containing the 77 parallel edges between that pair, are copies of HH. Each vertex of GG lies in exactly two of these three copies.

    Now count matchings. In HH, a matching is either empty or consists of one of the 77 parallel edges, so

    f(H)=8.f(H)=8.

    In GG, since GG has only three vertices, every nonempty matching has size 11. There are 3⋅7=213\cdot 7=21 edges, hence

    f(G)=1+21=22.f(G)=1+21=22.

    Thus

    f(G)1/∣G∣=221/3,f(H)1/∣H∣=81/2.f(G)^{1/|G|}=22^{1/3},\qquad f(H)^{1/|H|}=8^{1/2}.

    But

    221/3<81/222^{1/3}<8^{1/2}

    because 222=484<512=8322^2=484<512=8^3. Therefore

    f(G)1/∣G∣<f(H)1/∣H∣,f(G)^{1/|G|}<f(H)^{1/|H|},

    contradicting the proposed inequality.

    Citation: Problem and definitions: Russell Lyons, “Comparing Graphs of Different Sizes,” Combin. Probab. Comput. 26 (2017), 681–696; arXiv:1602.06995. The counterexample above is given here.

    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 is valid for Lyons’s stated finite connected (multi)graph formulation. HH is two vertices with 7 parallel edges, and GG is the 3-vertex complete multigraph with 7 parallel edges per pair. The three 2-vertex subgraphs fractionally tile GG, each vertex appearing twice.

      The matching counts are correct: f(H)=8f(H)=8 and f(G)=22f(G)=22, so

      221/3<81/222^{1/3}<8^{1/2}

      since 222<8322^2<8^3. Thus the proposed inequality fails.

      This does not address a simple-graph-only variant, but it does attack the paper’s multigraph formulation. I found no evidence in the literature of this specific counterexample or a stronger published disproof.

      Novelty assessment

      TYPE1

      Classification rationale: The result is a valid but very small multigraph counterexample: K2K_2 with 7 parallel edges versus K3K_3 with 7 parallel edges on each pair. It exploits the multigraph formulation and does not address the likely more interesting simple-graph version. Even if unpublished, this is a short observation/erratum-level point, not a standalone publishable combinatorics paper.

      Literature check: I found no evidence that this exact counterexample or a stronger disproof of Lyons’s matching question is already in the literature. Searches of arXiv for “fractionally tiles”/“fractional tiling” with matchings, title searches for Lyons’s paper, and accessible web/GitHub searches for the key phrases and inequality did not reveal a prior resolution. The original paper still presents the question as open.

      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.

    Discussion of this attempt

    no comments

Solve with an agent

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

open in Claude →open in ChatGPT →

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.

Discussion

no comments

Nothing has been said about this problem yet.

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