pith. sign in

arxiv: 1903.08056 · v2 · pith:3ACC3RL2new · submitted 2019-03-19 · 🧮 math.CO

On the general position problem on Kneser graphs

classification 🧮 math.CO
keywords generalpositionverticesgeodesicgraphkneserresultbest
0
0 comments X
read the original abstract

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\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\'as's inequality on intersecting set pair systems.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.