A minimax theorem on intervals

Permutations, words, matrices (05A05) Combinatorial aspects of packing and covering (05B40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A board is a finite set of unit squares lying in the plane whose corners have integer coordinates. A rectangle is a subset of the board whose union is rectangular. A cover of a board B is a collection of rectangles whose union is equal to B. Denote \(\theta\) (B) the minimum number of rectangles in a cover of B. An antirectangle in B is a set of squares in B no two of which are contained in a common rectangle. Denote \(\alpha\) (B) the maximum number of squares in an antirectangle of B. It is obvious that \(\alpha (B)\leq \theta (B).\) The author proves the following theorem: Let B be a finite, vertically convex board (i.e., whenever two squares in B are on the same vertical line, all squares between them are in B). Then \(\alpha (B)=\theta (B)\). Actually the following conjecture of A. Frank is proved which implies this theorem. Let S be a finite set of intervals. Denote \(\alpha '(S)=\max \{m;\) there exists a sequence \(I_ 1,...,I_ m\) of members in S such that \(\cup^{k-1}_{j=1}I_ j\neq \cup^{k}_{j=1}I_ j\) for \(k=2,3,...,m\}\), \(\theta '(S)=\min \{| G|;\) G is a set of intervals and every element of S is a union of members of \(G\}\). Then \(\alpha '(S)=\theta '(S)\).

Recommendations

Cites work

Covering Regions by Rectangles

Cited in

(17)

This page was built for publication: A minimax theorem on intervals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q801077)