Does any long path in a planar graph contain one of O(n) k-tuple of vertices?

Question

My question is a bit related to both the container method and shallow cell complexity. Let's start with that the number of length $\ell$ paths (where $\ell$ denotes the number of vertices of the path!) in a planar graph on $n$ vertices is $O(n^{\lfloor\frac{\ell+1}2\rfloor})$ (where the hidden constant depends on $\ell$). This follows from that there are $O(n)$ choices for every second edge. It is also best possible as shown by blowing up every second vertex of a path of length $\ell$ to $n/\ell$ vertices. Now I'll state my question.

Is it true that in a planar graph on $n$ vertices one can select $O(n)$ ${\lceil\frac{\ell+1}2\rceil}$-tuples of vertices such that any path of length $\ell$ contains one of these ${\lceil\frac{\ell+1}2\rceil}$-tuples among its vertices?

Note that this would also imply that the number of length $\ell$ paths is $O(n\cdot n^{\ell-\lceil\frac{\ell+1}2\rceil})=O(n^{\lfloor\frac{\ell+1}2\rfloor})$, as there are $O(n^{\ell-\lceil\frac{\ell+1}2\rceil})$ ways one can select the remaining vertices of the path. Another, probably nicer way to state the question is if we let $k=\lceil\frac{\ell+1}2\rceil$.

Is it true that in a planar graph on $n$ vertices one can select $O(n)$ $k$-tuples of vertices such that any path of length $2k-2$ contains one of these $k$-tuples among its vertices?

This is trivial for $k=1,2$ as the number of vertices/edges is $O(n)$. That we cannot hope to hit all paths of length $2k-3$ by $k$-tuples is shown by the same example as above; blow up every second vertex of a path of length $2k-3$ to $n/k$ vertices.

I couldn't even prove my question for $k=3$, nor show that it would hold with some other function $f(k)$ instead of $2k-2$.

Answer 1

For $k=3$ there are $O(n)$ such triples, in fact paths with three vertices.

Orient the planar graph $G$ so that the maximum outdegree is at most $3$. In such an orientation there are $O(n)$ paths with three vertices and with unique source-vertex (those are either directed paths or paths whose edges are oriented from the central vertex to the endvertices). Every path with $4$ vertices contains a subpath with a unique source-vertex, since source-vertices cannot be neighbors.

Answer 2

******If the constant hidden in the $O$-notation is absolute i.e., independent of $k$, or is even only allowed to grow linearly with $k$ [and in fact even if the constant is allowed to grow poly$(k)$], the answer is no. Here is a SKETCH.

1. Let $G$ be an $n \times n$ grid i.e., $V(G) = \{(i,j); i,j \in \{1,\ldots, n\}$ and $(i,j)$ is adjacent to $(i',j')$ iff $|i'-i| +|j'-j| = 1$ (no wraparound), and let $k \le 4 \log n$ but at least a large enough constant.

2. Then for every set $S$ of $k$-tuples of $V(G)$ satisfying $|S| = O(kn^2)$ and any positive integer $\ell \in O(k)$ of your choosing [so $\ell=2k$ will do], there is at least one vertex $v$ in the southwest quadrant of $G$ there are at most $O(\ell^2 \frac{k|S|}{|V(G)|})$ = $O(\ell^2k^2)$ of the $k$-tuples of $S$ that cover any vertex within distance $\ell$ of $v$ in $G$. So now fix such an $\ell$ and then a $v$.

3. Then let $S_v$ be the set of $k$-tuples $X$ of $S_v$ s.t. every vertex in $X$ is within distance $\ell$ of $v$. Then $|S_v| = O(\ell^2 \frac{k|S|}{|V(G)|}) = O(k^4)$, as $\ell \in O(k)$.

4. Now let $Q$ be the set of paths of length $\ell$ starting at $v$ in $G$ such that each $P \in Q$ heads north or east in the grid $G$ from $v$ at each step. Then $|Q| = 2^{\ell}$, and furthermore, if a path $P \in Q$ covers an $X \in S$, then $P$ covers an $X \in S_v$. We show that there is a $P \in Q$ that does not contain any $X \in S_v$.

5. Each vertex in $G$ can be specified by the ordered pair $(x,y); x=1,\ldots, n$; $y=1,2,\ldots, n$. Write $v = (x_0,y_0)$. For each $j=0,1,2,\ldots, \ell$ let

$$U^j \doteq \{(x,y); x \ge x_0; y \ge y_0; x+y=x_0+y_0+j \}$$. Then every $P \in Q$ contains exactly one vertex in $U^j$ for each $j=0,1,2,\ldots, \ell$.

6. Let $X \in S_v$. Then if there exists a $j$ such that $|X \cap U^j| \geq 2$ then no $P \in Q$ covers $X$. Otherwise for $\ell \geq k$ there are at most $2^{\ell-k+1}$ paths $P \in Q$ cover $X$. [Indeed let $u \in U^j$ and $u' \in U^{j+i}$, then there are no more than ${i \choose {\frac{i}{2}}} \le 2^{i-1}$ ways to head from $u$ to $u'$ heading north or east at each step. So let $X =\{u_1, \ldots, u_k\} \in S_v$ be such that $u_i \in U^{j_i}$ where the $j_i$s are strictly increasing. Then there are at most $2^{j_1-1}2^{j_2-j_1-1} \ldots 2^{j_k-j_{k-1}-1}2^{\ell-j_k} = 2^{\ell-k}$ paths in $Q$ containing all of $u_1,\ldots, u_k$ and thus all of $X$.]

7. So from 6. there are at most $2^{\ell-k+1}|S_v|$ $=2^{\ell-k+1}O(k^4)$ paths in $Q$ that cover an $X \in S_v$.

8. But $|Q| = 2^{\ell} > 2^{\ell-k+1}O(k^4)$ for $k$ as in 1. above so there is at least one $P \in Q$ that does not cover any $X \in S_v$.

9. So by 4. above there is at least one $P \in Q$ that does not cover any $X \in S$. $\surd$

---

And in fact if $k$ is allowed to increase with the number $n$ of vertices at a certain rate e.g., $k = \theta(\log^2 n)$ with the path lengths $\ell$ staying at $\theta(k)$, then the size of these smallest such set of $k$-tuples would have to increase faster than any function in poly$(kn)$ [and not just any function in $O(kn)$]