Fix integers and . The Razborov closure of a family of vertex sets of size at most repeatedly adjoins a set whenever there are existing sets whose pairwise intersections are contained in . A family equal to its closure is called -closed.
An inclusion-minimal -set in an upward-closed family cannot belong to an -member delta-system of such minimal sets: its proper core would be adjoined by Razborov closure, violating minimality. The Erdős–Rado sunflower lemma therefore bounds the number of minimal -sets. This weaker factorial bound is sufficient for the superpolynomial monotone clique lower bound.
An -closed family has at most inclusion-minimal members of cardinality . This limits the number of cliques accepted by a proper closed approximation.
Articles by others on the same topic
There are currently no matching articles.