292 KB19 KB200820252020Patkós, Balázsletnik:18številka:2str. 273-280ISSN:1855-3966COBISSID_HOST:41154563URN:URN:NBN:SI:doc-0Q2QC4LRenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneageneral position problemintersection theoremsKneser graphsKneserjevi grafipresečni izrekiproblem splošne legeOn the general position problem on Kneser graphs|In a graph ?$G$?, a geodesic between two vertices ?$x$? and ?$x$? is a shortest path connecting ?$x$? to ?$y$?. A subset ?$S$? of the vertices of ?$G$? is in general position if no vertex of ?$S$? lies on any geodesic between two other vertices of ?$S$?. The size of a largest set of vertices in general position is the general position number that we denote by ?$gp(G)$?. Recently, Ghorbani et al, proved that for any ?$k$? if ?$n\ge k^3-k^2+2k-2$?, then ?$gp(Kn_{n,k})=\binom{n-1}{k-1}$?, where ?$Kn_{n,k}$? denotes the Kneser graph. We improve on their result and show that the same conclusion holds for ?$n\ge 2.5k-0.5$? and this bound is best possible. Our main tools are a result on cross-intersecting families and a slight generalization of Bollobás's inequality on intersecting set pair systemsGeodetka 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 sistemovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije