Status
On this page
Status
Topics
Status
On this page
Status
Topics
Is it true that every -uniform hypergraph on vertices with at least edges must contain either a subgraph on vertices with edges or a subgraph on vertices with edges?
Source: erdosproblems.com/794
An accepted solution exists. The statement is false.
Disproved, by an elementary counterexample to the statement as printed. The counterexample is the site's, due to Harris, recomputed in the Current assessment: the -uniform hypergraph on whose edges are the triples with one element in each of , , and the triple has edges on vertices, and no four of its vertices span three edges (the check is in the Current assessment), so the statement fails at . The same construction (the complete 3-partite 3-graph on vertices plus one triple inside a class) fails it for every by the same check, a class needing three vertices to hold the extra triple. The frontmatter standing is derived from the accepted claim page Harris's counterexample, whose acceptance evidence is the site's own and which also carries the links to the Lean checks of the example; a pending claim page, Aristotle's Lean proof published by Alexeev, records an independent Lean proof of the construction for every . The site's label DISPROVED (LEAN) carries a catalog suffix explained under Formalization: the counterexample has been checked in Lean in external files the corpus has not built.