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

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$$.

• Does the hidden constant in $O(n)$ depend on $k$? Mar 22, 2019 at 0:18
• The number of paths of length $2$ in $K_{1,n}$ is $\Theta(n^2)$; so shouldn't the exponent for the number of paths of length $\ell$ be $\lceil\frac{\ell+1}{2}\rceil$? Mar 22, 2019 at 1:04
• $k$ is a constant on which the constant hidden in the $O(.)$ notation can depend. Sorry if this wasn't clear. Mar 22, 2019 at 12:47
• @Jan I've used $\ell$ to denote the number of vertices, sorry that I forgot to mention this. Mar 22, 2019 at 12:52

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.

• I'm sure your solution is correct, but I don't get it. What is a '(unique) source-vertex'? Mar 23, 2019 at 5:58
• By a "source-vertex" I mean a vertex with indegree 0. By "paths with unique source-vertex" I mean paths with exactly one source-vertex; so excluded are only those paths with the middle vertex of indegree 2. Mar 23, 2019 at 10:10
• I'm missing something here...why would all paths with 4 vertices in $G$ contain a directed path (according to the orientation that gives max out-degree 3) of 3 edges? Consider the path $P=wxyz$ in $G$ where the edges in $P$ according to the orientation are directed $xw$ $xy$, $zy$.
– Mike
Mar 23, 2019 at 16:52
• @Mike Jan didn't talk about directed paths. Take any path with 4 vertices. Then one of its two subpaths on 3 vertices will have the property that its direction is not such that the middle vertex has in-degree 2. Mar 23, 2019 at 19:29

******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$$.

1. 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$$.]

2. 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$$.

3. 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$$.

4. 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)$$]

• I saw that the path lengths are longer than $k$. I am currently re-editting....
– Mike
Mar 21, 2019 at 18:12
• Red-editted.......
– Mike
Mar 21, 2019 at 20:00
• The grid cannot work, as there are $\le 4^kn=O(n)$ paths of length $k$ in it, so I can put all of their vertices to be my $k$-tuples. Did you maybe assume that you have $n^2$ vertices instead of $n$? Mar 22, 2019 at 6:05
• But [in an $n \times n$ grid] you are only allowed $k \times O(n^2)$ $k$-tuples according to the problem statement, but there are $\Omega(2^k n^2)$ paths. Am I understanding the problem correctly?
– Mike
Mar 22, 2019 at 12:27
• $k$ is a constant on which the constant hidden in the $O(.)$ notation can depend. Sorry if this wasn't clear. Mar 22, 2019 at 12:46