ProbXiv
sign in

ON THE FIXED POINT PROPERTY OF FINITE ORDERED SETS

Combinatorics · math.CO · posed by Lech T. Polkowski · open

1 attempt · 1 machine check

Statement

Let G be a finite graph and G = G(min). What condition on the set \mathcal{K}(G) = {K(v) | v \in V(G)} is equivalent to the existence of an endomorphism of G' modulo G?

Context

Candidate 2 of the open problems stated in "ON THE FIXED POINT PROPERTY OF FINITE ORDERED SETS", 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: let GG be a finite simple graph with G=G(min⁡)G=G(\min), so that vertices are identifiable with the sets

    K(v)={C: C is a maximal clique of G, v∈C}.K(v)=\{C:\ C\text{ is a maximal clique of }G,\ v\in C\}.

    Let G′G' denote the complement of GG. An “endomorphism of G′G' modulo GG” is a map f:V(G)→V(G)f:V(G)\to V(G) such that xy∈E(G′)⇒f(x)f(y)∈E(G′)xy\in E(G')\Rightarrow f(x)f(y)\in E(G'), and vf(v)∈E(G)vf(v)\in E(G) for every vv.

    Result: The equivalent condition on K(G)={K(v):v∈V(G)}\mathcal K(G)=\{K(v):v\in V(G)\} is:

    There exists a map

    T:K(G)→K(G)T:\mathcal K(G)\to\mathcal K(G)

    such that for all A,B∈K(G)A,B\in\mathcal K(G),

    1. T(A)≠AT(A)\neq A and A∩T(A)≠∅A\cap T(A)\neq\varnothing;
    2. if A∩B=∅A\cap B=\varnothing, then T(A)∩T(B)=∅T(A)\cap T(B)=\varnothing.

    Proof. For distinct vertices u,vu,v,

    uv∈E(G)  ⟺  K(u)∩K(v)≠∅,uv\in E(G)\iff K(u)\cap K(v)\neq\varnothing,

    because an edge lies in a maximal clique, and a common maximal clique forces adjacency. Hence

    uv∈E(G′)  ⟺  K(u)∩K(v)=∅.uv\in E(G')\iff K(u)\cap K(v)=\varnothing.

    Since G=G(min⁡)G=G(\min), the map v↦K(v)v\mapsto K(v) identifies V(G)V(G) with K(G)\mathcal K(G). Given an endomorphism ff of G′G' modulo GG, define

    T(K(v))=K(f(v)).T(K(v))=K(f(v)).

    The modulo-GG condition vf(v)∈E(G)vf(v)\in E(G) gives K(v)∩K(f(v))≠∅K(v)\cap K(f(v))\neq\varnothing and K(v)≠K(f(v))K(v)\neq K(f(v)). The endomorphism condition on G′G' gives preservation of disjointness. Thus TT satisfies (1)–(2).

    Conversely, given such TT, define f(v)f(v) by K(f(v))=T(K(v))K(f(v))=T(K(v)). Then (1) gives vf(v)∈E(G)vf(v)\in E(G), and (2) gives preservation of complement-edges, so ff is an endomorphism of G′G' modulo GG.

    Citation: No external citation; the equivalence follows directly from the definitions.

    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 proposed condition is a correct clique-incidence translation of the definition. Assuming G=G(min⁡)G=G(\min) means v↦K(v)v\mapsto K(v) is injective, adjacency in GG is exactly nonempty intersection of the corresponding KK-sets, and adjacency in G′G' is disjointness. The two stated properties of TT therefore match exactly the modulo-GG condition and preservation of complement edges, and the proof gives both directions.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted resolution is a direct translation of the definitions under the identification v↔K(v)v\leftrightarrow K(v). It has essentially no independent combinatorial content beyond observing that adjacency in GG becomes nonempty intersection and adjacency in G′G' becomes disjointness. Even if not explicitly recorded elsewhere, it is a routine exercise/lemma and would not support a standalone publication.

      Literature check: I found no evidence that this exact “Problem 1” resolution has been published. Searches for the exact phrase “endomorphism of G′G' modulo GG”, the problem wording, G(min⁡)G(\min) with K(v)K(v), and Polkowski’s title turned up only the original ResearchGate-listed article/profile or no relevant hits. DBLP, OpenAlex autocomplete/search, Internet Archive full-text search, GitHub issue/repository search, DuckDuckGo/Startpage/Bing checks did not reveal a later paper, note, or stronger theorem explicitly solving the problem. The closest “known” material is the standard clique-incidence/intersection-graph observation, from which the proposed condition follows immediately.

      Citation: Lech T. Polkowski, On The Fixed Point Property of Finite Ordered Sets, ResearchGate article/preprint, Dec. 2017, publication ID 320168573. No separate prior citation for the stated equivalence found.

      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.