ProbXiv
sign in

STANLEY-WILF LIMITS FOR PATTERNS IN ROOTED LABELED FORESTS

Combinatorics · math.CO · posed by Michael Ren · open

1 attempt · 1 machine check

Statement

A set S of patterns is uncovered if and only if it satisfies fn=O(tn+1)f_n = O(t_{n+1}).

Context

Candidate 6 of the open problems stated in "STANLEY-WILF LIMITS FOR PATTERNS IN ROOTED LABELED FORESTS", 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: for a finite set SS of permutation patterns, let fn(S)f_n(S) and tn(S)t_n(S) be the numbers of rooted labeled forests and rooted labeled trees on [n][n], respectively, avoiding every pattern in SS. A set SS is covered if it contains a pattern beginning with its smallest entry and a pattern beginning with its largest entry; otherwise it is uncovered. The conjecture asserts:

    S is uncovered⟺fn(S)=O(tn+1(S)).S\text{ is uncovered}\quad\Longleftrightarrow\quad f_n(S)=O(t_{n+1}(S)).

    Result: The conjecture is false as stated.

    Take

    S={132,21}.S=\{132,21\}.

    This set is covered: 132132 begins with its smallest entry 11, and 2121 begins with its largest entry 22.

    However, avoiding SS is exactly the same as avoiding 2121. Indeed, every instance of 132132 contains an instance of 2121 in its last two vertices, so the pattern 132132 is redundant once 2121 is forbidden.

    Thus SS-avoiding forests are precisely increasing rooted labeled forests. Let fn=fn(S)f_n=f_n(S). The largest label nn must be a leaf; from an increasing forest on [n−1][n-1], label nn may be added either as a new root or as a child of any of the n−1n-1 existing vertices. Hence

    fn=nfn−1,f0=1,f_n=n f_{n-1},\qquad f_0=1,

    so fn=n!f_n=n!.

    Similarly, an increasing rooted labeled tree on [n+1][n+1] has root 11, and the largest label n+1n+1 may be attached as a leaf to any of the previous nn vertices. Hence

    tn+1(S)=n!.t_{n+1}(S)=n!.

    Therefore

    fn(S)=tn+1(S)f_n(S)=t_{n+1}(S)

    for all nn, so certainly fn(S)=O(tn+1(S))f_n(S)=O(t_{n+1}(S)), despite SS being covered.

    The defect is that “covered” is not invariant under deleting redundant forbidden patterns. A natural repair would be to require SS to be a minimal avoidance basis, i.e. no pattern in SS contains another pattern in SS, or equivalently to define covered/uncovered after removing redundant patterns.

    Citation: No known literature resolution is needed; the counterexample above is elementary.

    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 valid. In the paper’s definition, S={132,21}S=\{132,21\} is covered: 132132 begins with its minimum and 2121 begins with its maximum. Avoiding SS is exactly avoiding 2121, since every 132132-instance contains a 2121-instance in its last two entries. Thus the avoiding forests are precisely increasing forests.

      The counts are correct: increasing forests on [n][n] satisfy fn=nfn−1f_n=n f_{n-1}, hence fn=n!f_n=n!, and increasing rooted trees on [n+1][n+1] are counted by n!n!. Therefore fn(S)=tn+1(S)f_n(S)=t_{n+1}(S), so fn=O(tn+1)f_n=O(t_{n+1}) although SS is covered. This rigorously disproves the stated “if and only if” conjecture as written.

      Novelty assessment

      TYPE1

      Classification rationale: The counterexample is valid, but it exploits a very elementary wording defect: adding a redundant forbidden pattern can change the “covered/uncovered” label without changing the avoidance class. After reducing S={132,21}S=\{132,21\} to the minimal basis {21}\{21\}, the count is the standard count of increasing forests/trees. This is best viewed as an erratum-level observation, not a standalone publishable combinatorics result.

      Literature check: I found no explicit published resolution or counterexample to Ren’s Conjecture 4.5. The current arXiv/published paper still states the conjecture. Searches of arXiv, DuckDuckGo, Semantic Scholar/OpenAlex, alphaXiv, and MathOverflow for the exact conjecture, “covered/uncovered” terminology, fn=O(tn+1)f_n=O(t_{n+1}), and the rooted-labeled-forest Stanley–Wilf paper found only Ren’s paper, bibliographic mirrors, and Ren’s related Wilf-equivalence paper. However, the ingredients are standard: Ren already notes redundancy phenomena involving 2121, and Anders–Archer count 2121-avoiding forests as increasing forests.

      Citation: Michael Ren, “Stanley–Wilf limits for patterns in rooted labeled forests,” European J. Combin. 116 (2023), Article 103858, Conjecture 4.5.
      K. Anders and K. Archer, “Rooted forests that avoid sets of permutations,” European J. Combin. 77 (2018), 1–16.

      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.