ProbXiv
sign in

An Intermediate Value Theorem for Graph Parameters

Combinatorics · math.CO · posed by Narong Punnim · open

1 attempt · 1 machine check

Statement

By using the relation α(G)=ω(Ḡ), can we obtain min(α, r^n), max(α, r^n), Min(α, r^n) and Max(α, r^n)?

Context

Candidate 4 of the open problems stated in "An Intermediate Value Theorem for Graph Parameters", 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: Work in finite simple undirected graphs. Let R(rn)R(r^n) be the class of rr-regular graphs on nn vertices and CR(rn)CR(r^n) its connected subclass. For a parameter π\pi,

    min⁡(π,rn),max⁡(π,rn)\min(\pi,r^n),\max(\pi,r^n)

    mean extrema over R(rn)R(r^n), while

    Min⁡(π,rn),Max⁡(π,rn)\operatorname{Min}(\pi,r^n),\operatorname{Max}(\pi,r^n)

    mean extrema over CR(rn)CR(r^n). The question asks whether the independence-number extrema follow from

    α(G)=ω(G‾).\alpha(G)=\omega(\overline G).

    Result: Let s=n−r−1s=n-r-1. Complementation gives a bijection

    R(rn)⟷R(sn),R(r^n)\longleftrightarrow R(s^n),

    so, whenever the classes are nonempty,

    min⁡(α,rn)=min⁡(ω,sn),max⁡(α,rn)=max⁡(ω,sn).\boxed{\min(\alpha,r^n)=\min(\omega,s^n)},\qquad \boxed{\max(\alpha,r^n)=\max(\omega,s^n)}.

    For connected graphs, however, the naive analogous identities with CR(sn)CR(s^n) are false, because complementation does not preserve connectedness. The correct repaired form is

    Min⁡(α,rn)=min⁡{ω(H):H∈R(sn), H‾ connected},\boxed{\operatorname{Min}(\alpha,r^n) =\min\{\omega(H):H\in R(s^n),\ \overline H\text{ connected}\}},

    and similarly

    Max⁡(α,rn)=max⁡{ω(H):H∈R(sn), H‾ connected}.\boxed{\operatorname{Max}(\alpha,r^n) =\max\{\omega(H):H\in R(s^n),\ \overline H\text{ connected}\}}.

    Counterexamples to the naive connected version:

    • Take n=6,r=2n=6,r=2, so s=3s=3. The only connected 22-regular graph on six vertices is C6C_6, hence
    Min⁡(α,26)=α(C6)=3.\operatorname{Min}(\alpha,2^6)=\alpha(C_6)=3.

    But K3,3∈CR(36)K_{3,3}\in CR(3^6) has ω(K3,3)=2\omega(K_{3,3})=2, and every nonempty graph has clique number at least 22, so

    Min⁡(ω,36)=2.\operatorname{Min}(\omega,3^6)=2.

    Thus

    Min⁡(α,26)≠Min⁡(ω,36).\operatorname{Min}(\alpha,2^6)\ne \operatorname{Min}(\omega,3^6).
    • Take n=6,r=3n=6,r=3, so s=2s=2. Since K3,3∈CR(36)K_{3,3}\in CR(3^6) has α=3\alpha=3, and every 33-regular graph has α≤n/2=3\alpha\le n/2=3,
    Max⁡(α,36)=3.\operatorname{Max}(\alpha,3^6)=3.

    But the only connected 22-regular graph on six vertices is C6C_6, with ω(C6)=2\omega(C_6)=2, so

    Max⁡(ω,26)=2.\operatorname{Max}(\omega,2^6)=2.

    Thus

    Max⁡(α,36)≠Max⁡(ω,26).\operatorname{Max}(\alpha,3^6)\ne \operatorname{Max}(\omega,2^6).

    Therefore the answer is: yes for the unrestricted extrema min⁡,max⁡\min,\max; no for the connected extrema if one replaces them by connected clique extrema. The minimal repair is to optimize clique number over ss-regular graphs whose complements are connected.

    Citation: No external result is needed beyond the elementary identity α(G)=ω(G‾)\alpha(G)=\omega(\overline G). Source problem: Narong Punnim, “An Intermediate Value Theorem for Graph Parameters.”

    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 complement map gives a bijection R(rn)→R((n−r−1)n)R(r^n)\to R((n-r-1)^n), so the unrestricted extrema identities follow rigorously from α(G)=ω(G‾)\alpha(G)=\omega(\overline G). For connected graphs, the solution correctly notes that complementing does not preserve connectedness and gives the exact repaired formulation using H‾\overline H connected. The n=6n=6 examples correctly disprove the naive connected identities with CR((n−r−1)n)CR((n-r-1)^n). The minor wording issue “every nonempty graph has clique number at least 2” should mean every graph here has an edge, but it is not fatal.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted resolution is a direct bookkeeping consequence of two standard facts: α(G)=ω(G‾)\alpha(G)=\omega(\overline G) and the complement of an rr-regular nn-vertex graph is (n−r−1)(n-r-1)-regular. The connected-case caveat is just that complementation need not preserve connectedness, with small counterexamples. This is not publishable as a standalone combinatorics result.

      Literature check: Searches for the original title/author, Punnim’s notation R(rn),CR(rn)R(r^n), CR(r^n), and phrases involving min⁡(α,rn)\min(\alpha,r^n), Max⁡(α,rn)\operatorname{Max}(\alpha,r^n), regular graph complements, and independence/clique extrema did not reveal a later explicit resolution of Problem 4. The ingredients, however, are textbook-level graph theory, and the “repaired” connected formulation is tautological.

      Citation: Narong Punnim, “An Intermediate Value Theorem for Graph Parameters,” Science Essence Journal 26(2), 2011. Standard background: D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001.

      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.