Let be a down-set in an -element Boolean lattice, and let its layer be nonempty, with . Define byThe real binomial coefficient is continuous and strictly increasing for , starting at one, so this parameter exists uniquely. It measures an effective number of coordinates rather than the actual size of the support.
The Lovász shadow bound and give , hence whenever the later layer is nonempty. For all subsets of a fixed -element set, embedded in the larger ground set, one has for every .
The positive-rank condition is necessary: a nonempty zero layer has size one, while for every , so it determines no unique parameter. Empty layers likewise have no parameter in the displayed range.
For a down-set on coordinates, let . For with , the effective ground-set parameter of a hereditary uniform layer gives the displayed ratio bound. Iteration is valid up to the first empty layer. In particular, whenever , ; if the later layer is empty this conclusion is immediate. Ratios with are undefined and must be replaced by the assertion that all later layers are empty.
Articles by others on the same topic
There are currently no matching articles.