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
    0 references
    transversal
    0 references
    Katchalski-Lewis conjecture
    0 references
    0 references
    0 references