2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Does the hidden constant in $O(n)$ depend on $k$? $\endgroup$ – Jan Kyncl Mar 22 '19 at 0:18
  • $\begingroup$ 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$? $\endgroup$ – Jan Kyncl Mar 22 '19 at 1:04
  • $\begingroup$ $k$ is a constant on which the constant hidden in the $O(.)$ notation can depend. Sorry if this wasn't clear. $\endgroup$ – domotorp Mar 22 '19 at 12:47
  • $\begingroup$ @Jan I've used $\ell$ to denote the number of vertices, sorry that I forgot to mention this. $\endgroup$ – domotorp Mar 22 '19 at 12:52
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I'm sure your solution is correct, but I don't get it. What is a '(unique) source-vertex'? $\endgroup$ – domotorp Mar 23 '19 at 5:58
  • 1
    $\begingroup$ 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. $\endgroup$ – Jan Kyncl Mar 23 '19 at 10:10
  • $\begingroup$ 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$. $\endgroup$ – Mike Mar 23 '19 at 16:52
  • 2
    $\begingroup$ @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. $\endgroup$ – domotorp Mar 23 '19 at 19:29
0
$\begingroup$

******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)$]

$\endgroup$
8
  • $\begingroup$ I saw that the path lengths are longer than $k$. I am currently re-editting.... $\endgroup$ – Mike Mar 21 '19 at 18:12
  • $\begingroup$ Red-editted....... $\endgroup$ – Mike Mar 21 '19 at 20:00
  • $\begingroup$ 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$? $\endgroup$ – domotorp Mar 22 '19 at 6:05
  • $\begingroup$ 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? $\endgroup$ – Mike Mar 22 '19 at 12:27
  • 1
    $\begingroup$ $k$ is a constant on which the constant hidden in the $O(.)$ notation can depend. Sorry if this wasn't clear. $\endgroup$ – domotorp Mar 22 '19 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.