ProbXiv
sign in

Cycle-Continuous Mappings-Order Structure

Combinatorics · math.CO · posed by Robert Šámal · open

1 attempt · 1 machine check

Statement

In the poset of graphs and cc mappings between them, is every non-degenerate interval nonempty? Does every nondegenerate interval contain an infinite antichain? Does every nondegenerate interval contain every countable poset?

Context

Candidate 3 of the open problems stated in "Cycle-Continuous Mappings-Order Structure", 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: in the preorder of finite multigraphs, loops and parallel edges allowed, with
    G≤HG\le H meaning that there exists a cycle-continuous edge map E(G)→E(H)E(G)\to E(H), and after quotienting by mutual reachability, is every strict interval

    (A,B)={X:A<X<B}(A,B)=\{X:A<X<B\}

    nonempty, or even rich enough to contain infinite antichains / every countable poset?

    Result: No. There is a strict empty interval.

    Let 00 be the edgeless graph, and let C2C_2 be the multigraph with two vertices joined by two parallel edges. The only cycles of C2C_2 are ∅\varnothing and E(C2)E(C_2).

    We have 0<C20<C_2: the empty edge map E(0)→E(C2)E(0)\to E(C_2) is cycle-continuous, while no map E(C2)→E(0)E(C_2)\to E(0) exists.

    Now suppose XX satisfies 0<X<C20<X<C_2. Since X≤C2X\le C_2, there is a cycle-continuous map f:E(X)→E(C2)f:E(X)\to E(C_2). But

    f−1(E(C2))=E(X),f^{-1}(E(C_2))=E(X),

    so E(X)E(X) must itself be a cycle in XX, i.e. every vertex of XX has even degree in the whole edge set.

    Also 0<X0<X implies E(X)≠∅E(X)\ne\varnothing. Choose an edge e∈E(X)e\in E(X), and define g:E(C2)→E(X)g:E(C_2)\to E(X) by sending both parallel edges of C2C_2 to ee. For any cycle Z⊆E(X)Z\subseteq E(X), the preimage g−1(Z)g^{-1}(Z) is either ∅\varnothing or all of E(C2)E(C_2), both cycles of C2C_2. Hence gg is cycle-continuous, so C2≤XC_2\le X.

    Thus X≤C2X\le C_2 and C2≤XC_2\le X, contradicting X<C2X<C_2. Therefore

    (0,C2)=∅.(0,C_2)=\varnothing.

    So not every nondegenerate interval is nonempty. Consequently, not every such interval contains an infinite antichain or every countable poset.

    Citation: No external resolution needed; this is a direct counterexample from the definitions in Šámal, “Cycle-continuous mappings — order structure,” Question 5.3.

    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 rigorous under the paper’s stated definitions. The paper allows multigraphs with loops/parallel edges and defines cycles as even edge sets. The edgeless graph 00 maps cycle-continuously to C2C_2, but not conversely, so 0<C20<C_2. If 0<X<C20<X<C_2, then any cc map X→C2X\to C_2 forces E(X)E(X) itself to be a cycle. Since XX has an edge, mapping both edges of C2C_2 to one edge of XX is cycle-continuous, giving C2≤XC_2\le X, contradicting X<C2X<C_2. Thus (0,C2)=∅(0,C_2)=\varnothing, disproving all three asserted interval-richness questions.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample is a one-paragraph boundary observation: C2C_2 is the least nonzero element above the edgeless graph in the cc-order, so (0,C2)=∅(0,C_2)=\varnothing. Even if not explicitly recorded, this is a routine consequence of the definitions and would not support a standalone paper except perhaps as a short correction/comment.

      Literature check: I found the correct source as Šámal’s arXiv:1212.6909 / JGT paper; the URL in the input, arXiv:1212.6861, is unrelated. The paper asks this as Question 4.3 in the arXiv version, defining open intervals and asking whether every non-degenerated interval is nonempty/rich. It also notes a conditional empty interval (Pt,K2)(Pt,K_2) if Jaeger’s conjecture holds, but does not give the unconditional (0,C2)(0,C_2) example. Searches for the exact question phrases, “non-degenerated interval”, “cycle-continuous” with “empty interval”, “edgeless”, “C2C_2”, and related cc-order terms did not reveal a published explicit resolution or stronger known theorem.

      Citation: Robert Šámal, “Cycle-continuous mappings — order structure,” Journal of Graph Theory 85(1):56–73, 2017; arXiv:1212.6909; doi:10.1002/jgt.22047.

      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.