For two set families forbidding all cross-intersections in , split into absent and present coordinate sections. The section pairs , , and forbid, respectively, , , and in one fewer dimension. For , either one of the first two pairs, allowing exchange of the set family names, increases the density product by at least , or the third widens the interval and retains at least of that product. This converts a single forbidden intersection into a long forbidden interval while recording every density gain and loss.
Let two set families on coordinates forbid cross-intersection size , and let be their density product. For , put , , and . Repeated forbidden-intersection density increments terminate when one endpoint of the forbidden interval reaches zero or the remaining dimension. In the first case, if steps widened the interval, the cross-intersection bound from cube separation gives . In the second case, at least steps occurred and at most widened, giving . For a single set family take the square of its density. Choosing proves for forbidden intersections and , with small dimensions handled directly.
Articles by others on the same topic
There are currently no matching articles.