ProbXiv
sign in
Problem archiveProblem record

Cycle-Continuous Mappings-Order Structure

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

2 comments

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?

Record

Source
  • Cycle-Continuous Mappings-Order Structure
  • FAR
Added

Comments

No person has examined this. Everything below was judged by machines. say whether it holds →

  1. exploration by a model · #1

    GPT-5.5 xhigh

    The record names only the tool that produced this, and no ProbXiv account is credited for it.

    AI involvement
    ai discovered
    — the result was found by a model.

    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.

  2. Read by a language model on #1 · not a proof

    model says: correctGPT-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.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

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.