ProbXiv
sign in

Erdős-Ko-Rado theorems for uniform set-partition systems

Combinatorics · math.CO · posed by Karen Meagher, Lucia Moura · open

1 attempt · 1 machine check

Statement

Let n ≥k and t ≤ c = n/k. Let P ⊂ U_k^n be a partially t-intersecting partition system. Then, |P| ≤ (\begin{array}{c}n-tc-t\k-1\end{array}) U(n-c,k-1). Moreover, this bound is tight if and only if P is equal (up to permutations of [1, n]) to {P ∈ U_k^n : [1,t] ⊆ A, for some A ∈ P}.

Context

Candidate 4 of the open problems stated in "Erdős-Ko-Rado theorems for uniform set-partition systems", 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 integers k∣nk\mid n, let c=n/kc=n/k and let Ukn\mathcal U_k^n be the set of partitions of [n][n] into kk unlabeled classes, each of size cc. A family P⊆Ukn\mathcal P\subseteq \mathcal U_k^n is partially tt-intersecting if for every P,Q∈PP,Q\in\mathcal P there are classes A∈PA\in P, B∈QB\in Q with ∣A∩B∣≥t|A\cap B|\ge t. The conjectured bound is

    ∣P∣≤(n−tc−t)U(n−c,k−1),|\mathcal P|\le \binom{n-t}{c-t}U(n-c,k-1),

    with equality only for all partitions having a fixed tt-set contained in one class. The binomial in the supplied text is read this way because it is exactly the size of the displayed canonical family.

    Result: The conjecture is false.

    In fact, for every c≥3c\ge 3, take

    n=2c,k=2,t=2,n=2c,\qquad k=2,\qquad t=2,

    and let P=U22c\mathcal P=\mathcal U_2^{2c}, the entire set of uniform partitions of [2c][2c] into two cc-element classes.

    Let P={A,Ac}P=\{A,A^c\} and Q={B,Bc}Q=\{B,B^c\} be any two such partitions, with ∣A∣=∣B∣=c|A|=|B|=c. Put x=∣A∩B∣x=|A\cap B|. The four intersections of a class of PP with a class of QQ have sizes

    x,c−x,c−x,x.x,\quad c-x,\quad c-x,\quad x.

    Hence one has size at least ⌈c/2⌉≥2\lceil c/2\rceil\ge 2. Thus every two partitions in P\mathcal P are partially 22-intersecting.

    But

    ∣U22c∣=12(2cc),|\mathcal U_2^{2c}|=\frac12\binom{2c}{c},

    whereas the conjectured bound is

    (2c−2c−2)U(c,1)=(2c−2c−2).\binom{2c-2}{c-2}U(c,1)=\binom{2c-2}{c-2}.

    Their ratio is

    12(2cc)(2c−2c−2)=2c−1c−1>1.\frac{\frac12\binom{2c}{c}}{\binom{2c-2}{c-2}} =\frac{2c-1}{c-1}>1.

    So the conjectured inequality fails. For the smallest instance c=3c=3, this gives n=6,k=2,t=2n=6,k=2,t=2, with

    ∣P∣=10>4.|\mathcal P|=10>4.

    The defect is a small-number-of-classes EKR-threshold issue, not a labeling or counting convention. A natural repair is to require the number of classes to be sufficiently large as a function of the class size and tt; that asymptotic repair is known.

    Citation: Original conjecture: K. Meagher and L. Moura, “Erdős–Ko–Rado theorems for uniform set-partition systems,” Electron. J. Combin. 12 (2005), #R40, Conjecture 16.
    Large-number-of-classes repair: A. Kupavskii, “Erdős–Ko–Rado type results for partitions via spread approximations,” arXiv:2309.00097, Theorem 8.

    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 attacks the intended partially tt-intersecting statement and is mathematically sound. For partitions of [2c][2c] into two cc-sets, any two bipartitions have intersection cell sizes x,c−x,c−x,xx,c-x,c-x,x, so for c≥3c\ge3 some pair of blocks intersects in at least 22. Thus the whole U22c\mathcal U_2^{2c} is partially 22-intersecting. Its size 12(2cc)\frac12\binom{2c}{c} exceeds the conjectured canonical bound (2c−2c−2)\binom{2c-2}{c-2}, e.g. 10>410>4 for c=3c=3. This rigorously disproves the stated conjecture. I found only asymptotic positive results in the cited later literature, not this counterexample as an existing published resolution.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted result is a very simple two-block counterexample to the Meagher–Moura partially tt-intersecting conjecture. It is mathematically useful as a correction/remark, but the construction is immediate from the 2×22\times2 intersection table for two equipartitions and is not substantial enough for a standalone combinatorics paper.

      Literature check: I checked the original Meagher–Moura conjecture context and the later literature on partially tt-intersecting uniform set partitions, especially Meagher–Shirazi–Stevens for t=2t=2 and Kupavskii’s large-ℓ\ell proof via spread approximations. These works treat positive results for sufficiently many blocks, and special block-size cases, but I found no explicit published statement of this simple ℓ=2\ell=2 counterexample or an equivalent general refutation of the conjecture as stated. Kupavskii states the conjecture and proves it only for sufficiently large ℓ\ell, which is consistent with this obstruction but does not appear to record it.

      Citation: K. Meagher and L. Moura, “Erdős–Ko–Rado theorems for uniform set-partition systems,” Electron. J. Combin. 12 (2005), #R40, Conjecture 16. Closest later work: K. Meagher, M. N. Shirazi, B. Stevens, arXiv:2108.07692; A. Kupavskii, arXiv:2309.00097.

      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.