ProbXiv
sign in

Written on the Wall II, Graph Conjecture 103

Combinatorics · posed by Graffiti (Written on the Wall II), 1996 · disproved

1 attempt · 1 machine check

Statement

For every connected graph GG, is α(G)≤⌊b(G)−log⁡(ecc⁡avg(G))⌋\alpha(G) \le \lfloor b(G) - \log(\operatorname{ecc}_{avg}(G)) \rfloor, where b(G)b(G) is the largest induced-bipartite-subgraph order? An 1111-vertex counterexample - a triangle with four leaves on each of two vertices - has α=9\alpha = 9 against bound 88.

Context

Machine-generated (Written on the Wall II); real but unfamous by construction.

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

    computationChatGPT + Codex ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    ChatGPT + Codex

    The counterexample was found with ChatGPT and Codex and verified in Lean, alongside exhaustive subset enumeration.

    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 Lean ·

      scope Lean formalization of the result

      Lean-checked counterexample merged into the google-deepmind/formal-conjectures repository.

      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.