On the general position problem on Kneser graphs

Balázs Patkós

Ars Mathematica Contemporanea, Tome 18 (2020) no. 2, pp. 273-280.

Résumé

In a graph G, a geodesic between two vertices x and y 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 ≥ k3 − k2 + 2k − 2, then gp(Knn, k) = (n − 1 choose k − 1), where Knn, k denotes the Kneser graph. We improve on their result and show that the same conclusion holds for n ≥ 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 systems.

Détail

DOI : 10.26493/1855-3974.1957.a0f

Keywords: General position problem, Kneser graphs, intersection theorems