Description
Ambrus, Bárány, Frankl, Varga: Piercing the chessboard
(https://arxiv.org/abs/2111.09702) cikkben azt vizsgálták,
hogy minimum hány egyenes kell ahhoz, hogy az nxn-es tábla
mindegyik mezőjét messe valamelyik egyenesünk. Ha a mezők zárt
négyzetek, akkor viszonylag egyszerű a probléma. Ha azonban
a mezőket nyiltaknak tekintjük, akkor egy komoly problémát
kapunk.
A fenti cikk eredménye, hogy 0.7n egyenes kell és n-1 elég.
A használt módszerek lineáris programozás, illetve egy
folytonos súlyfüggvényes módszer.
A fenti eredményeket összefoglalom és megvizsgálom, hogy
mi történik, ha a geometriai egyeneseket "lecseréljük"
kombinatorikus jellemzésű mezőhalmazokkal. Az igazán
érdekes alsó becslést (jelenlegi csúcs 0.7n) jól
megközelíthetjük teljesen elemi módszerekkel.
Közös kutatás Mészáros Violával.