A minimax theorem on intervals (Q801077): Difference between revisions

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)\).