A minimax theorem on intervals (Q801077): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: Covering Regions by Rectangles / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0095-8956(84)90039-x / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2039977337 / rank | |||
Normal rank |
Latest revision as of 09:24, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A minimax theorem on intervals |
scientific article |
Statements
A minimax theorem on intervals (English)
0 references
1984
0 references
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)\).
0 references
vertically convex lattice polygon
0 references
antirectangle
0 references
cover of polygons
0 references
sequence of intervals
0 references