ProbXiv
sign in

Union of shadows

Combinatorics · math.CO · posed by Béla Bollobás, Imre Leader · open

1 attempt · 1 machine check

Statement

If A\mathcal{A} is [k](4)[k]^{(4)} then this set is precisely A\mathcal{A} itself, but is it always the case that (for ∣A∣>1|\mathcal{A}| > 1) we have ∣S(A)∣≥∣A∣|S(\mathcal{A})| \ge |\mathcal{A}|?

Context

Candidate 6 of the open problems stated in "Union of shadows", 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 XX be finite and A⊆(X4)\mathcal A\subseteq \binom X4, ∣A∣>1|\mathcal A|>1. Define

    S(A)={P∪Q∈(X4): P,Q∈(X2), P∩Q=∅, ∃A,B∈A, A≠B, P⊂A, Q⊂B}.S(\mathcal A)=\{P\cup Q\in \binom X4:\ P,Q\in\binom X2,\ P\cap Q=\varnothing,\ \exists A,B\in\mathcal A,\ A\ne B,\ P\subset A,\ Q\subset B\}.

    This is the natural reading of “union of two 2-sets contained in different members of A\mathcal A.” The conjecture asks whether

    ∣S(A)∣≥∣A∣.|S(\mathcal A)|\ge |\mathcal A|.

    Result: The conjecture is true.

    Call E∈AE\in\mathcal A 2-isolated if no pair p∈(E2)p\in\binom E2 is contained in any other member of A\mathcal A. Let I\mathcal I be the set of 2-isolated members.

    First, for E∈AE\in\mathcal A,

    E∈S(A)⟺E∉I.E\in S(\mathcal A)\quad\Longleftrightarrow\quad E\notin\mathcal I.

    Indeed, if some pair p⊂Ep\subset E lies in F≠EF\ne E, then E=p∪(E∖p)∈S(A)E=p\cup(E\setminus p)\in S(\mathcal A). Conversely, if E=P∪Q∈S(A)E=P\cup Q\in S(\mathcal A), then one of the witnessing members different from the other gives a pair of EE lying in a member other than EE. Hence

    ∣S(A)∩A∣=∣A∣−∣I∣.|S(\mathcal A)\cap\mathcal A|=|\mathcal A|-|\mathcal I|.

    It remains to show ∣S(A)∖A∣≥∣I∣|S(\mathcal A)\setminus\mathcal A|\ge |\mathcal I|. For each E∈IE\in\mathcal I, choose FE∈A∖{E}F_E\in\mathcal A\setminus\{E\}. Since EE is 2-isolated, ∣E∩FE∣≤1|E\cap F_E|\le 1, so choose a pair pE⊂E∖FEp_E\subset E\setminus F_E. For every q∈(FE2)q\in\binom{F_E}{2}, the set pE∪qp_E\cup q lies in S(A)∖AS(\mathcal A)\setminus\mathcal A. There are six such qq's.

    The pairs pEp_E are distinct as EE varies, and any fixed 4-set contains at most six pairs. Therefore the union of all these constructed sets has size at least

    6∣I∣6=∣I∣.\frac{6|\mathcal I|}{6}=|\mathcal I|.

    Thus

    ∣S(A)∣=∣S(A)∩A∣+∣S(A)∖A∣≥(∣A∣−∣I∣)+∣I∣=∣A∣.|S(\mathcal A)|=|S(\mathcal A)\cap\mathcal A|+|S(\mathcal A)\setminus\mathcal A| \ge (|\mathcal A|-|\mathcal I|)+|\mathcal I| =|\mathcal A|.

    Citation: Problem source: Béla Bollobás and Imre Leader, “Union of shadows,” Theoretical Computer Science 307 (2003), 493–502. No external resolution is used here.

    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 proof is mathematically complete for the stated “different members” definition of S(A)S(\mathcal A). The isolated/non-isolated decomposition is valid, and the double-counting argument for producing at least ∣I∣|\mathcal I| new sets in S(A)∖AS(\mathcal A)\setminus\mathcal A is sound. I found no evidence of a prior published resolution in available citation/search checks, so this is not marked KNOWN.

      Novelty assessment

      TYPE1

      Classification rationale: The result appears genuinely new, but the proof is very short and elementary: an isolated/non-isolated decomposition plus a simple double-counting bound. It resolves only a narrow lower-bound question, not the broader minimization problem or main Bollobás–Leader conjectures. This would likely be a useful observation or addendum, but not a standalone standard-journal paper.

      Literature check: I found no prior resolution. OpenAlex’s record for the original paper lists cited_by_count 0. Searches around “Union of shadows”, Bollobás–Leader, “union of two 2-sets”, “different members”, and the S(A)S(\mathcal A) 4-set formulation did not reveal a paper, note, forum post, or stronger theorem containing this argument or statement.

      Citation: Béla Bollobás and Imre Leader, “Union of shadows,” Theoretical Computer Science 307(3) (2003), 493–502. DOI: 10.1016/S0304-3975(03)00233-0.

      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.