New bounds on the Katchalski-Lewis transversal problem (Q1404508)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New bounds on the Katchalski-Lewis transversal problem |
scientific article |
Statements
New bounds on the Katchalski-Lewis transversal problem (English)
0 references
21 August 2003
0 references
Let \({\mathcal F}\) be a family of disjoint translates of a compact convex set in the plane with the property that each three members of \({\mathcal F}\) are met by a line. Katchalski and Lewis showed in 1982 that there is a number \(k\), independent of \({\mathcal F}\), so that some line meets all but at most \(k\) members of \({\mathcal F}\). They also conjectured that one can choose \(k=2\). The present author sets a new record by showing that \(k\leq 22\), and he disproves the Katchalski-Lewis conjecture by constructing a family of disjoint translates of a parallelogram, each three met by a line, but where any line misses at least four members.
0 references
transversal
0 references
Katchalski-Lewis conjecture
0 references