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.

Pravice

URN

URN:NBN:SI:DOC-0Q2QC4LR

COBISSID

41154563

Objavljeno

28.04.2021

Metapodatki

Citiranje

APA:

Patkós, Balázs (2020). On the general position problem on Kneser graphs. Ars mathematica contemporanea, letnik 18, številka 2, str. 273-280. URN:NBN:SI:DOC-0Q2QC4LR from http://www.dlib.si

MLA:

Patkós, Balázs. "On the general position problem on Kneser graphs." Ars mathematica contemporanea letnik 18. številka 2 (2020) str. 273-280.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-0Q2QC4LR>

Ars mathematica contemporanea
2008-
(Zbirni zapis)