On the general position problem on Kneser graphs - Patkós, Balázs (Ars mathematica contemporanea, 2020)
Geodetka v grafu ?$G$? med točkama ?$x$? in ?$x$? je najkrajša pot, ki povezuje ?$x$? z ?$x$?. Podmnožica ?$S$? točk grafa ?$G$? je v splošni legi, če nobena točka množice ?$S$? ne leži na nobeni geodetki med dvema drugima točkama množice ?$S$?. Velikost največje množice točk v splošni legi imenujemo splošnoležnost in označimo z ?$gp(G)$?. Nedavno so Ghorbani in dr. dokazali, da za vsak ?$k$?, ki ustreza pogoju ?$n\ge k^3-k^2+2k-2$?, velja ?$gp(Kn_{n,k})=\binom{n-1}{k-1}$, kjer $Kn_{n,k}$? označuje Kneserjev graf. V članku izboljšamo njihov rezultat in dokažemo, da velja isti zaključek ob predpostavki ?$n\ge 2.5k-0.5$?, in da je ta meja najboljša možna. Naši glavni orodji sta rezultat o križno sekajočih se družinah in rahla posplošitev Bollobásove neenakosti o presečni množici parnih sistemov.
Keywords: general position problem; intersection theorems; Kneser graphs; Kneserjevi grafi; presečni izreki; problem splošne lege