ProbXiv
sign in

Homomorphisms of Trees into a Path

Combinatorics · math.CO · posed by Péter Csikvári, Zhicong Lin · open

1 attempt · 1 machine check

Statement

The Möbius function of KCnKC_{n} alternates in sign for each n≥1n \geq 1.

Context

Candidate 3 of the open problems stated in "Homomorphisms of Trees into a Path", 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: Let KCnKC_n be the ranked poset of isomorphism classes of trees on nn vertices ordered by proper KC-transformations: if x,yx,y are non-leaves of a tree TT, every internal vertex of the path xPyxPy has degree 22, and zz is the neighbor of yy on xPyxPy, then the KC-transform deletes all edges ywyw with w∈N(y)∖{z}w\in N(y)\setminus\{z\} and adds xwxw. The rank is the number of leaves. The conjecture says that its Möbius function alternates:

    (−1)ρ(b)−ρ(a)μ(a,b)≥0(a≤b in KCn).(-1)^{\rho(b)-\rho(a)}\mu(a,b)\ge 0 \qquad(a\le b\text{ in }KC_n).

    This is the standard meaning of “the Möbius function of a ranked poset alternates in sign.”

    Result: The conjecture is false. A counterexample occurs in KC14KC_{14}.

    Use vertices 0,…,130,\dots,13. Let T0,…,T7T_0,\dots,T_7 be the following trees, where (i,j)(i,j) denotes an edge.

    E(T0)={(0,1),(0,8),(1,2),(2,3),(3,4),(4,5),(4,6),(4,7),(8,9),(9,10),(9,13),(10,11),(11,12)},E(T1)={(0,1),(0,10),(1,2),(1,5),(1,9),(2,3),(3,4),(5,6),(5,7),(5,8),(10,11),(11,12),(12,13)},E(T2)={(0,1),(0,5),(0,10),(0,13),(1,2),(2,3),(3,4),(5,6),(6,7),(6,8),(6,9),(10,11),(11,12)},E(T3)={(0,1),(0,6),(0,9),(0,13),(1,2),(2,3),(3,4),(3,5),(6,7),(7,8),(9,10),(9,11),(9,12)},E(T4)={(0,1),(0,6),(0,9),(0,13),(1,2),(2,3),(2,5),(3,4),(6,7),(7,8),(9,10),(9,11),(9,12)},E(T5)={(0,1),(0,6),(0,10),(0,13),(1,2),(2,3),(2,4),(2,5),(6,7),(7,8),(7,9),(10,11),(11,12)},E(T6)={(0,1),(0,6),(0,10),(0,13),(1,2),(2,3),(2,4),(2,5),(6,7),(6,9),(7,8),(10,11),(11,12)},E(T7)={(0,1),(0,6),(0,9),(0,13),(1,2),(2,3),(2,4),(2,5),(6,7),(7,8),(9,10),(9,11),(9,12)}.\begin{aligned} E(T_0)=&\{(0,1),(0,8),(1,2),(2,3),(3,4),(4,5),(4,6),(4,7),\\ &\qquad (8,9),(9,10),(9,13),(10,11),(11,12)\},\\ E(T_1)=&\{(0,1),(0,10),(1,2),(1,5),(1,9),(2,3),(3,4),\\ &\qquad (5,6),(5,7),(5,8),(10,11),(11,12),(12,13)\},\\ E(T_2)=&\{(0,1),(0,5),(0,10),(0,13),(1,2),(2,3),(3,4),\\ &\qquad (5,6),(6,7),(6,8),(6,9),(10,11),(11,12)\},\\ E(T_3)=&\{(0,1),(0,6),(0,9),(0,13),(1,2),(2,3),(3,4),(3,5),\\ &\qquad (6,7),(7,8),(9,10),(9,11),(9,12)\},\\ E(T_4)=&\{(0,1),(0,6),(0,9),(0,13),(1,2),(2,3),(2,5),(3,4),\\ &\qquad (6,7),(7,8),(9,10),(9,11),(9,12)\},\\ E(T_5)=&\{(0,1),(0,6),(0,10),(0,13),(1,2),(2,3),(2,4),(2,5),\\ &\qquad (6,7),(7,8),(7,9),(10,11),(11,12)\},\\ E(T_6)=&\{(0,1),(0,6),(0,10),(0,13),(1,2),(2,3),(2,4),(2,5),\\ &\qquad (6,7),(6,9),(7,8),(10,11),(11,12)\},\\ E(T_7)=&\{(0,1),(0,6),(0,9),(0,13),(1,2),(2,3),(2,4),(2,5),\\ &\qquad (6,7),(7,8),(9,10),(9,11),(9,12)\}. \end{aligned}

    A direct check of all proper KC-transformations gives the complete interval [T0,T7][T_0,T_7] with Hasse diagram

    T0⋖T1,T2,T1⋖T3,T4,T2⋖T5,T6,T3,T4,T5,T6⋖T7.T_0\lessdot T_1,T_2,\qquad T_1\lessdot T_3,T_4,\qquad T_2\lessdot T_5,T_6,\qquad T_3,T_4,T_5,T_6\lessdot T_7.

    No other elements lie in this interval.

    The leaf counts are

    ρ(T0)=5,ρ(T1)=ρ(T2)=6,ρ(T3)=⋯=ρ(T6)=7,ρ(T7)=8.\rho(T_0)=5,\quad \rho(T_1)=\rho(T_2)=6,\quad \rho(T_3)=\cdots=\rho(T_6)=7,\quad \rho(T_7)=8.

    Thus ρ(T7)−ρ(T0)=3\rho(T_7)-\rho(T_0)=3.

    Compute the Möbius function recursively:

    μ(T0,T0)=1,\mu(T_0,T_0)=1, μ(T0,T1)=μ(T0,T2)=−1,\mu(T_0,T_1)=\mu(T_0,T_2)=-1,

    and

    μ(T0,Ti)=0(3≤i≤6),\mu(T_0,T_i)=0\qquad (3\le i\le 6),

    because each TiT_i for 3≤i≤63\le i\le 6 covers exactly one of T1,T2T_1,T_2. Finally,

    μ(T0,T7)=−∑T0≤z<T7μ(T0,z)=−(1−1−1+0+0+0+0)=1.\mu(T_0,T_7) = -\sum_{T_0\le z<T_7}\mu(T_0,z) =-(1-1-1+0+0+0+0)=1.

    But alternating sign would require

    (−1)3μ(T0,T7)≥0,(-1)^3\mu(T_0,T_7)\ge 0,

    i.e. −1≥0-1\ge0, impossible. Hence the conjecture is false.

    Citation: Original conjecture: P. Csikvári and Z. Lin, “Homomorphisms of Trees into a Path,” SIAM J. Discrete Math. 29 (2015), 1406–1422, Conjecture 5.3. The counterexample above is not taken from the literature.

    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 TYPE2

      PASS

      The counterexample attacks the exact Conjecture 5.3: alternating signs for all intervals in the KC/Csikvári poset. The listed 14-vertex trees have the stated ranks, and the asserted interval gives μ(T0,T7)=1\mu(T_0,T_7)=1 while ρ(T7)−ρ(T0)=3\rho(T_7)-\rho(T_0)=3, contradicting (−1)3μ≥0(-1)^3\mu\ge 0. The KC-cover relations and absence of other interval elements are finite and check out from the given edge lists. I found no prior published resolution/counterexample in the literature search.

      Novelty assessment

      TYPE2

      Classification rationale: A concrete counterexample in KC14KC_{14} disproves a named published conjecture about the Möbius function of Csikvári/KC tree posets. The result is narrow and essentially finite/computational, so it is not top-journal level, but it plausibly supports a short standalone note in a standard combinatorics journal.

      Literature check: I searched for the conjecture text and variants involving “KC_n”, “KC-transformation”, “Csikvári poset”, “generalized tree shift”, “Möbius/Mobius function”, “alternates in sign”, and “KC_{14}”. I found no prior counterexample or resolution. Semantic Scholar lists only four citations to the original paper, none concerning this Möbius-sign conjecture. Recent related work, especially Ding’s 2024/2025 paper on Csikvári’s poset and the Tutte polynomial, studies the same poset but proves a different Reiner–Smith conjecture and does not address the Möbius function.

      Citation: P. Csikvári and Z. Lin, “Homomorphisms of Trees into a Path,” SIAM Journal on Discrete Mathematics 29 (2015), 1406–1422, Conjecture 5.3. Related: C. Ding, “Csikvári’s poset and Tutte polynomial,” arXiv:2405.09027 / Discrete Mathematics 2025.

      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.