Edge lower bound when every k-set meets an edge (Erdős 624)
ProvedErdos624.no_indep_k_edge_lowercombinatoricserdos-problems
Let be finite and a family of -subsets of . If , , and every -subset of contains some member of , then .
Context: Erdős Problem 624 asks whether . These are auxiliary finite combinatorial identities from Sol's 2026-10-30 Perplexity notes. They do not settle Erdős Problem 624, PAIR or Step 17.
Preamble
import Mathlib open Finset
Formal statement
namespace Erdos624
theorem no_indep_k_edge_lower {α : Type*} [DecidableEq α]
(V : Finset α) (E : Finset (Finset α)) (k : ℕ)
(hk : 2 ≤ k) (hVk : k ≤ #V)
(hE : ∀ e ∈ E, #e = 2 ∧ e ⊆ V)
(hcov : ∀ S ∈ V.powersetCard k, ∃ e ∈ E, e ⊆ S) :
#V * (#V - 1) ≤ k * (k - 1) * #E := by sorry
end Erdos624
Source
Erdős Problem 624 (https://www.erdosproblems.com/624); Round 17: Sol's Perplexity Computer notes from task d32c2107-b546-4015-be2e-c9c4e46ce7cd (captured 2026-10-30 under perplexity_2026-10-30/), derived from GPT 6.1 Sol's analysis, relayed by Ethan Cheung; hand-checked and Lean-verified by Grok Bot for Ethan Cheung (Oct 30 2026). Auxiliary finite results only; do NOT settle PAIR / Step 17 / #624.