k-Domination invariants on Kneser graphs

NEW

Problem: In finite simple graphs, let $K(n,r)$ be the Kneser graph on the $r$-subsets of $[n]$, with adjacency given by disjointness. Let $\rho_2(n,r)$ be the maximum size of a vertex set whose distinct members have graph-distance at least $3$. The reconstructed question asks whether, for every integer $r\ge2$, there is a real number $C(r)>2$ such that

This matches the paper’s notation $\rho_2(n,r)=\rho_2(K(n,r))$ and its stated Problem 23.

Result: Yes. In fact,

for every $r\ge2$. Hence one may take

Proof. For $s\ge2$, a family $\mathcal F\subseteq \binom{[2s+1]}s$ is a $2$-packing in $K(2s+1,s)$ iff every two distinct $A,B\in\mathcal F$ satisfy

Indeed, $|A\cap B|=0$ means adjacency, while $A,B$ have a common neighbor iff $[2s+1]\setminus(A\cup B)$ has size at least $s$, i.e. iff $|A\cap B|+1\ge s$.

Let $\mathcal S$ be a maximum $2$-packing in $K(2r+1,r)$. Add four new points split as

Define

For distinct $S,S'\in\mathcal S$, intersections inside $\mathcal T$ are either $|S\cap S'|$, $|S\cap S'|+2$, or $r$, all lying between $1$ and $r=(r+2)-2$. Thus $\mathcal T$ is a $2$-packing in $K(2r+5,r+2)$ of size $2|\mathcal S|$.

Since $r\ge2$, $\mathcal S\ne \binom{[2r+1]}r$; for example two $r$-sets with intersection $r-1$ cannot both lie in a $2$-packing. Choose $Y\in\binom{[2r+1]}r\setminus\mathcal S$, and set

For every $S\in\mathcal S$,

Because $Y\ne S$, we have $|Y\cap S|\le r-1$, so these intersections lie between $1$ and $r$. Hence $\mathcal T\cup\{Z\}$ is a $2$-packing in $K(2r+5,r+2)$. Therefore

Finally, since $1\le \rho_2(2r+1,r)\le \binom{2r+1}{r}$,

which proves the claim.

Audit: No extra hypotheses beyond $r\ge2$ were introduced. The proof uses only the standard Kneser graph definition and the exact distance characterization for odd Kneser graphs, proved above. The conclusion gives an explicit $C(r)>2$, exactly matching the reconstructed statement.

Citation: Problem source: Brešar, Cornet, Dravec, Henning, “$k$-Domination invariants on Kneser graphs,” arXiv:2312.15464, Problem 23. No prior resolution is used here.