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

$$\rho_2(2r+5,r+2)\ge C(r)\rho_2(2r+1,r).$$

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

Result: Yes. In fact,

$$\rho_2(2r+5,r+2)\ge 2\rho_2(2r+1,r)+1$$

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

$$C(r)=2+\binom{2r+1}{r}^{-1}>2.$$

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

$$1\le |A\cap B|\le s-2.$$

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

$$A=\{a_1,a_2\},\qquad B=\{b_1,b_2\}.$$

Define

$$\mathcal T=\{S\cup A:S\in\mathcal S\}\cup \{S\cup B:S\in\mathcal S\}.$$

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

$$Z=Y\cup\{a_1,b_1\}.$$

For every $S\in\mathcal S$,

$$|Z\cap(S\cup A)|=|Y\cap S|+1,\qquad |Z\cap(S\cup B)|=|Y\cap S|+1.$$

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

$$\rho_2(2r+5,r+2)\ge 2\rho_2(2r+1,r)+1.$$

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

$$2\rho_2(2r+1,r)+1 \ge \left(2+\binom{2r+1}{r}^{-1}\right)\rho_2(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.