/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 643

References:

    erdosproblems.com/643

    [Fu84] F"uredi, Z., Hypergraphs in which all disjoint pairs have distinct unions. Combinatorica (1984), 161--168.

    [PiVe09] Pikhurko, Oleg and Verstra"{e}te, Jacques, The maximum size of hypergraphs without generalized 4-cycles. J. Combin. Theory Ser. A (2009), 637--649.

    [HMY26] Huang, Hao, Ma, Jie, and Yang, Tianchi, Extremal hypergraphs without generalized 4-cycles. arXiv:2609.37744 (2026), Theorem 1.2.

@[expose] public sectionnamespace Erdos643open Filter Asymptotics

The least number of edges forcing two distinct disjoint pairs with the same union. It is one more than the maximum size of an avoiding family.

noncomputable def forcingThreshold (n t : ℕ) : ℕ := Hypergraph.extremalNumber n t (fun H ↦ ¬ H.HasRepeatedDisjointUnion) + 1def erdos_643.parts.i.answer : ℕ → ℕ → ℝ := sorry

Let $f(n;t)$ be minimal such that if a $t$-uniform hypergraph on $n$ vertices contains at least $f(n;t)$ edges then there must be four edges $A,B,C,D$ such that $$A\cup B= C\cup D$$ and $$A\cap B=C\cap D=\emptyset.$$ Estimate $f(n;t)$ - in particular, is it true that for $t\geq 3$ $$f(n;t)=(1+o(1))\binom{n}{t-1}?$$

@[category research open, question value, AMS 5] theorem erdos_643.parts.i : ∀ t : ℕ, 1 ≤ t → (fun n ↦ (forcingThreshold n t : ℝ)) ~[atTop] erdos_643.parts.i.answer t := ⊢ ∀ (t : ℕ), 1 ≤ t → (fun n ↦ ↑(forcingThreshold n t)) ~[atTop] i.answer t All goals completed! 🐙

Is it true that $f(n;t)=(1+o(1))\binom{n}{t-1}$ for $t\geq 3$?

For $t\geq4$, Huang, Ma, and Yang [HMY26] prove the exact extremal formula below. The case $t=3$ remains open.

@[category research open, question, AMS 5] theorem erdos_643.parts.ii : ∀ t : ℕ, 3 ≤ t → (fun n ↦ (forcingThreshold n t : ℝ)) ~[atTop] (fun n ↦ (n.choose (t - 1) : ℝ)) := ⊢ ∀ (t : ℕ), 3 ≤ t → (fun n ↦ ↑(forcingThreshold n t)) ~[atTop] fun n ↦ ↑(n.choose (t - 1)) All goals completed! 🐙

Huang, Ma, and Yang [HMY26, Theorem 1.2] determine the maximum size of an avoiding family for each fixed $t\geq4$ and all sufficiently large $n$: $$\binom{n-1}{t-1}+\left\lfloor\frac{n-1}{t}\right\rfloor.$$ The forcing threshold is one larger.

@[category research solved, AMS 5] theorem erdos_643.variants.exact_t_ge_four : ∀ t : ℕ, 4 ≤ t → ∀ᶠ n : ℕ in atTop, Hypergraph.extremalNumber n t (fun H ↦ ¬ H.HasRepeatedDisjointUnion) = (n - 1).choose (t - 1) + (n - 1) / t := ⊢ ∀ (t : ℕ), 4 ≤ t → ∀ᶠ (n : ℕ) in atTop, (Hypergraph.extremalNumber n t fun H ↦ ¬H.HasRepeatedDisjointUnion) = (n - 1).choose (t - 1) + (n - 1) / t All goals completed! 🐙

The largest avoiding family attains the value one below the forcing threshold.

n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.Nonempty⊢ ∃ H, H.IsUniform t ∧ ¬H.HasRepeatedDisjointUnion ∧ H.card + 1 = forcingThreshold n t n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.card⊢ ∃ H, H.IsUniform t ∧ ¬H.HasRepeatedDisjointUnion ∧ H.card + 1 = forcingThreshold n t n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ ∃ H, H.IsUniform t ∧ ¬H.HasRepeatedDisjointUnion ∧ H.card + 1 = forcingThreshold n t n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ H.IsUniform tn:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ H.card + 1 = forcingThreshold n t n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ H.IsUniform t n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnione:Finset (Fin n)he:e ∈ H⊢ e.card = t All goals completed! 🐙 n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ H.card + 1 = forcingThreshold n t n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ H.card + 1 = (Hypergraph.extremalNumber n t fun H ↦ ¬H.HasRepeatedDisjointUnion) + 1 n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ H.card = Hypergraph.extremalNumber n t fun H ↦ ¬H.HasRepeatedDisjointUnion calc H.card = S.sup Finset.card := hmax.symm _ = Hypergraph.extremalNumber n t (fun H ↦ ¬ H.HasRepeatedDisjointUnion) := n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ S.sup Finset.card = Hypergraph.extremalNumber n t fun H ↦ ¬H.HasRepeatedDisjointUnion n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ S.sup Finset.card = {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}.sup Finset.card n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnion⊢ S = {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion} n:ℕt:ℕS:Finset (Finset (Finset (Fin n))) := {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hne:S.NonemptyH:Finset (Finset (Fin n))hH:H ∈ Shmax:S.sup Finset.card = H.cardhmem:H ∈ (Finset.powersetCard t Finset.univ).powerset ∧ ¬H.HasRepeatedDisjointUnionK:Finset (Finset (Fin n))⊢ K ∈ S ↔ K ∈ {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion} All goals completed! 🐙

A bound is at least the forcing threshold exactly when every uniform family with that many edges contains the forbidden four-edge configuration.

n:ℕt:ℕm:ℕhm:forcingThreshold n t ≤ mH:Finset (Finset (Fin n))hHt:H.IsUniform thcard:m ≤ H.cardhfree:¬H.HasRepeatedDisjointUnionhmem:H ∈ {H ∈ (Finset.powersetCard t Finset.univ).powerset | ¬H.HasRepeatedDisjointUnion}hmax:H.card < forcingThreshold n t⊢ False All goals completed! 🐙 n:ℕt:ℕm:ℕ⊢ (∀ (H : Finset (Finset (Fin n))), H.IsUniform t → m ≤ H.card → H.HasRepeatedDisjointUnion) → forcingThreshold n t ≤ m n:ℕt:ℕm:ℕhm:∀ (H : Finset (Finset (Fin n))), H.IsUniform t → m ≤ H.card → H.HasRepeatedDisjointUnion⊢ forcingThreshold n t ≤ m n:ℕt:ℕm:ℕhm:∀ (H : Finset (Finset (Fin n))), H.IsUniform t → m ≤ H.card → H.HasRepeatedDisjointUnionH:Finset (Finset (Fin n))hHt:H.IsUniform thfree:¬H.HasRepeatedDisjointUnionhmax:H.card + 1 = forcingThreshold n t⊢ forcingThreshold n t ≤ m n:ℕt:ℕm:ℕhm:∀ (H : Finset (Finset (Fin n))), H.IsUniform t → m ≤ H.card → H.HasRepeatedDisjointUnionH:Finset (Finset (Fin n))hHt:H.IsUniform thfree:¬H.HasRepeatedDisjointUnionhmax:H.card + 1 = forcingThreshold n thlt:¬forcingThreshold n t ≤ m⊢ False exact hfree (hm H hHt (n:ℕt:ℕm:ℕhm:∀ (H : Finset (Finset (Fin n))), H.IsUniform t → m ≤ H.card → H.HasRepeatedDisjointUnionH:Finset (Finset (Fin n))hHt:H.IsUniform thfree:¬H.HasRepeatedDisjointUnionhmax:H.card + 1 = forcingThreshold n thlt:¬forcingThreshold n t ≤ m⊢ m ≤ H.card All goals completed! 🐙))

When no edge of size $t$ fits in the ground set, the threshold is one.

n:ℕt:ℕh:n < thempty:Finset.powersetCard t Finset.univ = ∅⊢ forcingThreshold n t = 1 All goals completed! 🐙end Erdos643