SPB Git

spb/wp32_uqo

Public
2.9 KB · 31 lines latex
1% Section: Upper bounds2\section{Upper bounds}\label{sec:upper}34\begin{proposition}[the uniform bound $12$]\label{prop:P7}5For every $n\ge 12$ the set $S=\{u_0,\dots,u_{11}\}$ is a zero-forcing set of $\PP{n}{5}$. Hence $\Z(\PP{n}{5})\le 12$ for all $n\ge 11$.6\end{proposition}78\begin{proof}9For $n=12$, $S$ is the whole outer layer and each $u_i$ forces $v_i$ through its spoke. Let $n\ge 13$.1011\emph{Phase 1.} For $i=1,\dots,10$ perform $u_i\to v_i$: the other neighbours $u_{i-1},u_{i+1}$ of $u_i$ lie in $S$ because $0\le i-1$ and $i+1\le 11$. Then $v_5\to v_0$ ($N(v_5)=\{u_5,v_{10},v_0\}$, the first two black) and $v_6\to v_{11}$ ($N(v_6)=\{u_6,v_1,v_{11}\}$). Now columns $0,\dots,11$ are black and columns $12,\dots,n-1$ white (column $n-1\ne 11$ since $n\ge 13$).1213\emph{Phase 2.} For $j=12,\dots,n-1$ in increasing order perform $u_{j-1}\to u_j$ and then $v_{j-5}\to v_j$. Invariant before stage $j$: columns $<j$ black, columns $\ge j$ white. $N(u_{j-1})=\{u_{j-2},v_{j-1},u_j\}$ with the first two in columns $<j$, so the first force is legal; it leaves $v_j$ as the only white neighbour of $v_{j-5}$, because $N(v_{j-5})=\{u_{j-5},v_{j-10},v_j\}$ and $j-5\ge 7$, $j-10\ge 2$ are columns in $[0,j)$. After stage $n-1$ every vertex is black. For $n=11$ the value $6<12$ is part of Theorem~\ref{thm:main}.14\end{proof}1516This is the $2k+2$ bound of \citet{alameda2018families} and \citet[Theorem~2.2]{rashidi2020petersen}; the column-by-column proof is the $k=4$ argument of \citet{arxiv2610_24059} with the indices adjusted to $k=5$. Figure~\ref{fig:chronology}(a) shows the chronology on $\PP{14}{5}$; it was replayed by an independent program for every $12\le n\le 300$ (Section~\ref{sec:robustness}). For $11\le n\le 22$ the upper bounds in Theorem~\ref{thm:main} are given by explicit sets found by exhaustive search; Table~\ref{tab:witnesses} (Appendix~\ref{app:tables}) lists one minimum zero-forcing set for each $n$ and Figure~\ref{fig:chronology}(b) shows an $8$-vertex set for $\PP{15}{5}$ together with its full chronology. Every stored witness is accompanied by its chronology and was replayed force by force by a checker that shares no code with the solvers.1718\begin{figure}[t]19\centering20\begin{subfigure}[t]{0.48\textwidth}\centering21\includegraphics[width=\linewidth]{fig2a_chronology_P14_5_P7.pdf}22\caption{Proposition~\ref{prop:P7} on $\PP{14}{5}$: $S=\{u_0,\dots,u_{11}\}$, $16$ forces.}23\end{subfigure}\hfill24\begin{subfigure}[t]{0.48\textwidth}\centering25\includegraphics[width=\linewidth]{fig2b_chronology_P15_5_optimal.pdf}26\caption{A minimum zero-forcing set of $\PP{15}{5}$ ($|S|=8=\Z$), $22$ forces.}27\end{subfigure}28\caption{Two independently replayed forcing chronologies. Black vertices form the initial set; each other vertex carries the step at which it was forced; arrows point from the forcing vertex to the forced vertex. Both chronologies were re-validated force by force by the figure generator before drawing.}29\label{fig:chronology}30\end{figure}31
Files · main
Menu

Theme