k-Domination invariants on Kneser graphs

NEW

Problem: For fixed positive integers $k,r$, let $K(n,r)$ be the Kneser graph on the $r$-subsets of $[n]$, with adjacency given by disjointness. Let $\gamma_k(n,r)$ be the minimum size of a family $D\subseteq \binom{[n]}r$ such that every $r$-set not in $D$ is disjoint from at least $k$ members of $D$. The problem asks whether there is $n_0=n_0(k,r)<2(k+r)$ such that

Result: Yes. In fact one may take

For $r=1$, $K(n,1)\cong K_n$, and for $n>k$, $\gamma_k(n,1)=k$, so the claim is immediate.

Assume $r\ge2$, and fix $n\ge 2(k+r)-1$. Let $D$ be a minimum $k$-dominating family in $\binom{[n]}r$. For an $(r-1)$-set $A\subseteq[n]$, write

Choose $D$, among all minimum $k$-dominating families, minimizing

We claim $\Phi(D)=0$. Suppose not, so $h_D(A)<k$ for some $A$. Then every $A\cup\{x\}$, $x\in[n]\setminus A$, must lie in $D$; otherwise $A\cup\{x\}\notin D$ would have fewer than $k$ neighbors in $D$.

Let $X=[n]\setminus A$. Choose $R\subseteq X$ with $|R|=k$. Since

we can choose $k$ distinct $r$-sets $H_1,\dots,H_k\subseteq X\setminus R$. Define

We verify that $D'$ is $k$-dominating in $K(n,r)$. If $W\cap A=\varnothing$, then $W\subseteq X$, and the remaining star vertices $A\cup\{x\}$ with $x\in X\setminus(R\cup W)$ are disjoint from $W$. There are at least

such vertices. If $W\cap A\neq\varnothing$, then removed star vertices were not adjacent to $W$. If $W\notin D$, its old $k$ neighbors remain; if $W=A\cup\{x\}$ with $x\in R$, then all $H_i$ are disjoint from $W$. Thus $D'$ is $k$-dominating. Since $D$ was minimum and $|D'|\le |D|$, equality holds and $D'$ is also minimum.

Now $h_{D'}(A)=h_D(A)+k\ge k$. For any $B\neq A$ with $B\cap A\neq\varnothing$, no removed star vertex was disjoint from $B$, so $h_{D'}(B)\ge h_D(B)$. If $B\cap A=\varnothing$, then the remaining star vertices disjoint from $B$ number at least

so $h_{D'}(B)\ge k$. Hence $\Phi(D')<\Phi(D)$, contradicting the choice of $D$. Therefore $\Phi(D)=0$.

Thus for every $(r-1)$-set $A\subseteq[n]$, at least $k$ members of $D$ are disjoint from $A$. Viewing $D$ as a family in $\binom{[n+1]}r$, it still $k$-dominates all old vertices, and it also $k$-dominates every new vertex $A\cup\{n+1\}$. Hence

So monotonicity holds for all $n\ge 2(k+r)-1$, giving the required $n_0<2(k+r)$.

Citation: Problem 20 and notation are from Brešar, Cornet, Dravec, and Henning, “$k$-Domination invariants on Kneser graphs,” arXiv:2312.15464. The one-step improvement proved above is not cited there.